×

zbMATH — the first resource for mathematics

Fast thresholding algorithms with feedbacks for sparse signal recovery. (English) Zbl 1294.65068
Summary: We provide another framework of iterative algorithms based on thresholding, feedback and null space tuning for sparse signal recovery arising in sparse representations and compressed sensing. Several thresholding algorithms with various feedbacks are derived. Convergence results are also provided. The core algorithm is shown to converge in finitely many steps under a (preconditioned) restricted isometry condition. The algorithms are seen as exceedingly effective and fast, particularly for large scale problems. Numerical studies about the effectiveness and the speed of the algorithms are also presented.

MSC:
65K10 Numerical optimization and variational techniques
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
93B52 Feedback control
Software:
PDCO; TwIST; CVX; CoSaMP
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Natarajan, B. K., Sparse approximate solutions to linear-systems, SIAM J. Comput., 24, 2, 227-234, (1995) · Zbl 0827.68054
[2] Candès, E. J., Compressive sampling, (International Congress of Mathematicians, vol. 3, (2006), European Mathematical Society Zürich), 1433-1452 · Zbl 1130.94013
[3] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509, (2006) · Zbl 1231.94017
[4] Donoho, D. L.; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell^1\) minimization, Proc. Natl. Acad. Sci. USA, 100, 5, 2197-2202, (2003) · Zbl 1064.94011
[5] Donoho, D. L.; Elad, M.; Temlyakov, V. N., Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inf. Theory, 52, 1, 6-18, (2006) · Zbl 1288.94017
[6] Donoho, D. L.; Huo, X., Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inf. Theory, 47, 7, 2845-2862, (2001) · Zbl 1019.94503
[7] Elad, M.; Bruckstein, A. M., A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Inf. Theory, 48, 9, 2558-2567, (2002) · Zbl 1062.15001
[8] Fuchs, J.-J., On sparse representations in arbitrary redundant bases, IEEE Trans. Inf. Theory, 50, 6, 1341-1344, (2004) · Zbl 1284.94018
[9] Gribonval, R.; Nielsen, M., Sparse representations in unions of bases, IEEE Trans. Inf. Theory, 49, 12, 3320-3325, (2003) · Zbl 1286.94032
[10] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159, (2001) · Zbl 0979.94010
[11] Kim, S.-J.; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., An interior-point method for large-scale \(\ell_1\)-regularized least squares, IEEE J. Sel. Top. Signal Process., 1, 4, 606-617, (2007)
[12] Mallat, S. G.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 12, 3397-3415, (1993) · Zbl 0842.94004
[13] Needell, D.; Vershynin, R., Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. Comput. Math., 9, 3, 317-334, (2009) · Zbl 1183.68739
[14] Tropp, J. A., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 10, 2231-2242, (2004) · Zbl 1288.94019
[15] Donoho, D. L.; Tsaig, Y.; Drori, I.; Starck, J.-L., Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, (2006), Stanford Univ., Tech. Rep. · Zbl 1365.94069
[16] Needell, D.; Tropp, J., Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321, (2009) · Zbl 1163.94003
[17] Dai, W.; Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inf. Theory, 55, 5, 2230-2249, (2009) · Zbl 1367.94082
[18] Bioucas-Dias, J. M.; Figueiredo, M. A.T., A new twist: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16, 12, 2992-3004, (2007)
[19] Bredies, K.; Lorenz, D. A., Iterated hard shrinkage for minimization problems with sparsity constraints, SIAM J. Sci. Comput., 30, 2, 657-683, (2008) · Zbl 1170.46067
[20] Bredies, K.; Lorenz, D. A., Linear convergence of iterative soft-thresholding, J. Fourier Anal. Appl., 14, 5-6, 813-837, (2008) · Zbl 1175.65061
[21] Candès, E. J.; Romberg, J., Signal recovery from random projections, Proc. SPIE, 5674, 76-86, (2005)
[22] Daubechies, I.; Defrise, M.; Mol, C. D., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 57, 11, 1413-1457, (2004) · Zbl 1077.65055
[23] Ehler, M., Shrinkage rules for variational minimization problems and applications to analytical ultracentrifugation, J. Inverse Ill-Posed Probl., 19, 4-5, 593-614, (2011) · Zbl 1279.65084
[24] Fornasier, M.; Rauhut, H., Iterative thresholding algorithms, Appl. Comput. Harmon. Anal., 25, 2, 187-208, (2008) · Zbl 1149.65038
[25] Fornasier, M.; Rauhut, H., Recovery algorithms for vector-valued data with joint sparsity constraints, SIAM J. Numer. Anal., 46, 2, 577-613, (2008) · Zbl 1211.65066
[26] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202, (2009) · Zbl 1175.94009
[27] Figueiredo, M. A.T.; Nowak, R. D.; Wright, S. J., Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1, 4, 586-597, (2007)
[28] Wright, S. J.; Nowak, R. D.; Figueiredo, M. A.T., Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 7, 2479-2493, (2009) · Zbl 1391.94442
[29] Cai, J.-F.; Osher, S.; Shen, Z., Linearized Bregman iterations for compressed sensing, Math. Comput., 78, 1, 1515-1536, (2009) · Zbl 1198.65102
[30] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for \(\ell_1\)-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 1, 143-168, (2008) · Zbl 1203.90153
[31] Blumensath, T.; Davies, M. E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654, (2008) · Zbl 1175.94060
[32] Lange, K., Optimization, (2004), Springer · Zbl 1140.90004
[33] Maleki, A.; Donoho, D. L., Optimally tuned iterative reconstruction algorithms for compressed sensing, IEEE J. Sel. Top. Signal Process., 4, 4, 330-341, (2010)
[34] Foucart, S., Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 6, 2543-2563, (2011) · Zbl 1242.65060
[35] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274, (2009) · Zbl 1174.94008
[36] Björck, Å., Numerical methods for least squares problems, (1996), SIAM: Society for Industrial and Applied Mathematics · Zbl 0734.65031
[37] Horn, R. A.; Johnson, C. R., Matrix analysis, (1990), Cambridge University Press · Zbl 0704.15002
[38] Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215, (2005) · Zbl 1264.94121
[39] Rudelson, M.; Vershynin, R., Non-asymptotic theory of random matrices: extreme singular values, (Proceedings of the International Congress of Mathematicians, (2010)), 1576-1602 · Zbl 1227.60011
[40] Vershynin, R., Introduction to the non-asymptotic analysis of random matrices, (Eldar, Y. C.; Kutyniok, G., Compressed Sensing, Theory and Applications, (2012), Cambridge University Press), 210-268
[41] Foucart, S., Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants, (Approximation Theory XIII, San Antonio, (2010)), 65-77 · Zbl 1250.65057
[42] Grant, M.; Boyd, S., CVX: Matlab software for disciplined convex programming, (April 2011), version 1.21
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.