ALTERNATING DIRECTION ALGORITHMS FOR l1-PROBLEMS IN COMPRESSIVE SENSING
ALTERNATING DIRECTION ALGORITHMS FOR l1-PROBLEMS IN COMPRESSIVE SENSING
复制标题
压缩感知中 L1 问题的交替方向算法
DOI：
10.1137/090777761
复制
发表时间：
2011-01-01
影响因子：
3.1
通讯作者：
Zhang, Yin
中科院分区：
文献类型：
--
作者：
Yang, Junfeng;Zhang, Yin
在本文中，我们提出并研究使用交替方向算法的压缩感知稀疏解恢复所产生的几个l（1）-范数最小化问题，包括基追踪问题，无约束和约束形式的基追踪去噪问题等。我们提出并研究两类算法，无论是原始或对偶形式的l（1）-问题。算法的构造包括两个主要步骤：（1）通过添加新的变量和约束将l（1）-问题转化为具有块可分目标函数的问题;（2）对所得问题的增广拉格朗日函数应用精确或不精确交替方向方法。由于在每次迭代中原始变量和对偶变量都被更新，因此所导出的交替方向算法可以被看作是一阶原始-对偶算法。这些算法的收敛性建立或重述时，他们已经存在。使用随机化的部分沃尔什-阿达玛传感矩阵进行了大量的数值实验，以证明所提出的方法的通用性和有效性。此外，我们提出的数值结果强调两个实际上重要的，但可能被忽视的点：（i）算法的速度应评估相对于适当的解决方案的准确性;（ii）当错误的测量可能存在，l（1）-保真度一般应优于l（2）-保真度。
In this paper, we propose and study the use of alternating direction algorithms for several l(1)-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis pursuit denoising problems of both unconstrained and constrained forms, and others. We present and investigate two classes of algorithms derived from either the primal or the dual form of l(1)-problems. The construction of the algorithms consists of two main steps: (1) to reformulate an l(1)-problem into one having blockwise separable objective functions by adding new variables and constraints; and (2) to apply an exact or inexact alternating direction method to the augmented Lagrangian function of the resulting problem. The derived alternating direction algorithms can be regarded as first-order primal-dual algorithms because both primal and dual variables are updated at every iteration. Convergence properties of these algorithms are established or restated when they already exist. Extensive numerical experiments are performed, using randomized partial Walsh-Hadamard sensing matrices, to demonstrate the versatility and effectiveness of the proposed approach. Moreover, we present numerical results to emphasize two practically important but perhaps overlooked points: (i) that algorithm speed should be evaluated relative to appropriate solution accuracy; and (ii) that when erroneous measurements possibly exist, the l(1)-fidelity should generally be preferable to the l(2)-fidelity.