梯度投影算法在稀疏重建中的应用：压缩感知和其他逆问题

需积分: 10 86 浏览量更新于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

[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

A (the

Hessian of ky − Axk

) by a diagonal D (i.e., D − A

is positive semi-deﬁnite), 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 ﬁnd 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 sufﬁciently incoherent, then OMP

ﬁnds 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

, 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 ﬁnal debiasing phase (which ﬁnds the least

squares ﬁt over the support set of the solution to (1)), are

also important in making the method practical and efﬁcient.

Unlike the MM approach, GPSR does not involve bounds

on the matrix A

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 ℓ

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) efﬁciently

for a sequence of values of τ. Once a solution has been

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 ℓ

-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 beneﬁt from

a warm start, IP methods require the initial point to be not

only close to the solution but also sufﬁciently interior to the

feasible set and close to a “central path,” which is difﬁcult to

satisfy in practice.

II. PROPOSED FORMULATION

A. Formulation as a Quadratic Program

The ﬁrst 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 satisﬁed by u

= (x

)

and v

(−x

)

for all i = 1, 2, . . . , n, where (·)

denotes the

positive-part operator deﬁned as (x)

= max{0, x}. We thus

have kxk

= 1

u + 1

v, where 1

= [1, 1, . . . , 1]

is the

vector consisting of n ones, so (1) can be rewritten as the

following bound-constrained quadratic program (BCQP):

min

u,v

ky − A(u − v)k

+ τ 1

u + τ 1

s.t. u ≥ 0 (7)

v ≥ 0.

Note that the ℓ

-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

s ≥ 0. It follows

that, at the solution of the problem (7), u

= 0 or v

= 0, for

i = 1, 2, . . . , n, so that in fact u

= (x

)

and v

= (−x

)

for all i = 1, 2 , . . . , n, as desired.

Problem (7) can be written in more standard BCQP form,

min

z +

Bz ≡ F (z),

s.t. z ≥ 0, (8)

where

z =





, b = A

y, c = τ 1



−b



and

B =



A −A

−A

A A



. (9)

剩余11页未读，继续阅读

totoroproactive

粉丝: 0
资源: 1

梯度投影算法在稀疏重建中的应用：压缩感知和其他逆问题

认知WSN的自适应能量有效梯度投影稀疏重构

OMP算法在图像压缩恢复中的应用研究

压缩感知技术在图像向下缩放重建中的应用

Gradient Projection for Sparse Reconstruction

gradient projection for sparse reconstruction

matlab_压缩传感方面的Gradient Projection for Sparse Reconstruction 工具包

Holographic SAR Tomography Image Reconstruction by Combination of Adaptive Imaging and Sparse Bayesian Inference

orthogonal least squares.zip_GP-OLS_The Signal_sparse_sparse ols

GPSR算法源代码实现SBHE矩阵与投影矩阵梯度投影

玄武岩纤维行业研究报告 新材料技术 玄武岩纤维 性能应用 市场分析

最新资源

玄武岩纤维行业研究报告新材料技术玄武岩纤维性能应用市场分析