More Web Proxy on the site http://driver.im/

article

A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation

Authors:

Donald Goldfarb,

Yin ZhangAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 32, Issue 4

Pages 1832 - 1857

https://doi.org/10.1137/090747695

Published: 01 June 2010 Publication History

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.

References

[1]

S. Aybat and G. Iyengar, A first-order smoothed penalty method for compressed sensing, SIAM J. Optim., submitted.

[2]

J. Barzilai and J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), pp. 141-148.

[3]

S. Becker, J. Bobin, and E. Candès, NESTA: A Fast and Accurate First-order Method for Sparse Recovery, Technical report, California Institute of Technology, Pasadena, 2009; available online from http://arxiv.org/abs/0904.3367.

[4]

J. Bect, L. Blanc-Feraud, G. Aubert, and A. Chambolle, A $\ell_1$-unified variational framework for image restoration, in Proceedings of the European Conference on Computer Vision, Prague, Lecture Notes in Comput. Sci. 3024, Springer, Berlin, Heidelberg, 2004, pp. 1-13.

[5]

J. M. Bioucas-Dias and M. A. T. Figueiredo, A new twist: Two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16 (2007), pp. 2992-3004.

[6]

J. V. Burke and J. J. Moré, On the identification of active constraints, SIAM J. Numer. Anal., 25 (1988), pp. 1197-1211.

[7]

J. V. Burke and J. J. Moré, Exposing constraints, SIAM J. Optim., 4 (1994), pp. 573-595.

[8]

R. H. Byrd, N. I. M. Gould, J. Nocedal, and R. A. Waltz, An algorithm for nonlinear optimization using linear programming and equality constrained subproblems, Math. Program., 100 (2004), pp. 27-48.

[9]

R. H. Byrd, N. I. M. Gould, J. Nocedal, and R. A. Waltz, On the convergence of successive linear-quadratic programming algorithms, SIAM J. Optim., 16 (2005), pp. 471-489.

[10]

E. Candes and S. Becker, private communication, 2008.

[11]

E. Candès and J. Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math., 6 (2006), pp. 227-254.

[12]

E. Candès, J. Romberg, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), pp. 489-509.

[13]

E. Candès and T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies, IEEE Trans. Inform. Theory, 52 (2004), pp. 5406-5425.

[14]

P. L. Combettes and J.-C. Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim., 18 (2007), pp. 1351-1376.

[15]

P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), pp. 1168-1200.

[16]

A. R. Conn and J. W. Sinclair, Quadratic Programming via a Nondifferentiable Penalty Function, Technical report CORR 75/15, Faculty of Mathematics, University of Waterloo, Waterloo, ON, Canada, 1975.

[17]

W. Dai and M. Olgica, Subspace Pursuit for Compressive Sensing: Closing the Gap between Performance and Complexity, Technical report, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL, 2008.

[18]

Y. H. Dai, On the nonmonotone line search, J. Optim. Theory Appl., 112 (2002), pp. 315-330.

[19]

C. De Mol and M. Defrise, A note on wavelet-based inversion algorithms, in Inverse Problems, Image Analysis, and Medical Imaging, Contemp. Math. 313, AMS, Providence, RI, 2002, pp. 85-96.

[20]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201-213.

[21]

D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289-1306.

[22]

D. Donoho, I. Drori, V. Stodden, and Y. Tsaig, SparseLab, 2008, http://sparselab.stanford.edu/.

[23]

D. Donoho, Y. Tsaig, I. Drori, and J.-C. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inform. Theory, submitted.

[24]

M. Elad, Why simple shrinkage is still relevant for redundant representations?, IEEE Trans. Inform. Theory, 52 (2006), pp. 5559-5569.

[25]

M. Elad, B. Matalon, J. Shtok, and M. Zibulevsky, A wide-angle view at iterated shrinkage algorithms, in Proceedings of the SPIE (Wavelets XII), Vol. 6701, San Diego, 2007, 670102.

[26]

M. Elad, B. Matalon, and M. Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal., 23 (2006), pp. 346-367.

[27]

F. Facchinei, A. Fischer, and C. Kanzow, On the accurate identification of active constraints, SIAM J. Optim., 9 (1998), pp. 14-32.

[28]

M. Figueiredo and R. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12 (2003), pp. 906-916.

[29]

M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE J. Sel. Topics Signal Process., 1 (2007), pp. 586-598.

[30]

N. I. M. Gould and P. L. Toint, An iterative working-set method for large-scale nonconvex quadratic programming, Appl. Numer. Math., 43 (2002), pp. 109-128.

[31]

L. Grippo, F. Lampariello, and S. Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal., 23 (1986), pp. 707-716.

[32]

W. W. Hager and H. Zhang, A new active set algorithm for box constrained optimization, SIAM J. Optim., 17 (2006), pp. 526-557.

[33]

E. T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for $l\sb 1$-minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), pp. 1107-1130.

[34]

E. T. Hale, W. Yin, and Y. Zhang, A numerical study of fixed-point continuation applied to compressed sensing, J. Comput. Math., 28 (2010), pp. 170-194.

[35]

Ilog, Inc., ILOG CPLEX 10.0, 2006, http://www-01.ibm.com/software/integration/ optimization/cplex-optimizer/.

[36]

S.-J. Kim, K. Koh, M. Lustig, S. Boyd, and D. Gorinevsky, An interior-point method for large-scale l$_1$-regularized least squares, IEEE J. Sel. Topics Signal Process., 1 (2007), pp. 606-617.

[37]

S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, and R. Baraniuk, Analog-to-information conversion via random demodulation, in Proceedings of the IEEE Dallas Circuits and Systems Workshop (DCAS), Dallas, 2006.

[38]

J. Laska, S. Kirolos, M. Duarte, T. Ragheb, R. Baraniuk, and Y. Massoud, Theory and implementation of an analog-to-information converter using random demodulation, in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), New Orleans, 2007.

[39]

J. Laska, S. Kirolos, Y. Massoud, R. Baraniuk, A. Gilbert, M. Iwen, and M. Strauss, Random sampling for analog-to-information conversion of wideband signals, in Proceedings of the IEEE Dallas Circuits and Systems Workshop (DCAS), Dallas, 2006.

[40]

H. Lee, A. Battle, R. Raina, and A. Y. Ng, Efficient sparse coding algorithms, in Advances in Neural Information Processing Systems, Vol. 19, B. Schölkopf, J. Platt, and T. Hoffman, eds., MIT Press, Cambridge, MA, 2007, pp. 801-808.

[41]

M. Lustig, D. Donoho, and J. M. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magn. Reson. Med., 58 (2007), pp. 1182-1195.

[42]

S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41 (1993), pp. 3397-3415.

[43]

J. J. Moré and G. Toraldo, Algorithms for bound constrained quadratic programming problems, Numer. Math., 55 (1989), pp. 377-400.

[44]

J. J. Moré and G. Toraldo, On the solution of large quadratic programming problems with bound constraints, SIAM J. Optim., 1 (1991), pp. 93-113.

[45]

D. Needell and J. A. Tropp, Cosamp: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26 (2008), pp. 301-321.

[46]

Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Discussion Paper 2007/76, 2007, http://www.optimization-online.org.

[47]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Ser. Oper. Res., 2nd ed., Springer, New York, 2006.

[48]

R. Nowak and M. Figueiredo, Fast wavelet-based image deconvolution using the EM algorithm, in Proceedings of the 35th IEEE Asilomar Conference on Signals, Systems, and Computers, Monterey, CA, 2001, pp. 371-375.

[49]

S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci., 8 (2010), pp. 93-111.

[50]

W. Sun and Y.-X. Yuan, Optimization Theory and Methods, Nonlinear Programming, Springer Optimization and Its Applications 1, Springer, New York, 2006.

[51]

D. Takhar, J. Laska, M. Wakin, M. Duarte, D. Baron, S. Sarvotham, K. Kelly, and R. Baraniuk, A new compressive imaging camera architecture using optical-domain compression, in Proceedings of Computational Imaging IV at SPIE Electronic Imaging, San Jose, CA, 2006, pp. 43-52.

[52]

P. L. Toint, An assessment of nonmonotone linesearch techniques for unconstrained optimization, SIAM J. Sci. Comput., 17 (1996), pp. 725-739.

[53]

J. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50 (2006), pp. 2231-2342.

[54]

J. Tropp, Just relax: Convex programming methods for identifying sparse signals, IEEE Trans. Inform. Theory, 51 (2006), pp. 1030-1051.

[55]

J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk, Random filters for compressive sampling and reconstruction, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Toulouse, France, 2006, pp. 872-875.

[56]

P. Tseng and S. Yun, Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization, J. Optim. Theory Appl., 140 (2009), pp. 513-535.

[57]

P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117 (2009), pp. 387-423.

[58]

E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31 (2008), pp. 890-912.

[59]

E. van den Berg, M. P. Friedlander, G. Hennenfent, F. J. Herrmann, R. Saab, and O. Yilmaz, Algorithm $890$: Sparco: A testing framework for sparse reconstruction, ACM Trans. Math. Software, 35 (2009), pp. 1-16.

[60]

M. Wakin, J. Laska, M. Duarte, D. Baron, S. Sarvotham, D. Takhar, K. Kelly, and R. Baraniuk, An architecture for compressive imaging, in Proceedings of the IEEE International Conference on Image Processing (ICIP), Atlanta, 2006, pp. 1273-1276.

[61]

M. Wakin, J. Laska, M. Duarte, D. Baron, S. Sarvotham, D. Takhar, K. Kelly, and R. Baraniuk, Compressive imaging for video representation and coding, in Proceedings of the Picture Coding Symposium (PCS), Beijing, China, 2006.

[62]

Z. Wen, W. Yin, D. Goldfarb, and Y. Zhang, On the Convergence of an Active Set Method for $L_1$ Minimization, Technical report, Department of Industrial Engineering and Operations Research, Columbia University, New York, 2008.

[63]

S. J. Wright, R. D. Nowak, and M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Proc., 57 (2009), pp. 2479-2493.

[64]

J. Yang, Y. Zhang, and W. Yin, A fast alternating direction method for TVL$1$-L$2$ signal reconstruction from partial Fourier data, IEEE J. Sel. Top. Signal Process., 4 (2007), pp. 288-297.

[65]

W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for $\ell_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), pp. 143-168.

[66]

H. Zhang and W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14 (2004), pp. 1043-1056.

[67]

C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal, Algorithm $778$: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Software, 23 (1997), pp. 550-560.

Cited By

Tao MZhang XXia Z(2024)On Partial Smoothness, Activity Identification and Faster Algorithms of $L_{1}$ Over $L_{2}$ MinimizationIEEE Transactions on Signal Processing10.1109/TSP.2024.340425072(2874-2889)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3404250
Liu XXiao NYuan Y(2024)A Penalty-Free Infeasible Approach for a Class of Nonsmooth Optimization Problems Over the Stiefel ManifoldJournal of Scientific Computing10.1007/s10915-024-02495-499:2Online publication date: 20-Mar-2024
https://dl.acm.org/doi/10.1007/s10915-024-02495-4
Wang YShen CZhang LYang W(2023)Proximal Gradient/Semismooth Newton Methods for Projection onto a Polyhedron via the Duality-Gap-Active-Set StrategyJournal of Scientific Computing10.1007/s10915-023-02302-697:1Online publication date: 14-Aug-2023
https://dl.acm.org/doi/10.1007/s10915-023-02302-6
Show More Cited By

A Fast Algorithm for Sparse Reconstruction Based on Shrinkage, Subspace Optimization, and Continuation
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the convergence of an active-set method for ℓ1 minimization

We analyse an abridged version of the active-set algorithm FPC_AS proposed in Wen <italic>et al</italic>. [A fast algorithm for sparse reconstruction based on shrinkage, subspace optimisation and continuation, SIAM J. Sci. Comput. 32 2010, pp. 1832–1857]...
Sparse Approximate Reconstruction Decomposed by Two Optimization Problems

We propose a novel sparse signal reconstruction method aiming to directly minimize $$\ell _{0}$$ℓ0-quasinorm. Based on the smoothed $$\ell _{0}$$ℓ0-quasinorm, we show that there exists an unconstrained optimization problem such that both this problem ...
Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing

In this paper, we propose and study the use of alternating direction algorithms for several $\ell_1$-norm minimization problems arising from sparse solution recovery in compressive sensing, including the basis pursuit problem, the basis pursuit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 32, Issue 4

June 2010

752 pages

ISSN:1064-8275

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 June 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tao MZhang XXia Z(2024)On Partial Smoothness, Activity Identification and Faster Algorithms of $L_{1}$ Over $L_{2}$ MinimizationIEEE Transactions on Signal Processing10.1109/TSP.2024.340425072(2874-2889)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3404250
Liu XXiao NYuan Y(2024)A Penalty-Free Infeasible Approach for a Class of Nonsmooth Optimization Problems Over the Stiefel ManifoldJournal of Scientific Computing10.1007/s10915-024-02495-499:2Online publication date: 20-Mar-2024
https://dl.acm.org/doi/10.1007/s10915-024-02495-4
Wang YShen CZhang LYang W(2023)Proximal Gradient/Semismooth Newton Methods for Projection onto a Polyhedron via the Duality-Gap-Active-Set StrategyJournal of Scientific Computing10.1007/s10915-023-02302-697:1Online publication date: 14-Aug-2023
https://dl.acm.org/doi/10.1007/s10915-023-02302-6
Ge ZWu ZZhang XNi Q(2023)An extrapolated proximal iteratively reweighted method for nonconvex composite optimization problemsJournal of Global Optimization10.1007/s10898-023-01299-486:4(821-844)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1007/s10898-023-01299-4
Cheng WWang XChen X(2022)An Interior Stochastic Gradient Method for a Class of Non-Lipschitz Optimization ProblemsJournal of Scientific Computing10.1007/s10915-022-01897-692:2Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10915-022-01897-6
Yang MMilzarek AWen ZZhang T(2022)A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimizationMathematical Programming: Series A and B10.1007/s10107-021-01629-y194:1-2(257-303)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-021-01629-y
Babapour SLakestani MFatholahzadeh A(2021)AFISTA: Accelerated FISTA for sparse signal recovery and compressive sensingMultimedia Tools and Applications10.1007/s11042-021-10701-w80:13(20707-20731)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s11042-021-10701-w
Yu TLiu XDai YSun J(2021)Stochastic Variance Reduced Gradient Methods Using a Trust-Region-Like SchemeJournal of Scientific Computing10.1007/s10915-020-01402-x87:1Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10915-020-01402-x
Jiang SFang SJin Q(2020)Sparse Solutions by a Quadratically Constrained ℓ q (0 < q < 1) Minimization ModelINFORMS Journal on Computing10.1287/ijoc.2020.100433:2(511-530)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1287/ijoc.2020.1004
Shen CXue WZhang LWang B(2020)An Active-Set Proximal-Newton Algorithm for Regularized Optimization Problems with Box ConstraintsJournal of Scientific Computing10.1007/s10915-020-01364-085:3Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10915-020-01364-0
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents