Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Invitation to Compressive Sensing Read chapter Read first chapter

2013 | OriginalPaper | Chapter

15. Algorithms for ℓ1-Minimization

Authors : Simon Foucart, Holger Rauhut

Published in: A Mathematical Introduction to Compressive Sensing

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter presents a selection of three algorithms designed specifically to compute solutions of ℓ 1-minimization problems. The algorithms, chosen with simplicity of analysis and diversity of techniques in mind, are the homotopy method, Chambolle and Pock’s primal–dual algorithm, and the iteratively reweighted least squares algorithm. Other algorithms are also mentioned but discussed in less detail.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Recovery of Random Signals using Deterministic Matrices
Literature
4.
M. Afonso, J. Bioucas Dias, M. Figueiredo, Fast image recovery using variable splitting and constrained optimization. IEEE Trans. Image Process. 19(9), 2345–2356 (2010)MathSciNetCrossRef
20.
K. Arrow, L. Hurwicz, H. Uzawa, Studies in Linear and Non-linear Programming (Stanford University Press, Stanford, California, 1958)MATH
32.
S. Bartels, Total variation minimization with finite elements: convergence and iterative solution. SIAM J. Numer. Anal. 50(3), 1162–1180 (2012)MathSciNetMATHCrossRef
34.
H. Bauschke, P. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC (Springer, New York, 2011)
36.
A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183–202 (2009)MathSciNetMATHCrossRef
37.
A. Beck, M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. 18(11), 2419–2434 (2009)MathSciNetCrossRef
38.
S. Becker, J. Bobin, E.J. Candès, NESTA: A fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4(1), 1–39 (2011)MathSciNetMATHCrossRef
44.
D. Bertsekas, J. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods (Athena Scientific, Cambridge, MA, 1997)
49.
E. Birgin, J. Martínez, M. Raydan, Inexact spectral projected gradient methods on convex sets. IMA J. Numer. Anal. 23(4), 539–559 (2003)MathSciNetMATHCrossRef
70.
S. Boyd, L. Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004)MATHCrossRef
71.
79.
M. Burger, M. Moeller, M. Benning, S. Osher, An adaptive inverse scale space method for compressed sensing. Math. Comp. 82(281), 269–299 (2013)MathSciNetMATHCrossRef
107.
A. Chambolle, T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imag. Vis. 40, 120–145 (2011)MathSciNetMATHCrossRef
109.
R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 14(10), 707–710 (2007)CrossRef
110.
R. Chartrand, V. Staneva, Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24(3), 1–14 (2008)MathSciNetCrossRef
111.
R. Chartrand, W. Yin, Iteratively reweighted algorithms for compressive sensing. In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, Las Vegas, Nevada, USA, pp. 3869–3872, 2008
112.
121.
127.
P. Combettes, J.-C. Pesquet, A Douglas-Rachford Splitting Approach to Nonsmooth Convex Variational Signal Recovery. IEEE J. Sel. Top. Signal Process. 1(4), 564–574 (2007)CrossRef
128.
P. Combettes, J.-C. Pesquet, Proximal splitting methods in signal processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, ed. by H. Bauschke, R. Burachik, P. Combettes, V. Elser, D. Luke, H. Wolkowicz (Springer, New York, 2011), pp. 185–212
129.
P. Combettes, V. Wajs, Signal recovery by proximal forward-backward splitting. Multiscale Model. Sim. 4(4), 1168–1200 (electronic) (2005)
138.
I. Daubechies, M. Defrise, C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm. Pure Appl. Math. 57(11), 1413–1457 (2004)MathSciNetMATHCrossRef
139.
I. Daubechies, R. DeVore, M. Fornasier, C. Güntürk, Iteratively re-weighted least squares minimization for sparse recovery. Comm. Pure Appl. Math. 63(1), 1–38 (2010)MathSciNetMATHCrossRef
140.
I. Daubechies, M. Fornasier, I. Loris, Accelerated projected gradient methods for linear inverse problems with sparsity constraints. J. Fourier Anal. Appl. 14(5–6), 764–792 (2008)MathSciNetMATHCrossRef
169.
D.L. Donoho, Y. Tsaig, Fast solution of l1-norm minimization problems when the solution may be sparse. IEEE Trans. Inform. Theor. 54(11), 4789–4812 (2008)MathSciNetMATHCrossRef
172.
J. Douglas, H. Rachford, On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)MathSciNetMATHCrossRef
177.
186.
H.W. Engl, M. Hanke, A. Neubauer, Regularization of Inverse Problems (Springer, New York, 1996)MATHCrossRef
188.
E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman. Preprint (2009)
196.
M.A. Figueiredo, R.D. Nowak, An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12(8), 906–916 (2003)MathSciNetCrossRef
197.
M.A. Figueiredo, R.D. Nowak, S. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Proces. 1(4), 586–598 (2007)CrossRef
201.
M. Fornasier, Numerical methods for sparse recovery. In Theoretical Foundations and Numerical Methods for Sparse Recovery, ed. by M. Fornasier. Radon Series on Computational and Applied Mathematics, vol. 9 (de Gruyter, Berlin, 2010), pp. 93–200
202.
203.
M. Fornasier, H. Rauhut, Recovery algorithms for vector valued data with joint sparsity constraints. SIAM J. Numer. Anal. 46(2), 577–613 (2008)MathSciNetMATHCrossRef
205.
M. Fornasier, H. Rauhut, R. Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM J. Optim. 21(4), 1614–1640 (2011)MathSciNetMATHCrossRef
216.
D. Gabay, Applications of the method of multipliers to variational inequalities. In Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, ed. by M. Fortin, R. Glowinski (North-Holland, Amsterdam, 1983), pp. 299–331CrossRef
217.
D. Gabay, B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite elements approximations. Comput. Math. Appl. 2, 17–40 (1976)MATHCrossRef
226.
R. Glowinski, T. Le, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics (SIAM, Philadelphia, 1989)MATHCrossRef
229.
D. Goldfarb, S. Ma, Convergence of fixed point continuation algorithms for matrix rank minimization. Found. Comput. Math. 11(2), 183–210 (2011)MathSciNetMATHCrossRef
230.
256.
E. Hale, W. Yin, Y. Zhang, Fixed-point continuation for ℓ 1-minimization: methodology and convergence. SIAM J. Optim. 19(3), 1107–1130 (2008)MathSciNetMATHCrossRef
257.
E. Hale, W. Yin, Y. Zhang, Fixed-point continuation applied to compressed sensing: implementation and numerical experiments. J. Comput. Math. 28(2), 170–194 (2010)MathSciNetMATH
264.
B. He, X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imag. Sci. 5(1), 119–149 (2012)MathSciNetMATHCrossRef
302.
S. Kim, K. Koh, M. Lustig, S. Boyd, D. Gorinevsky, A method for large-scale l1-regularized least squares problems with applications in signal processing and statistics. IEEE J. Sel. Top. Signal Proces. 4(1), 606–617 (2007)CrossRef
303.
J. King, A minimal error conjugate gradient method for ill-posed problems. J. Optim. Theor. Appl. 60(2), 297–304 (1989)MATHCrossRef
318.
C. Lawson, Contributions to the Theory of Linear Least Maximum Approximation. PhD thesis, University of California, Los Angeles, 1961
323.
J. Lee, Y. Sun, M. Saunders, Proximal Newton-type methods for convex optimization. Preprint (2012)
324.
B. Lemaire, The proximal algorithm. In New Methods in Optimization and Their Industrial Uses (Pau/Paris, 1987), Internationale Schriftenreihe Numerischen Mathematik, vol. 87 (Birkhäuser, Basel, 1989), pp. 73–87
328.
334.
D. Lorenz, M. Pfetsch, A. Tillmann, Solving Basis Pursuit: Heuristic optimality check and solver comparison. Preprint (2011)
335.
I. Loris, L1Packv2: a Mathematica package in minimizing an ℓ 1-penalized functional. Comput. Phys. Comm. 179(12), 895–902 (2008)MathSciNetMATHCrossRef
345.
B. Martinet, Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4(Ser. R-3), 154–158 (1970)
365.
A. Nemirovsky, D. Yudin, Problem Complexity and Method Efficiency in Optimization. A Wiley-Interscience Publication. (Wiley, New York, 1983)
366.
Y. Nesterov, A method for solving the convex programming problem with convergence rate O(1 ∕ k 2). Dokl. Akad. Nauk SSSR 269(3), 543–547 (1983)MathSciNet
367.
Y. Nesterov, Smooth minimization of non-smooth functions. Math. Program. 103(1, Ser. A), 127–152 (2005)
369.
J. Nocedal, S. Wright, Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering (Springer, New York, 2006)
375.
M. Osborne, Finite Algorithms in Optimization and Data Analysis (Wiley, New York, 1985)MATH
376.
M. Osborne, B. Presnell, B. Turlach, A new approach to variable selection in least squares problems. IMA J. Numer. Anal. 20(3), 389–403 (2000)MathSciNetMATHCrossRef
377.
M. Osborne, B. Presnell, B. Turlach, On the LASSO and its dual. J. Comput. Graph. Stat. 9(2), 319–337 (2000)MathSciNet
395.
T. Pock, A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In IEEE International Conference Computer Vision (ICCV) 2011, pp. 1762 –1769, November 2011
396.
T. Pock, D. Cremers, H. Bischof, A. Chambolle, An algorithm for minimizing the Mumford-Shah functional. In ICCV Proceedings (Springer, Berlin, 2009)
405.
H. Raguet, J. Fadili, G. Peyré, A generalized forward-backward splitting. Preprint (2011)
423.
446.
S. Setzer, Operator splittings, Bregman methods and frame shrinkage in image processing. Int. J. Comput. Vis. 92(3), 265–280 (2011)MathSciNetMATHCrossRef
451.
J.-L. Starck, F. Murtagh, J. Fadili, Sparse Image and Signal Processing: Wavelets, Curvelets, Morphological Diversity (Cambridge University Press, Cambridge, 2010)CrossRef
493.
E. van den Berg, M. Friedlander, Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890–912 (2008)MathSciNetMATHCrossRef
511.
S. Worm, Iteratively re-weighted least squares for compressed sensing. Diploma thesis, University of Bonn, 2011
516.
X. Zhang, M. Burger, X. Bresson, S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM J. Imag. Sci. 3(3), 253–276 (2010)MathSciNetMATHCrossRef
517.
X. Zhang, M. Burger, S. Osher, A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46, 20–46 (2011)MathSciNetMATHCrossRef
518.
M. Zhu, T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration. Technical report, CAM Report 08–34, UCLA, Los Angeles, CA, 2008
Metadata
Title
Algorithms for ℓ1-Minimization
Authors
Simon Foucart
Holger Rauhut
Copyright Year
2013
Publisher
Springer New York
Book
A Mathematical Introduction to Compressive Sensing

Print ISBN: 978-0-8176-4947-0

Electronic ISBN: 978-0-8176-4948-7

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-0-8176-4948-7_15

Premium Partner

    Image Credits