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 31 articles , 1 standard article )

Showing results 1 to 20 of 31.
Sorted by year (citations)

1 2 next

  1. Byrd, Richard H.; Chin, Gillian M.; Nocedal, Jorge; Oztoprak, Figen: A family of second-order methods for convex $\ell _1$-regularized optimization (2016)
  2. De Santis, Marianna; Lucidi, Stefano; Rinaldi, Francesco: A fast active set block coordinate descent algorithm for $\ell_1$-regularized least squares (2016)
  3. Hager, William W.; Zhang, Hongchao: An active set algorithm for nonlinear optimization with polyhedral constraints (2016)
  4. Treister, Eran; Turek, Javier S.; Yavneh, Irad: A multilevel framework for sparse optimization with application to inverse covariance estimation and logistic regression (2016)
  5. Huang, Yakui; Liu, Hongwei: A Barzilai-Borwein type method for minimizing composite functions (2015)
  6. Lin, Qihang; Xiao, Lin: An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization (2015)
  7. Ulbrich, Michael; Wen, Zaiwen; Yang, Chao; Klöckner, Dennis; Lu, Zhaosong: A proximal gradient method for ensemble density functional theory (2015)
  8. Zhao, ZhiHua; Xu, FengMin; Li, XiangYang: Adaptive projected gradient thresholding methods for constrained $l_0$ problems (2015)
  9. Aybat, N.S.; Iyengar, G.: A unified approach for minimizing composite norms (2014)
  10. Cao, Shuhan; Xiao, Yunhai; Zhu, Hong: Linearized alternating directions method for $\ell_1$-norm inequality constrained $\ell_1$-norm minimization (2014)
  11. Fountoulakis, Kimon; Gondzio, Jacek; Zhlobich, Pavel: Matrix-free interior point method for compressed sensing problems (2014)
  12. Lee, Jason D.; Sun, Yuekai; Saunders, Michael A.: Proximal Newton-type methods for minimizing composite functions (2014)
  13. Li, Yingying; Osher, Stanley; Tsai, Richard: Heat source identification based on $\ell_1$ constrained minimization (2014)
  14. Porcelli, Margherita; Rinaldi, Francesco: A variable fixing version of the two-block nonlinear constrained Gauss-Seidel algorithm for $\ell_1$-regularized least-squares (2014)
  15. Wang, Zhaoran; Liu, Han; Zhang, Tong: Optimal computational and statistical rates of convergence for sparse nonconvex learning problems (2014)
  16. Xiao, Yunhai; Wu, Soon-Yi; Qi, Liqun: Nonmonotone Barzilai-Borwein gradient algorithm for $\ell_1$-regularized nonsmooth minimization in compressive sensing (2014)
  17. Gu, Ming; Lim, Lek-Heng; Wu, Cinna Julie: ParNes: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals (2013)
  18. Setzer, Simon; Steidl, Gabriele; Morgenthaler, Jan: A cyclic projected gradient method (2013)
  19. Xiao, Lin; Zhang, Tong: A proximal-gradient homotopy method for the sparse least-squares problem (2013)
  20. Aybat, N.S.; Iyengar, G.: A first-order augmented Lagrangian method for compressed sensing (2012)

1 2 next