梯度投影算法在稀疏重建中的应用：压缩感知和其他逆问题
需积分: 10 127 浏览量
更新于2024-09-09
收藏 215KB PDF 举报
"这篇论文探讨了梯度投影算法在稀疏重建，特别是在压缩传感和其它逆问题中的应用。作者Mario A. T. Figueiredo、Robert D. Nowak和Stephen J. Wright针对未定或病态线性方程组中寻找稀疏解的问题进行了深入研究，提出了一种基于边界约束二次规划(BCQP)的梯度投影(GP)算法。"
正文:
在信号处理和统计推断领域，许多问题涉及到求解未定或者条件恶劣的线性方程组中的稀疏解。一个常见的方法是通过最小化包含平方误差项（ℓ2范数）和促进稀疏性的正则化项（ℓ1范数）的目标函数来实现。基础追求、最小绝对收缩选择算子（LASSO）、基于小波的去卷积以及压缩传感等都是这种方法的典型应用。
本文提出的梯度投影算法(GP)用于解决边界约束二次规划问题(BCQP)，这是一种优化框架，旨在找到既能最小化误差又能保持解的稀疏性的解。GP算法的核心在于利用梯度信息进行迭代更新，每次迭代将当前解沿着梯度的负方向投影到约束集内，从而逐步逼近最优解。
为了提高算法的性能，作者测试了不同线搜索参数选择策略的变体，包括基于Barzilai-Borwein方法的技术。Barzilai-Borwein方法是一种在梯度法中用于确定步长的策略，它通常能提供良好的收敛速度，并且在许多优化问题中表现优秀。
实验结果显示，这些GP方法在处理压缩传感和其他逆问题时表现出色。压缩传感是现代信号处理的一个重要分支，它利用信号的稀疏性和测量矩阵的特性，能够在远小于信号维数的观测中重构信号。GP算法在这一领域的应用，展示了其在处理高维、稀疏数据时的有效性和效率。
总结来说，"Gradient Projection for Sparse Reconstruction"这篇论文不仅提出了新的优化算法，还提供了在实际问题中应用这些算法的方法，特别是在压缩传感这一领域，对信号处理和数据恢复技术有重要贡献。通过结合不同的线搜索策略，GP算法在寻找稀疏解方面展现了强大的竞争力，为解决未定线性系统的挑战提供了新的工具。
TO APPEAR IN THE IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, 2007. 3
as an EM algorithm, in the context of image deconvolution
problems [45], [25]. IST can also be derived in a majorization-
minimization (MM) framework
2
[16], [26] (see also [23],
for a related algorithm derived from a different perspective).
Convergence of IST algorithms was shown in [13], [16].
IST algorithms are based on bounding the matrix A
T
A (the
Hessian of ky − Axk
2
2
) by a diagonal D (i.e., D − A
T
A
is positive semi-definite), thus attacking (1) by solving a
sequence of simpler denoising problems. While this bound
may be reasonably tight in the case of deconvolution (where
R is usually a square matrix), it may be loose in the CS case,
where matrix R usually has many fewer rows than columns.
For this reason, IST may not be as effective for solving (1) in
CS applications, as it is in deconvolution problems.
Finally, we mention matching pursuit (MP) and orthogonal
MP (OMP) [5], [17], [20], [56], which are greedy schemes
to find a sparse representation of a signal on a dictionary of
functions. (Matrix A is seen as an n-element dictionary of
k-dimensional signals). MP works by iteratively choosing the
dictionary element that has the highest inner product with the
current residual, thus most reduces the representation error.
OMP includes an extra orthogonalization step, and is known
to perform better than standard MP. Low computational cost
is one of the main arguments in favor of greedy schemes like
OMP, but such methods are not designed to solve any of the
optimization problems above. However, if y = Ax, with x
sparse and the columns of A sufficiently incoherent, then OMP
finds the sparsest representation [56]. It has also been shown
that, under similar incoherence and sparsity conditions, OMP
is robust to small levels of noise [20].
C. Proposed Approach
The approach described in this paper also requires only
matrix-vector products involving A and A
T
, rather than
explicit access to A. It is essentially a gradient projection (GP)
algorithm applied to a quadratic programming formulation of
(1), in which the search path from each iterate is obtained by
projecting the negative-gradient direction onto the feasible set.
(See [3], for example, for background on gradient projection
algorithms.) We refer to our approach as GPSR (gradient
projection for sparse reconstruction). Various enhancements to
this basic approach, together with careful choice of stopping
criteria and a final debiasing phase (which finds the least
squares fit over the support set of the solution to (1)), are
also important in making the method practical and efficient.
Unlike the MM approach, GPSR does not involve bounds
on the matrix A
T
A. In contrasts with the IP approaches
discussed above, GPSR involves only one level of iteration.
(The approaches in [11] and [36] have two iteration levels—an
outer IP loop and an inner CG, PCG, or LSQR loop. The ℓ
1
-
magic algorithm for (3) has three nested loops—an outer log-
barrier loop, an intermediate Newton iteration, and an inner
CG loop.)
GPSR is able to solve a sequence of problems (1) efficiently
for a sequence of values of τ. Once a solution has been
2
Also known as bound optimization algorithms (BOA). For a general
introduction to MM/BOA, see [33].
obtained for a particular τ, it can be used as a “warm-start”
for a nearby value. Solutions can therefore be computed for a
range of τ values for a small multiple of the cost of solving
for a single τ value from a “cold start.” This feature of GPSR
is somewhat related to that of LARS and other homotopy
schemes, which compute solutions for a range of parameter
values in succession. In particular, “warm-starting” allows
using GPSR within a continuation scheme (as suggested in
[31]). IP methods such as those in [11], [36], and ℓ
1
-magic
have been less successful in making effective use of warm-
start information, though this issue has been investigated in
various contexts (see, e.g., [30], [35], [61]). To benefit from
a warm start, IP methods require the initial point to be not
only close to the solution but also sufficiently interior to the
feasible set and close to a “central path,” which is difficult to
satisfy in practice.
II. PROPOSED FORMULATION
A. Formulation as a Quadratic Program
The first key step of our GPSR approach is to express (1)
as a quadratic program; as in [28], this is done by splitting
the variable x into its positive and negative parts. Formally,
we introduce vectors u and v and make the substitution
x = u − v, u ≥ 0, v ≥ 0. (6)
These relationships are satisfied by u
i
= (x
i
)
+
and v
i
=
(−x
i
)
+
for all i = 1, 2, . . . , n, where (·)
+
denotes the
positive-part operator defined as (x)
+
= max{0, x}. We thus
have kxk
1
= 1
T
n
u + 1
T
n
v, where 1
n
= [1, 1, . . . , 1]
T
is the
vector consisting of n ones, so (1) can be rewritten as the
following bound-constrained quadratic program (BCQP):
min
u,v
1
2
ky − A(u − v)k
2
2
+ τ 1
T
n
u + τ 1
T
n
v,
s.t. u ≥ 0 (7)
v ≥ 0.
Note that the ℓ
2
-norm term is unaffected if we set u ← u+s
and v ← v + s, where s ≥ 0 is a shift vector. However such
a shift increases the other terms by 2 τ 1
T
n
s ≥ 0. It follows
that, at the solution of the problem (7), u
i
= 0 or v
i
= 0, for
i = 1, 2, . . . , n, so that in fact u
i
= (x
i
)
+
and v
i
= (−x
i
)
+
for all i = 1, 2 , . . . , n, as desired.
Problem (7) can be written in more standard BCQP form,
min
z
c
T
z +
1
2
z
T
Bz ≡ F (z),
s.t. z ≥ 0, (8)
where
z =
u
v
, b = A
T
y, c = τ 1
2n
+
−b
b
and
B =
A
T
A −A
T
A
−A
T
A A
T
A
. (9)
剩余11页未读，继续阅读
2009-06-08 上传
2021-05-30 上传
2023-11-26 上传
2022-05-18 上传
2021-02-07 上传
2022-07-15 上传
2024-11-10 上传
2024-11-10 上传
2024-11-10 上传
2024-11-10 上传
totoroproactive
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- NIST REFPROP问题反馈与解决方案存储库
- 掌握LeetCode习题的系统开源答案
- ctop：实现汉字按首字母拼音分类排序的PHP工具
- 微信小程序课程学习——投资融资类产品说明
- Matlab犯罪模拟器开发：探索《当蛮力失败》犯罪惩罚模型
- Java网上招聘系统实战项目源码及部署教程
- OneSky APIPHP5库：PHP5.1及以上版本的API集成
- 实时监控MySQL导入进度的bash脚本技巧
- 使用MATLAB开发交流电压脉冲生成控制系统
- ESP32安全OTA更新：原生API与WebSocket加密传输
- Sonic-Sharp: 基于《刺猬索尼克》的开源C#游戏引擎
- Java文章发布系统源码及部署教程
- CQUPT Python课程代码资源完整分享
- 易语言实现获取目录尺寸的Scripting.FileSystemObject对象方法
- Excel宾果卡生成器：自定义和打印多张卡片
- 使用HALCON实现图像二维码自动读取与解码
