Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
An Invitation to Compressive Sensing Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

15. Algorithms for ℓ1-Minimization

verfasst von : Simon Foucart, Holger Rauhut

Erschienen in: A Mathematical Introduction to Compressive Sensing

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Recovery of Random Signals using Deterministic Matrices
Literatur
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.
P.-L. Lions, B. Mercier, Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)MathSciNetMATHCrossRef
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
Metadaten
Titel
Algorithms for ℓ1-Minimization
verfasst von
Simon Foucart
Holger Rauhut
Copyright-Jahr
2013
Verlag
Springer New York
Buch
A Mathematical Introduction to Compressive Sensing

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

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

Copyright-Jahr: 2013

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

Premium Partner

    Bildnachweise