Generalizing CoSaMP to signals from a union of low dimensional linear subspaces. (English) Zbl 1436.94019

Summary: The idea that signals reside in a union of low dimensional subspaces subsumes many low dimensional models that have been used extensively in the recent decade in many fields and applications. Until recently, the vast majority of works have studied each one of these models on its own. However, a recent approach suggests providing general theory for low dimensional models using their Gaussian mean width, which serves as a measure for the intrinsic low dimensionality of the data. In this work we use this novel approach to study a generalized version of the popular compressive sampling matching pursuit (CoSaMP) algorithm, and to provide general recovery guarantees for signals from a union of low dimensional linear subspaces, under the assumption that the measurement matrix is Gaussian. We discuss the implications of our results for specific models, and use the generalized algorithm as an inspiration for a new greedy method for signal reconstruction in a combined sparse-synthesis and cosparse-analysis model. We perform experiments that demonstrate the usefulness of the proposed strategy.


94A12 Signal theory (characterization, reconstruction, filtering, etc.)


Full Text: DOI arXiv


[1] Bruckstein, A. M.; Donoho, D. L.; Elad, M., From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 1, 34-81 (2009) · Zbl 1178.68619
[2] Nam, S.; Davies, M. E.; Elad, M.; Gribonval, R., The cosparse analysis model and algorithms, Appl. Comput. Harmon. Anal., 34, 1, 30-56 (2013) · Zbl 1261.94018
[3] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[4] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[5] Baraniuk, R. G.; Wakin, M. B., Random projections of smooth manifolds, Found. Comput. Math., 9, 1, 51-77 (2009) · Zbl 1172.53005
[6] Yu, G.; Sapiro, G.; Mallat, S., Solving inverse problems with piecewise linear estimators: from Gaussian mixture models to structured sparsity, IEEE Trans. Image Process., 21, 5, 2481-2499 (2012) · Zbl 1373.94471
[7] Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (2010), Springer · Zbl 1211.94001
[8] Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge University Press
[9] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, vol. 1 (2013), Springer · Zbl 1315.94002
[10] Chandrasekaran, V.; Recht, B.; Parrilo, P. A.; Willsky, A. S., The convex geometry of linear inverse problems, Found. Comput. Math., 12, 6, 805-849 (2012) · Zbl 1280.52008
[11] Plan, Y.; Vershynin, R., Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach, IEEE Trans. Inform. Theory, 59, 1, 482-494 (2013) · Zbl 1364.94153
[12] Amelunxen, D.; Lotz, M.; McCoy, M. B.; Tropp, J. A., Living on the edge: phase transitions in convex programs with random data, Inf. Inference (2014), iau005 · Zbl 1339.90251
[13] Candès, E. J.; Wakin, M. B., An introduction to compressive sampling, IEEE Signal Process. Mag., 25, 2, 21-30 (2008)
[14] Duarte, M. F.; Davenport, M. A.; Takhar, D.; Laska, J. N.; Sun, T.; Kelly, K. E.; Baraniuk, R. G., Single-pixel imaging via compressive sampling, IEEE Signal Process. Mag., 25, 2, 83 (2008)
[15] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[16] Candes, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[17] Candes, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[18] Candes, E.; Tao, T., The Dantzig selector: statistical estimation when p is much larger than n, Ann. Statist., 2313-2351 (2007) · Zbl 1139.62019
[19] Mallat, S. G.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 12, 3397-3415 (1993) · Zbl 0842.94004
[20] Chen, S.; Billings, S. A.; Luo, W., Orthogonal least squares methods and their application to non-linear system identification, Internat. J. Control, 50, 5, 1873-1896 (1989) · Zbl 0686.93093
[21] Pati, Y. C.; Rezaiifar, R.; Krishnaprasad, P., Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, (Signals, Systems and Computers, 1993 Conference Record of The Twenty-Seventh Asilomar Conference on (1993), IEEE), 40-44
[22] Needell, D.; Vershynin, R., Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, IEEE J. Sel. Top. Signal Process., 4, 2, 310-316 (2010)
[23] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274 (2009) · Zbl 1174.94008
[24] Foucart, S., Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 6, 2543-2563 (2011) · Zbl 1242.65060
[25] Dai, W.; Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55, 5, 2230-2249 (2009) · Zbl 1367.94082
[26] Needell, D.; Tropp, J. A., CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321 (2009) · Zbl 1163.94003
[27] Baraniuk, R. G.; Cevher, V.; Duarte, M. F.; Hegde, C., Model-based compressive sensing, IEEE Trans. Inform. Theory, 56, 4, 1982-2001 (2010) · Zbl 1366.94215
[28] Lee, K.; Bresler, Y., ADMiRA: atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[29] Davenport, M. A.; Needell, D.; Wakin, M. B., Signal space CoSaMP for sparse recovery with redundant dictionaries, IEEE Trans. Inform. Theory, 59, 10, 6820-6829 (2013) · Zbl 1364.94119
[30] Giryes, R.; Needell, D., Greedy signal space methods for incoherence and beyond, Appl. Comput. Harmon. Anal., 39, 1, 1-20 (2015) · Zbl 1345.94025
[31] Giryes, R.; Nam, S.; Elad, M.; Gribonval, R.; Davies, M. E., Greedy-like algorithms for the cosparse analysis model, Linear Algebra Appl., 441, 22-60 (2014) · Zbl 1332.94043
[32] Lu, Y. M.; Do, M. N., A theory for sampling signals from a union of subspaces, IEEE Trans. Signal Process., 56, 6, 2334-2345 (2008) · Zbl 1390.94656
[33] Blumensath, T.; Davies, M. E., Sampling theorems for signals from the union of finite-dimensional linear subspaces, IEEE Trans. Inform. Theory, 55, 4, 1872-1882 (2009) · Zbl 1367.94144
[34] Puy, G.; Davies, M.; Gribonval, R., Recipes for stable linear embeddings from Hilbert spaces to \(\mathbb{R}^m\), arXiv preprint · Zbl 1366.94122
[35] Eldar, Y. C.; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087
[36] Blumensath, T., Sampling and reconstructing signals from a union of linear subspaces, IEEE Trans. Inform. Theory, 57, 7, 4660-4671 (2011) · Zbl 1365.94173
[37] Blanchard, J. D.; Tanner, J., Performance comparisons of greedy algorithms in compressed sensing, Numer. Linear Algebra Appl., 22, 2, 254-282 (2015) · Zbl 1363.94017
[38] Blumensath, T.; Davies, M. E., Normalized iterative hard thresholding: guaranteed stability and performance, IEEE J. Sel. Top. Signal Process., 4, 2, 298-309 (2010)
[39] Giryes, R., A greedy algorithm for the analysis transform domain, Neurocomputing, 173, 278-289 (2016)
[40] Elad, M.; Starck, J.-L.; Querre, P.; Donoho, D. L., Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal., 19, 3, 340-358 (2005) · Zbl 1081.68732
[41] Gordon, Y., On Milman’s Inequality and Random Subspaces Which Escape Through a Mesh in \(\mathbb{R}^n (1988)\), Springer · Zbl 0651.46021
[42] Ledoux, M.; Talagrand, M., Probability in Banach Spaces: Isoperimetry and Processes (2013), Springer Science & Business Media
[43] Giryes, R.; Elad, M., RIP-based near-oracle performance guarantees for SP, CoSaMP, and IHT, IEEE Trans. Signal Process., 60, 3, 1465-1468 (2012) · Zbl 1393.94243
[44] Oymak, S.; Recht, B.; Soltanolkotabi, M., Sharp time-data tradeoffs for linear inverse problems, arXiv preprint · Zbl 1395.90205
[45] Plan, Y.; Vershynin, R., Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach (2014)
[46] Davis, G.; Mallat, S.; Avellaneda, M., Adaptive greedy approximations, Constr. Approx., 13, 1, 57-98 (1997) · Zbl 0885.41006
[47] Vershynin, R., Estimation in high dimensions: a geometric perspective, (Sampling Theory, a Renaissance (2015), Springer), 3-66 · Zbl 1370.94269
[48] Tillmann, A. M.; Gribonval, R.; Pfetsch, M. E., Projection onto the cosparse set is NP-hard, (2014 IEEE International Conference on Acoustics, Speech and Signal Processing. 2014 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (2014), IEEE), 7148-7152
[49] Waters, A. E.; Sankaranarayanan, A. C.; Baraniuk, R., SpaRCS: recovering low-rank and sparse matrices from compressive measurements, (Advances in Neural Information Processing Systems (2011)), 1089-1097
[50] Ai, A.; Lapanowski, A.; Plan, Y.; Vershynin, R., One-bit compressed sensing with non-Gaussian measurements, Linear Algebra Appl., 441, 222-239 (2014) · Zbl 1332.94041
[51] Foucart, S., Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants, (Approximation Theory XIII: San Antonio 2010 (2012), Springer), 65-77 · Zbl 1250.65057
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.