Iteratively Re-weighted Least Squares Minimization for Sparse Recovery
Abstract
Under certain conditions (known as the Restricted Isometry Property or RIP) on the m x N matrix (where m < N), vectors x included in R(sup N) that are sparse (i.e. have most of their entries equal to zero) can be recovered exactly from y := Phi-x even though Phi(inverse)(y) is typically an (N - m)- dimensional hyperplane; in addition x is then equal to the element in Phi(inverse)(y) of minimal L1-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 Re-weighted Least Squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Phi(inverse)(y) with smallest L2(w)-norm. If x(n) is the solution at iteration step n then the new weight w(n) is defined by wi(n) := [magnitude-xi(n)(exp 2) + epsilon(n)exp(2)]exp( -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 satisfies the RIP conditions, the sequence x(n) converges for all y, regardless of whether Phi(inverse)(y) contains a sparse vector. If there is a sparse vector in Phi(inverse)(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 [magnitude-xi(n)(exp -1 + lambda/2) + epsilon(n)exp(2)]exp( -1/2) , i = 1, . . . ,N, where lambda is between 0 and 1, can recover sparse solutions as well more importantly, we show its local convergence is superlinear and approaches a quadratic rate for lambda approaching to zero.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 14, 2008
- Accession Number
- ADA528510
Entities
People
- C. S. Gunturk
- Ingrid Daubechies
- Massimo Fornasier
- Ronald DeVore
Organizations
- Princeton University