Iteratively Reweighted Least Squares Minimization for Sparse Recovery
Iteratively Reweighted Least Squares Minimization for Sparse Recovery
复制标题
DOI：
10.1002/cpa.20303
复制
发表时间：
2010-01-01
影响因子：
3
通讯作者：
Guentuerk, C. Sinan
中科院分区：
文献类型：
--
作者：
Daubechies, Ingrid;Devore, Ronald;Guentuerk, C. Sinan
在\(m\times N\)矩阵\(\Phi\)（其中\(m<N\)）满足某些条件（称为限制等距性质，或RIP）的情况下，属于\(\mathbb{R}^N\)且稀疏的向量\(x\)（即其大部分元素等于\(0\)）可以从\(y := \Phi x\)精确恢复，尽管\(\Phi^{-1}(y)\)通常是一个\((N - m)\)维超平面；此外，此时\(x\)等于\(\Phi^{-1}(y)\)中\(\ell_1\)范数最小的元素。这个最小元素可以通过线性规划算法确定。我们研究一种确定\(x\)的替代方法，即作为一种迭代重加权最小二乘（IRLS）算法的极限。对于给定的权重向量\(w\)，这种IRLS的主要步骤是找到\(\Phi^{-1}(y)\)中\(\ell_2(w)\)范数最小的元素。如果\(x^{(n)}\)是第\(n\)次迭代步骤的解，那么新的权重\(w^{(n)}\)定义为\(w_i^{(n)} := [|x_i^{(n)}|^2+\epsilon^2(n)]^{-1/2}\)，\(i = 1,\ldots,N\)，其中\(\epsilon(n)\)是一个自适应定义的递减序列；然后使用这个更新的权重来获得\(x^{(n + 1)}\)，并重复该过程。我们证明当\(\Phi\)满足RIP条件时，对于所有的\(y\)，序列\(x^{(n)}\)都收敛，无论\(\Phi^{-1}(y)\)是否包含一个稀疏向量。如果\(\Phi^{-1}(y)\)中有一个稀疏向量，那么极限就是这个稀疏向量，并且当\(x^{(n)}\)足够接近极限时，算法的剩余步骤呈指数级快速收敛（在数值优化的术语中是线性收敛）。对于权重\(w_i^{(n)} = [|x_i^{(n)}|^2+\epsilon^2(n)]^{-1+\tau/2}\)，\(i = 1,\ldots,N\)（其中\(0 < \tau < 1\)）的相同算法也可以恢复稀疏解；更重要的是，我们表明其局部收敛是超线性的，并且当\(\tau\)趋近于\(0\)时接近二次收敛速率。（C）2009威利期刊公司
Under certain conditions (known as the restricted isometry property, or RIP) on the m x N matrix Phi (where m < N), vectors x is an element of R-N that arc sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Phi x even though Phi(-1) (y) is typically an (N-m)-dimensional hyperplane; in addition x is then equal to the element in Phi(-1) (y) of minimal l(1)-norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Phi(-1) (y) with smallest l(2)(w)-norm. If x((n)) is the solution at iteration step n, then the new weight w((n)) is defined by w(i)((n)) := [|x(i)((n))|(2) + epsilon(2)(n)](-1/2), i = 1,...,N, for a decreasing sequence of adaptively defined epsilon(n); this updated weight is then used to obtain x((n+1)) and the process is repeated. We prove that when Phi satisfies the RIP conditions, the sequence x((n)) converges for all y, regardless of whether Phi(-1) (y) contains a sparse vector. If there is a sparse vector in Phi(-1) (y), then the limit is this sparse vector, and when x((n)) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the "heavier" weight w(i)((n)) = [|x(i)((n))|(2) + epsilon(2)(n)](-1+tau/2), i = 1,...,N, where 0 < tau < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for tau approaching 0. (C) 2009 Wiley Periodicals, Inc.