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

Wen, Zaiwen; Yin, Wotao; Goldfarb, Donald; Zhang, Yin

SIAM J. Sci. Comput. 32, No. 4, 1832-1857 (2010).

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.

MSC:

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

Keywords:

\(\ell_1\)-minimization; basis pursuit; compressive sensing; subspace optimization; active set; continuation; shrinkage

Software:

L-BFGS; QPA; L-BFGS-B; FPC_AS; Sparco; RecPF; NESTA