Multilevel preconditioning and adaptive sparse solution of inverse problems. (English) Zbl 1239.65037
The authors study the efficient numerical solution of minimization problems in Hilbert spaces involving sparsity constraints by employing functional analytic techniques as well as the iterative soft-shrinkage algorithm. Applying these methods, a numerical scheme is analyzed that guarantees to converge with exponential rate and which allows for a controlled inflation of the support size of the iterations.
The paper concludes with some interesting numerical experiments which outline: i) Local well-conditioning, ii) Recovery of sparse solutions, iii) Choice of the regularization parameter, iv) Linear convergence to the minimize, v) Support dynamics, vi) Dynamics, vi) Adaptivity
The reader can find several references (both old and new) which make the presentation valuable.
The paper concludes with some interesting numerical experiments which outline: i) Local well-conditioning, ii) Recovery of sparse solutions, iii) Choice of the regularization parameter, iv) Linear convergence to the minimize, v) Support dynamics, vi) Dynamics, vi) Adaptivity
The reader can find several references (both old and new) which make the presentation valuable.
Reviewer: John T. Coletsos (Athens)
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 65T60 | Numerical methods for wavelets |
| 49J27 | Existence theories for problems in abstract spaces |
| 65J10 | Numerical solutions to equations with linear operators |
| 65J20 | Numerical solutions of ill-posed problems in abstract spaces; regularization |
Keywords:
adaptive sparse solution; inverse problems; efficient numerical solution; Hilbert spaces; bounded linear operator; quasi-Banach space; iterative soft-shrinkage algorithm; numerical experiments; regularization; convergenceReferences:
| [1] | Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183 – 202. · Zbl 1175.94009 · doi:10.1137/080716542 |
| [2] | T. Bonesky, S. Dahlke, P. Maass, and T. Raasch, Adaptive wavelet methods and sparsity reconstruction for inverse heat conduction problems, Adv. Comput. Math. 33 (2010), no. 4, 385-411. · Zbl 1207.65114 |
| [3] | Kristian Bredies and Dirk A. Lorenz, Linear convergence of iterative soft-thresholding, J. Fourier Anal. Appl. 14 (2008), no. 5-6, 813 – 837. · Zbl 1175.65061 · doi:10.1007/s00041-008-9041-1 |
| [4] | Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203 – 4215. · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979 |
| [5] | Emmanuel J. Candes and Terence Tao, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406 – 5425. · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507 |
| [6] | Albert Cohen, Numerical analysis of wavelet methods, Studies in Mathematics and its Applications, vol. 32, North-Holland Publishing Co., Amsterdam, 2003. · Zbl 1038.65151 |
| [7] | Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp. 70 (2001), no. 233, 27 – 75. · Zbl 0980.65130 |
| [8] | A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet methods. II. Beyond the elliptic case, Found. Comput. Math. 2 (2002), no. 3, 203 – 245. · Zbl 1025.65056 · doi:10.1007/s102080010027 |
| [9] | Patrick L. Combettes and Valérie R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168 – 1200. · Zbl 1179.94031 · doi:10.1137/050626090 |
| [10] | Stephan Dahlke, Massimo Fornasier, and Thorsten Raasch, Adaptive frame methods for elliptic operator equations, Adv. Comput. Math. 27 (2007), no. 1, 27 – 63. · Zbl 1122.65103 · doi:10.1007/s10444-005-7501-6 |
| [11] | -, Multilevel preconditioning for adaptive sparse optimization, Preprint 25, DFG-SPP 1324, August 2009. |
| [12] | Stephan Dahlke, Thorsten Raasch, Manuel Werner, Massimo Fornasier, and Rob Stevenson, Adaptive frame methods for elliptic operator equations: the steepest descent approach, IMA J. Numer. Anal. 27 (2007), no. 4, 717 – 740. · Zbl 1153.65050 · doi:10.1093/imanum/drl035 |
| [13] | Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55 – 228. · Zbl 0884.65106 · doi:10.1017/S0962492900002713 |
| [14] | Wolfgang Dahmen and Angela Kunoth, Multilevel preconditioning, Numer. Math. 63 (1992), no. 3, 315 – 344. · Zbl 0757.65031 · doi:10.1007/BF01385864 |
| [15] | W. Dahmen, S. Prössdorf, and R. Schneider, Wavelet approximation methods for pseudodifferential equations. II. Matrix compression and fast solution, Adv. Comput. Math. 1 (1993), no. 3-4, 259 – 335. · Zbl 0826.65093 · doi:10.1007/BF02072014 |
| [16] | Wolfgang Dahmen, Siegfried Prössdorf, and Reinhold Schneider, Multiscale methods for pseudo-differential equations on smooth closed manifolds, Wavelets: theory, algorithms, and applications (Taormina, 1993) Wavelet Anal. Appl., vol. 5, Academic Press, San Diego, CA, 1994, pp. 385 – 424. · Zbl 0847.65081 · doi:10.1016/B978-0-08-052084-1.50023-5 |
| [17] | Ingrid Daubechies, Michel Defrise, and Christine De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413 – 1457. · Zbl 1077.65055 · doi:10.1002/cpa.20042 |
| [18] | Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51 – 150. · Zbl 0931.65007 · doi:10.1017/S0962492900002816 |
| [19] | Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani, Least angle regression, Ann. Statist. 32 (2004), no. 2, 407 – 499. With discussion, and a rejoinder by the authors. · Zbl 1091.62054 · doi:10.1214/009053604000000067 |
| [20] | Heinz W. Engl, Martin Hanke, and Andreas Neubauer, Regularization of inverse problems, Mathematics and its Applications, vol. 375, Kluwer Academic Publishers Group, Dordrecht, 1996. · Zbl 0859.65054 |
| [21] | Stephen J. Wright, Robert D. Nowak, and Mário A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process. 57 (2009), no. 7, 2479 – 2493. · Zbl 1391.94442 · doi:10.1109/TSP.2009.2016892 |
| [22] | Mário A. T. Figueiredo and Robert D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process. 12 (2003), no. 8, 906 – 916. · Zbl 1279.94015 · doi:10.1109/TIP.2003.814255 |
| [23] | Massimo Fornasier and Francesca Pitolli, Adaptive iterative thresholding algorithms for magnetoencephalography (MEG), J. Comput. Appl. Math. 221 (2008), no. 2, 386 – 395. · Zbl 1146.92022 · doi:10.1016/j.cam.2007.10.048 |
| [24] | Tsogtgerel Gantumur, Helmut Harbrecht, and Rob Stevenson, An optimal adaptive wavelet method without coarsening of the iterands, Math. Comp. 76 (2007), no. 258, 615 – 629. · Zbl 1115.41023 |
| [25] | G. H. Golub and C. F. van Loan, Matrix Computations, John Hopkins University Press, 1989. · Zbl 0733.65016 |
| [26] | Markus Grasmair, Markus Haltmeier, and Otmar Scherzer, Sparse regularization with \?^{\?} penalty term, Inverse Problems 24 (2008), no. 5, 055020, 13. · Zbl 1157.65033 · doi:10.1088/0266-5611/24/5/055020 |
| [27] | -, Necessary and sufficient conditions for linear convergence of \( \ell_1\)-regularization, preprint (2009). |
| [28] | Tsogtgerel Gantumur, Helmut Harbrecht, and Rob Stevenson, An optimal adaptive wavelet method without coarsening of the iterands, Math. Comp. 76 (2007), no. 258, 615 – 629. · Zbl 1115.41023 |
| [29] | S. Jaffard, Propriétés des matrices ”bien localisées” près de leur diagonale et quelques applications, Ann. Inst. H. Poincaré Anal. Non Linéaire 7 (1990), no. 5, 461 – 476 (French, with English summary). · Zbl 0722.15004 |
| [30] | P.-G. Lemarié, Bases de’ondelettes sur les groupes de Lie stratifié, Bulletin de la Société Mathématique de France 117 (1989), no. 2, 213-232. |
| [31] | A. K. Louis, Inverse und schlechtgestellte Probleme, Teubner, Stuttgart, 1989. |
| [32] | M. Primbs, Stabile biorthogonale Spline-Waveletbasen auf dem Intervall, Dissertation, Universität Duisburg-Essen, 2006. · Zbl 1196.65015 |
| [33] | R. Ramlau, G. Teschke, and M. Zhariy, A compressive Landweber iteration for solving ill-posed inverse problems, Inverse Problems 24 (2008), no. 6, 065013, 26. · Zbl 1166.65024 · doi:10.1088/0266-5611/24/6/065013 |
| [34] | H. Rauhut, Compressive sensing and structured random matrices, Theoretical Foundations and Numerical Methods for Sparse Recovery , Radon Series Comp. Appl. Math., deGruyter, 2010. · Zbl 1208.15027 |
| [35] | Reinhold Schneider, Multiskalen- und Wavelet-Matrixkompression, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1998 (German, with German summary). Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme. [Analysis-based methods for the efficient solution of large nonsparse systems of equations]. · Zbl 0899.65063 |
| [36] | J.-L. Starck, E. J. Candès, and D. L. Donoho, Astronomical image representation by curvelet transform, Astronomy and Astrophysics 298 (2003), 785-800. |
| [37] | J.-L. Starck, M. K. Nguyen, and F. Murtagh, Wavelets and curvelets for image deconvolution: a combined approach, Signal Proc. 83 (2003), 2279-2283. · Zbl 1145.94329 |
| [38] | Rob Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41 (2003), no. 3, 1074 – 1100. · Zbl 1057.41010 · doi:10.1137/S0036142902407988 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
