\(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed? (English) Zbl 1460.94021

Summary: This paper investigates the problem of stable signal estimation from undersampled, noisy sub-Gaussian measurements under the assumption of a cosparse model. Based on generalized notions of sparsity, a novel recovery guarantee for the \(\ell^1\)-analysis basis pursuit is derived, enabling accurate predictions of its sample complexity. The bounds on the number of required measurements explicitly depend on the Gram matrix of the analysis operator and therefore account for its mutual coherence structure. The presented results defy conventional wisdom which promotes the sparsity of analysis coefficients as the crucial quantity to be studied. In fact, this paradigm breaks down in many situations of interest, for instance, when applying a redundant (multilevel) frame as analysis prior. In contrast, the proposed sampling-rate bounds reliably capture the recovery capability of various practical examples. The proofs are based on establishing a sophisticated upper bound on the conic Gaussian mean width associated with the underlying \(\ell^1\)-analysis polytope.


94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C90 Applications of mathematical programming
Full Text: DOI arXiv


[1] Aberdam, A.; Sulam, J.; Elad, M., Multi-layer sparse coding: the holistic way, SIAM J. Math. Data Sci., 1, 1, 46-77 (2019)
[2] Amelunxen, D.; Lotz, M.; McCoy, M. B.; Tropp, J. A., Living on the edge: phase transitions in convex programs with random data, Inf. Inference, 3, 3, 224-294 (2014) · Zbl 1339.90251
[3] Baraniuk, R. G.; Choi, H.; Neelamani, R., Rice Wavelet Toolbox, Version 3 (Aug. 2017)
[4] van den Berg, E.; Friedlander, M. P., Spot - A Linear-Operator Toolbox (Aug. 2013)
[5] Bian, X.; Krim, H.; Bronstein, A.; Dai, L., Sparsity and nullity: paradigms for analysis dictionary learning, SIAM J. Imaging Sci., 9, 3, 1107-1126 (2016) · Zbl 1343.68191
[6] Blumensath, T.; Davies, M. E., Sampling theorems for signals from the union of finite-dimensional linear subspaces, IEEE Trans. Inf. Theory, 55, 4, 1872-1882 (2009) · Zbl 1367.94144
[7] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122
[8] Bruer, J. J.; Tropp, J. A.; Cevher, V.; Becker, S. R., Designing statistical estimators that balance sample size, risk, and computational cost, IEEE J. Sel. Top. Signal Process., 9, 4, 612-624 (2015)
[9] Cai, J.-F.; Osher, S.; Shen, Z., Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8, 2, 337-369 (2010) · Zbl 1189.94014
[10] Cai, J.-F.; Xu, W., Guarantees of total variation minimization for signal recovery, Inf. Inference, 4, 4, 328-353 (2015) · Zbl 1387.94028
[11] Candès, E. J.; Eldar, Y. C.; Needell, D.; Randall, P., Compressed sensing with coherent and redundant dictionaries, Appl. Comput. Harmon. Anal., 31, 1, 59-73 (2011) · Zbl 1215.94026
[12] Candès, E. J.; Romberg, J. K.; 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
[13] Candès, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[14] (Casazza, P. G.; Kutyniok, G., Finite Frames: Theory and Applications. Applied and Numerical Harmonic Analysis (2013), Birkhäuser: Birkhäuser Basel) · Zbl 1257.42001
[15] Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 1, 89-97 (2004) · Zbl 1366.94048
[16] Chandrasekaran, V.; Jordan, M. I., Computational and statistical tradeoffs via convex relaxation, Proc. Natl. Acad. Sci. USA, 110, 13, E1181-E1190 (2013) · Zbl 1292.62019
[17] 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
[18] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 1, 33-61 (1998) · Zbl 0919.94002
[19] Chen, Y.; Ranftl, R.; Pock, T., Insights into analysis operator learning: from patch-based sparse models to higher order MRFs, IEEE Trans. Image Process., 23, 3, 1060-1072 (2014) · Zbl 1374.94065
[20] Coifman, R. R.; Donoho, D. L., Translation-invariant de-noising, (Antoniadis, A.; Oppenheim, G., Wavelets and Statistics. Wavelets and Statistics, Lecture Notes in Statistics, vol. 103 (1995), Springer: Springer New York), 125-150 · Zbl 0866.94008
[21] Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[22] Donoho, D. L.; Johnstone, J. M., Ideal spatial adaptation by wavelet shrinkage, Biometrika, 81, 3, 425-455 (1994) · Zbl 0815.62019
[23] Dragotti, P. L.; Vetterli, M., Wavelet footprints: theory, algorithms, and applications, IEEE Trans. Signal Process., 51, 5, 1306-1323 (2003) · Zbl 1369.94043
[24] Elad, M.; Milanfar, P.; Rubinstein, R., Analysis versus synthesis in signal priors, Inverse Probl., 23, 3, 947-968 (2007) · Zbl 1138.93055
[25] Folland, G. B., Real Analysis: Modern Techniques and Their Applications (1999), Wiley · Zbl 0924.28001
[26] Fornasier, M.; Gröchenig, K., Intrinsic localization of frames, Constr. Approx., 22, 3, 395-415 (2005) · Zbl 1130.41304
[27] Foucart, S., Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl., 441, 4-21 (2014) · Zbl 1332.94042
[28] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing: Applied and Numerical Harmonic Analysis (2013), Birkhäuser: Birkhäuser Basel
[29] Fowler, J. E., The redundant discrete wavelet transform and additive noise, IEEE Signal Process. Lett., 12, 9, 629-632 (2005)
[30] Friedlander, M. P.; Mansour, H.; Saab, R.; Yilmaz, O., Recovering compressively sampled signals using partial support information, IEEE Trans. Inf. Theory, 58, 2, 1122-1134 (2012) · Zbl 1365.94071
[31] Genzel, M., High-dimensional estimation of structured signals from non-linear observations with general convex loss functions, IEEE Trans. Inf. Theory, 63, 3, 1601-1619 (2017) · Zbl 1366.94101
[32] 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
[33] Giryes, R.; Plan, Y.; Vershynin, R., On the effective measure of dimension in the analysis Cosparse model, IEEE Trans. Inf. Theory, 61, 10, 5745-5753 (2015) · Zbl 1359.94032
[34] Giryes, R.; Eldar, Y. C.; Bronstein, A. M.; Sapiro, G., Tradeoffs between convergence speed and reconstruction accuracy in inverse problems, IEEE Trans. Signal Process., 66, 7, 1676-1690 (2018) · Zbl 1414.94216
[35] Gordon, Y., On Milman’s inequality and random subspaces which escape through a mesh in \(\operatorname{R}^n\), (Lindenstrauss, J.; Milman, V. D., Geometric Aspects of Functional Analysis. Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 1317 (1988), Springer: Springer Berlin Heidelberg), 84-106
[36] Grant, M.; Boyd, S., Graph implementations for nonsmooth convex programs, (Blondel, V.; Boyd, S.; Kimura, H., Recent Advances in Learning and Control. Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, vol. 371 (2008), Springer: Springer London), 95-110 · Zbl 1205.90223
[37] Grant, M.; Boyd, S., CVX: Matlab Software for Disciplined Convex Programming (Mar. 2014), version 2.1
[38] Gröchenig, K., Localization of frames, Banach frames, and the invertibility of the frame operator, J. Fourier Anal. Appl., 10.2, 105-132 (2004) · Zbl 1055.42018
[39] Guerquin-Kern, M.; Lejeune, J.; Pruessmann, K. P.; Unser, M., Realistic analytical phantoms for parallel Magnetic Resonance Imaging, IEEE Trans. Med. Imaging, 31, 3, 626-636 (2012)
[40] Hawe, S.; Kleinsteuber, M.; Diepold, K., Analysis operator learning and its application to image reconstruction, IEEE Trans. Image Process., 22, 6, 2138-2150 (2013) · Zbl 1373.94161
[41] Kabanava, M.; Rauhut, H., Analysis \(\ell_1\)-recovery with frames and Gaussian measurements, Acta Appl. Math., 140, 1, 173-195 (2015) · Zbl 1378.94008
[42] Kabanva, M.; Rauhut, H.; Zhang, H., Robust analysis \(\ell_1\)-recovery from Gaussian measurements and total variation minimization, Eur. J. Appl. Math., 26, 6, 917-929 (2015) · Zbl 1387.94039
[43] Khajehnejad, M. A.; Xu, W.; Avestimehr, A. S.; Hassibi, B., Weighted \(\ell^1\) minimization for sparse recovery with prior information, (Proceedings of the IEEE International Symposium on Information Theory Proceedings (ISIT) (2009)), 483-487
[44] Kitić, S.; Albera, L.; Bertin, N.; Gribonval, R., Physics-driven inverse problems made tractable with cosparse regularization, IEEE Trans. Signal Process., 64, 2, 335-348 (2016) · Zbl 1412.94050
[45] Krahmer, F.; Kruschel, C.; Sandbichler, M., Total Variation Minimization in Compressed Sensing, (Boche, H.; Caire, G.; Calderbank, R.; März, M.; Kutyniok, G.; Mathar, R., Compressed Sensing and its Applications: Second International MATHEON Conference 2015 (2017), Birkhäuser Cham)
[46] Krahmer, F.; Needell, D.; Ward, R., Compressive sensing with redundant dictionaries and structured measurements, SIAM J. Math. Anal., 47, 6, 4606-4629 (2015) · Zbl 1345.94014
[47] Kutyniok, G.; Lim, W.-Q.; Reisenhofer, R., Shearlab 3D: faithful digital shearlet transforms based on compactly supported shearlets, ACM Trans. Math. Softw., 42, 1 (2016), Art. 5 · Zbl 1347.65203
[48] Lee, K.; Li, Y.; Jin, K. H.; Ye, J. C., Unified theory for recovery of sparse signals in a general transform domain, IEEE Trans. Inf. Theory, 64, 8, 5457-5477 (2018) · Zbl 1401.94044
[49] Liaw, C.; Mehrabian, A.; Plan, Y.; Vershynin, R., A simple tool for bounding the deviation of random matrices on geometric sets, (Klartag, B.; Milman, E., Geometric Aspects of Functional Analysis. Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 2169 (2017), Springer: Springer Cham), 277-299 · Zbl 1366.60011
[50] Lin, J.; Li, S., Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO, Appl. Comput. Harmon. Anal., 37, 1, 126-139 (2014) · Zbl 1345.94016
[51] Liu, Y.; Mi, T.; Li, S., Compressed sensing with general frames via optimal-dual-based \(\ell_1\)-analysis, IEEE Trans. Inf. Theory, 58, 7, 4201-4214 (2012) · Zbl 1365.94181
[52] Lustig, M.; Donoho, D. L.; Santos, J. M.; Pauly, J. M., Compressed sensing MRI, IEEE Signal Process. Mag., 25, 2, 72-82 (2008)
[53] Mallat, S., A Wavelet Tour of Signal Processing: The Sparse Way (2009), Elsevier · Zbl 1170.94003
[54] McMahon, E., An extension of Price’s theorem (corresp.), IEEE Trans. Inf. Theory, 10.2, 168 (1964) · Zbl 0141.17004
[55] Mead, J. L.; Renaut, R. A., Least squares problems with inequality constraints as quadratic constraints, Linear Algebra Appl., 432, 8, 1936-1949 (2010) · Zbl 1185.65068
[56] Mendelson, S.; Pajor, A.; Tomczak-Jaegermann, N., Reconstruction and subgaussian operators in asymptotic geometric analysis, Geom. Funct. Anal., 17, 4, 1248-1282 (2007) · Zbl 1163.46008
[57] Mohri, M.; Rostamizadeh, A.; Talwalkar, A., Foundations of Machine Learning (2012), MIT press · Zbl 1318.68003
[58] 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
[59] Nam, S.; Gribonval, R., Physics-driven structured cosparse modeling for source localization, (Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (2012)), 5397-5400
[60] Needell, D.; Ward, R., Stable image reconstruction using total variation minimization, SIAM J. Imaging Sci., 6, 2, 1035-1058 (2013) · Zbl 1370.94042
[61] Oymak, S.; Recht, B.; Soltanolkotabi, M., Sharp time-data tradeoffs for linear inverse problems, IEEE Trans. Inf. Theory, 64, 6, 4129-4158 (2018) · Zbl 1395.90205
[62] Oymak, S.; Hassibi, B., Sharp MSE bounds for proximal denoising, Found. Comput. Math., 16, 4, 965-1029 (2016) · Zbl 1380.90221
[63] Oymak, S.; Khajehnejad, M. A.; Hassibi, B., Recovery threshold for optimal weight \(\ell_1\) minimization, (Proceedings of the IEEE International Symposium on Information Theory Proceedings. Proceedings of the IEEE International Symposium on Information Theory Proceedings, ISIT (2012)), 2032-2036
[64] Plan, Y.; Vershynin, R., Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach, IEEE Trans. Inf. Theory, 59, 1, 482-494 (2013) · Zbl 1364.94153
[65] Plonka, G.; Ma, J., Curvelet-wavelet regularized split Bregman iteration for compressed sensing, Int. J. Wavelets Multiresolut. Inf. Process., 09, 01, 79-110 (2011) · Zbl 1208.94017
[66] Poon, C., Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames, Appl. Comput. Harmon. Anal., 42, 3, 402-451 (2017) · Zbl 1422.94021
[67] Price, R., A useful theorem for nonlinear devices having Gaussian inputs, IRE Trans. Inf. Theory, 4, 2, 69-72 (1958) · Zbl 0108.30605
[68] Rauhut, H.; Schnass, K.; Vandergheynst, P., Compressed sensing and redundant dictionaries, IEEE Trans. Inf. Theory, 54, 5, 2210-2219 (2008) · Zbl 1332.94022
[69] Ravishankar, S.; Bresler, Y., Learning sparsifying transforms, IEEE Trans. Signal Process., 61, 5, 1072-1089 (2013) · Zbl 1393.94409
[70] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press · Zbl 0229.90020
[71] Rubinstein, R.; Peleg, T.; Elad, M., Analysis K-SVD: a dictionary-learning algorithm for the analysis sparse model, IEEE Trans. Signal Process., 61, 3, 661-677 (2013) · Zbl 1393.94416
[72] Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math., 61, 8, 1025-1045 (2008) · Zbl 1149.94010
[73] Rudin, L.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60.1-4, 259-268 (1992) · Zbl 0780.49028
[74] Selesnick, I. W.; Figueiredo, M. A.T., Signal restoration with overcomplete wavelet transforms: comparison of analysis and synthesis priors, (Goyal, V. K.; Papadakis, M.; Ville, D. V.D., Proceedings of SPIE, Wavelets XIII, vol. 7446 (2009))
[75] Shalev-Shwartz, S.; Ben-David, S., Understanding Machine Learning: From Theory to Algorithms (2014), Cambridge University Press · Zbl 1305.68005
[76] Shen, Y.; Han, B.; Braverman, E., Stable recovery of analysis based approaches, Appl. Comput. Harmon. Anal., 39, 1, 161-172 (2015) · Zbl 1345.94019
[77] Tan, Z.; Eldar, Y. C.; Beck, A.; Nehorai, A., Smoothing and decomposition for analysis sparse recovery, IEEE Trans. Signal Process., 62, 7, 1762-1774 (2014) · Zbl 1394.94580
[78] Tillmann, A. M.; Gribonval, R.; Pfetsch, M. E., Projection onto the cosparse set is NP-hard, (Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (2014)), 7148-7152
[79] Tropp, J. A., Convex recovery of a structured signal from independent random linear measurements, (Pfander, G. E., Sampling Theory, a Renaissance. Sampling Theory, a Renaissance, Applied and Numerical Harmonic Analysis (2015), Birkhäuser: Birkhäuser Cham), 67-101 · Zbl 1358.94034
[80] Vaiter, S.; Peyre, G.; Dossal, C.; Fadili, J., Robust sparse analysis regularization, IEEE Trans. Inf. Theory, 59, 4, 2001-2016 (2013) · Zbl 1364.94172
[81] Vandeghinste, B.; Goossens, B.; Van Holen, R.; Vanhove, C.; Pizurica, A.; Vandenberghe, S.; Staelens, S., Iterative CT reconstruction using shearlet-based regularization, IEEE Trans. Nucl. Sci., 60, 5, 3305-3317 (2013)
[82] Vapnik, V., The Nature of Statistical Learning Theory (2000), Springer: Springer New York · Zbl 0934.62009
[83] Vershynin, R., High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47 (2018), Cambridge University Press · Zbl 1430.60005
[84] 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
[85] Voigtlaender, F., A general version of Price’s theorem (2017), preprint
[86] Yaghoobi, M.; Nam, S.; Gribonval, R.; Davies, M. E., Constrained overcomplete analysis operator learning for cosparse signal modelling, IEEE Trans. Signal Process., 61, 9, 2341-2355 (2013)
[87] Zhang, B.; Xu, W.; Cai, J.-F.; Lai, L., Precise phase transition of total variation minimization, (Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP (2016)), 4518-4522
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.