Iteratively Re-weighted Least Squares Minimization for Sparse Recovery
PRINCETON UNIV NJ PROGRAM IN APPLIED AND COMPUTATIONAL MATHEMATICS
Pagination or Media Count:
Under certain conditions known as the Restricted Isometry Property or RIP on the m x N matrix where m N, vectors x included in Rsup N that are sparse i.e. have most of their entries equal to zero can be recovered exactly from y Phi-x even though Phiinversey is typically an N - m- dimensional hyperplane in addition x is then equal to the element in Phiinversey 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 Phiinversey with smallest L2w-norm. If xn is the solution at iteration step n then the new weight wn is defined by win magnitude-xinexp 2 epsilonnexp2exp -12 i 1, . . . ,N, for a decreasing sequence of adaptively defined epsilon-n this updated weight is then used to obtain xn1 and the process is repeated. We prove that when satisfies the RIP conditions, the sequence xn converges for all y, regardless of whether Phiinversey contains a sparse vector. If there is a sparse vector in Phiinversey, then the limit is this sparse vector, and when xn 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-xinexp -1 lambda2 epsilonnexp2exp -12 , 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.
- Numerical Mathematics
- Computer Programming and Software