An adaptive inverse scale space method for compressed sensing. (English) Zbl 1260.49053
Summary: In this paper we introduce a novel adaptive approach for solving \(\ell^1\)-minimization problems as frequently arising in compressed sensing, which is based on the recently introduced inverse scale space method. The scheme allows to efficiently compute minimizers by solving a sequence of low-dimensional nonnegative least-squares problems. We provide a detailed convergence analysis in a general setup as well as refined results under special conditions. In addition, we discuss experimental observations in several numerical examples.
MSC:
| 49M29 | Numerical methods involving duality |
| 90C25 | Convex programming |
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
Software:
CoSaMPReferences:
| [1] | [benning] M. Benning, T. K\`“osters, F. W\'”ubbeling, K. Sch\"afers, and M. Burger, A nonlinear variational method for improved quantification of myocardial blood flow using dynamic H215O PET, IEEE Nuclear Science Symposium Conference Record, 2008, pp. 4472-4477. |
| [2] | [blumensath] T. Blumensath and M. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmonic Anal. 27 (2009), 265-274. · Zbl 1174.94008 |
| [3] | [burgersparse] M. Burger, A note on sparse reconstruction methods, J. Phys. Conference Series, no. 012002, 2008. |
| [4] | [frick] M. Burger, K. Frick, S. Osher, and O. Scherzer, Inverse total variation flow, SIAM Multiscale Modelling and Simulation 6 (2007), 366-395. · Zbl 1147.49026 |
| [5] | [gilboa] M. Burger, G. Gilboa, S. Osher, and J. Xu, Nonlinear inverse scale space methods, Comm. Math. Sci. 4 (2006), 179-212. · Zbl 1106.68117 |
| [6] | [tvzoo1] M. Burger and S. Osher, A guide to TV zoo, preprint. · Zbl 1342.94014 |
| [7] | [BRH07] M. Burger, E. Resmerita, and L. He, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Computing 81 (2007), 109-135. · Zbl 1147.68790 |
| [8] | [cai2] J. Cai, S. Osher, and Z. Shen, Convergence of the linearized Bregman iteration for \(\ell_1\)-norm minimization, Math. Comp. 78 (2009), 2127-2136. · Zbl 1198.65103 |
| [9] | [cai1] \bysame, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), 1515-1536. · Zbl 1198.65102 |
| [10] | [candestao1] E. J. Candes and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2004), 4203-4215. · Zbl 1264.94121 |
| [11] | [candestao2] \bysame, Near-optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inform. Theory 52 (2004), 5406-5425. · Zbl 1309.94033 |
| [12] | [dahmen1] A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet schemes for elliptic operator equations-convergence rates, Math. Comp. 70 (2001), 27-75. · Zbl 0980.65130 |
| [13] | [dahmen2] \bysame, Adaptive wavelet methods II-beyond the elliptic case, Found. Comput. Math. 2 (2002), 203-245. · Zbl 1025.65056 |
| [14] | [dahmen3] S. Dahlke, W. Dahmen, and K. Urban, Adaptive wavelet methods for saddle point problems-optimal convergence rates, SIAM J. Numer. Anal. 40 (2002), 1230-1262. · Zbl 1024.65101 |
| [15] | [daubechies] I. Daubechies, M. Defrise, and C. DeMol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math. 57 (2004), 1413-1457. · Zbl 1077.65055 |
| [16] | [donoho2] D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), 1289-1306. · Zbl 1288.94016 |
| [17] | [donoho1] D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell^1\) minimization, Proc. Natl. Acad. Sci. USA 100 (2003), 2197-2202. · Zbl 1064.94011 |
| [18] | [donohotsaig] D. L. Donoho, Y. Tsaig, I. Drori, and J. L. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit (stomp), Tech. report, Stanford Univ., 2006, Stat. Dept. Tech. Rep. 2006-02. · Zbl 1365.94069 |
| [19] | [ekelandtemam] I. Ekeland and R. Temam, Convex analysis and variational problems, corrected reprint edition ed., SIAM, Philadelphia, 1999. · Zbl 0939.49002 |
| [20] | [mallat93] S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing 12 (1993), 3397-3415. · Zbl 0842.94004 |
| [21] | [meyer] Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations: The fifteenth Dean Jacqueline B. Lewis memorial lectures, American Mathematical Society, 2001. · Zbl 0987.35003 |
| [22] | [cosamp] D. Needell and J. A. Tropp, Cosamp: Iterative signal recovery from incomplete and inaccurate samples, Applied and Computational Harmonic Analysis 26 (2009), 301-321. · Zbl 1163.94003 |
| [23] | [NTV08] D. Needell, J. A. Tropp, and R. Vershynin, Greedy signal recovery review, Proc. 42nd Asilomar Conf. Signals, Systems and Computers, 2008. |
| [24] | [needell1] D. Needell and R. Vershynin, Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, IEEE J. Sel. Topics Signal Process 4 (2009), 310-316. · Zbl 1183.68739 |
| [25] | [osh-bur-gol-xu-yin] S. Osher, M. Burger, D. Goldfarb, and J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, SIAM Multiscale Model. Simul. 4 (2005), 460-489. · Zbl 1090.94003 |
| [26] | [kicking] S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), 93-111. · Zbl 1190.49040 |
| [27] | [pati] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, 1993, pp. 40-44. |
| [28] | [reader] A. J. Reader, J. C. Matthews, F. C. Sureau, C. Comtat, R. Tr\'ebossen, and I. Buvat, Fully 4D image reconstruction by estimation of an input function and spectral coefficients, IEEE Nuclear Science Symposium Conference Record, 2007, pp. 3260-3267. |
| [29] | [Tropp] J. A. Tropp, Just relax: Convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), 1030-1051. · Zbl 1288.94025 |
| [30] | [TroppGilbert] J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory 53 (2007), 4655-4666. · Zbl 1288.94022 |
| [31] | [suppdet] Y. Wang and W. Yin, Sparse signal reconstruction via iterative support detection, SIAM J. Imaging Sci. 3 (2010), 462-491. · Zbl 1206.68340 |
| [32] | [yin2] W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM J. Imaging Sciences 3 (2010), no. 4, pp. 856-877. · Zbl 1211.68491 |
| [33] | [yin] 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), 143-168. · Zbl 1203.90153 |
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.
