A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation. (English) Zbl 1215.49039

Summary: We propose a fast algorithm for solving the \(\ell_1\)-regularized minimization problem \(\min_{x\in \mathbb{R}^n}\mu \|x\|_1+\|Ax-b\|^2_2\) 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 \(\ell_1\)-norm \(\|x\|_1\) 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 \(\mu\). This code exhibits state-of-the-art performance in terms of both its speed and its ability to recover sparse signals.


49M30 Other numerical methods in calculus of variations (MSC2010)
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C06 Large-scale problems in mathematical programming
Full Text: DOI Link