Iteratively Re-weighted Least Squares minimization: Proof of faster than linear rate for sparse recovery

Given an mtimesN matrix Phi, with m<N, the system of equations Phix=y is typically underdetermined and has infinitely many solutions. Various forms of optimization can extract a "best" solution. One of the oldest is to select the one with minimal lscr₂ norm. It has been shown that in many applications a better choice is the minimal lscr₁ norm solution. This is the case in compressive sensing, when sparse solutions are sought. The minimal lscr₁ norm solution can be found by using linear programming; an alternative method is iterative re-weighted least squares (IRLS), which in some cases is numerically faster. The main step of IRLS finds, for a given weight w, the solution with smallest lscr₂(w) norm; this weight is updated at every iteration step: if x⁽ⁿ⁾ is the solution at step n, then w⁽ⁿ⁾ is defined by w_i ⁽ⁿ⁾:=1/|x_i ⁽ⁿ⁾|, i=1,...,N. We give a specific recipe for updating weights that avoids technical shortcomings in other approaches, and for which we can prove convergence under certain conditions on the matrix Phi known as the restricted isometry property. We also show that if there is a sparse solution, then the limit of the proposed algorithm is that sparse solution. It is also shown that whenever the solution at a given iteration is sufficiently close to the limit, then the remaining steps of the algorithm converge exponentially fast. In the standard version of the algorithm, designed to emulate lscr₁-minimization, the exponential rate is linear; in adapted versions aimed at lscr_tau-minimization with tau<1, we prove faster than linear rate.