FPC_AS

FPC_AS (fixed-point continuation and active set) is a MATLAB solver for the l1-regularized least squares problem: A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation. We propose a fast algorithm for solving the ℓ 1 -regularized minimization problem min x∈ℝ n μ∥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 ℓ 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 μ. This code exhibits state-of-the-art performance in terms of both its speed and its ability to recover sparse signals


References in zbMATH (referenced in 57 articles , 1 standard article )

Showing results 41 to 57 of 57.
Sorted by year (citations)
  1. Wang, Zhaoran; Liu, Han; Zhang, Tong: Optimal computational and statistical rates of convergence for sparse nonconvex learning problems (2014)
  2. Xiao, Yunhai; Wu, Soon-Yi; Qi, Liqun: Nonmonotone Barzilai-Borwein gradient algorithm for (\ell_1)-regularized nonsmooth minimization in compressive sensing (2014)
  3. Gu, Ming; Lim, Lek-Heng; Wu, Cinna Julie: ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals (2013)
  4. Setzer, Simon; Steidl, Gabriele; Morgenthaler, Jan: A cyclic projected gradient method (2013)
  5. Xiao, Lin; Zhang, Tong: A proximal-gradient homotopy method for the sparse least-squares problem (2013)
  6. Aybat, N. S.; Iyengar, G.: A first-order augmented Lagrangian method for compressed sensing (2012)
  7. Wen, Zaiwen; Yin, Wotao; Zhang, Hongchao; Goldfarb, Donald: On the convergence of an active-set method for (\ell_1) minimization (2012)
  8. Wu, Lei; Sun, Zhe: New nonsmooth equations-based algorithms for (\ell_1)-norm minimization and applications (2012)
  9. Aybat, N. S.; Iyengar, G.: A first-order smoothed penalty method for compressed sensing (2011)
  10. Becker, Stephen; Bobin, Jérôme; Candès, Emmanuel J.: NESTA: A fast and accurate first-order method for sparse recovery (2011)
  11. Becker, Stephen R.; Candès, Emmanuel J.; Grant, Michael C.: Templates for convex cone problems with applications to sparse signal recovery (2011)
  12. Ma, Shiqian; Goldfarb, Donald; Chen, Lifeng: Fixed point and Bregman iterative methods for matrix rank minimization (2011)
  13. Rinaldi, F.: Concave programming for finding sparse solutions to problems with convex constraints (2011)
  14. Hale, Elaine T.; Yin, Wotao; Zhang, Yin: Fixed-point continuation applied to compressed sensing: Implementation and numerical experiments (2010)
  15. Wang, Yilun; Yin, Wotao: Sparse signal reconstruction via iterative support detection (2010)
  16. Wen, Zaiwen; Yin, Wotao; Goldfarb, Donald; Zhang, Yin: A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation (2010)
  17. Yin, Wotao: Analysis and generalizations of the linearized Bregman method (2010)