Name
Title | ||
|---|---|---|
A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/090747695 | SIAM J. Scientific Computing |
Keywords | Field | DocType |
linear function,sparse signal,sparse solution,basis pursuit,linear equation,shrinkage,sparse reconstruction,continuation,active set,smooth quadratic function,compressive sensing,subspace optimization,subspace problem,basic two-stage algorithm,regularized minimization problem,fast algorithm,code fpc_as,ℓ1-minimization,linear equations,first order,compressed sensing,iteration method | Mathematical analysis,Basis pursuit,Minification,Homotopy,Compressed sensing,Discrete mathematics,Combinatorics,Mathematical optimization,System of linear equations,Subspace topology,Algorithm,Quadratic function,Linear function,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 4 | 1064-8275 |
Citations | PageRank | References |
47 | 3.10 | 31 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zaiwen Wen | 1 | 934 | 40.20 |
| Wotao Yin | 2 | 5038 | 243.92 |
| Donald Goldfarb | 3 | 755 | 63.99 |
| Yin Zhang | 4 | 3492 | 281.04 |