A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation

We propose a fast algorithm for solving the ₁-regularized minimization problem minxⁿμ\|x\|₁+\|Ax-b\|²₂ for recovering sparse solutions to an undetermined system of linear equations $Ax=b$. The algorithm is divided into two stages that are performed repeatedly. In the first stage a first-order iterative “shrinkage” method yields an estimate of the subset of components of x likely to be nonzero in an optimal solution. Restricting the decision variables x to this subset and fixing their signs at their current values reduces the ₁-norm \|x\|₁ to a linear function of x. The resulting subspace problem, which involves the minimization of a smaller and smooth quadratic function, is solved in the second phase. Our code FPC_AS embeds this basic two-stage algorithm in a continuation (homotopy) approach by assigning a decreasing sequence of values to μ. This code exhibits state-of-the-art performance in terms of both its speed and its ability to recover sparse signals.