{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T10:34:26Z","timestamp":1756636466412},"reference-count":101,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s10208-022-09580-w","type":"journal-article","created":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T16:03:55Z","timestamp":1661789035000},"page":"2089-2150","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sampling Rates for $$\\ell ^1$$-Synthesis"],"prefix":"10.1007","volume":"23","author":[{"given":"Maximilian","family":"M\u00e4rz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Boyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonas","family":"Kahn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Weiss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,29]]},"reference":[{"issue":"3","key":"9580_CR1","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1093\/imaiai\/iau005","volume":"3","author":"D Amelunxen","year":"2014","unstructured":"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\u2013294 (2014)","journal-title":"Inf. Inference"},{"key":"9580_CR2","doi-asserted-by":"crossref","unstructured":"Amelunxen, D., Lotz, M., Walvin, J.: Effective condition number bounds for convex regularization. IEEE Trans. Inf. Theory (2020). In press","DOI":"10.1109\/TIT.2020.2965720"},{"key":"9580_CR3","unstructured":"Baraniuk, R., Choi, H., Neelamani, R., et\u00a0al.: Rice Wavelet Toolbox, Version 3. URL: https:\/\/github.com\/ricedsp\/rwt (2017)"},{"key":"9580_CR4","first-page":"463","volume":"3","author":"PL Bartlett","year":"2002","unstructured":"Bartlett, P.L., Mendelson, S.: Rademacher and Gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res. 3, 463\u2013482 (2002)","journal-title":"J. Mach. Learn. Res."},{"key":"9580_CR5","unstructured":"Beurling, A.: Sur les int\u00e9grales de Fourier absolument convergentes et leur application \u00e0 une transformation fonctionnelle. In: Ninth Scandinavian Mathematical Congress, pp. 345\u2013366 (1938)"},{"key":"9580_CR6","doi-asserted-by":"crossref","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press (2013)","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"9580_CR7","doi-asserted-by":"crossref","unstructured":"Bristow, H., Eriksson, A., Lucey, S.: Fast convolutional sparse coding. In: 2013 IEEE Conference on Computer Vision and Pattern Recognition (2013)","DOI":"10.1109\/CVPR.2013.57"},{"issue":"4","key":"9580_CR8","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.jvcir.2008.03.001","volume":"19","author":"O Bryt","year":"2008","unstructured":"Bryt, O., Elad, M.: Compression of facial images using the K-SVD algorithm. J. Vis. Commun. Image Represent. 19(4), 270\u2013282 (2008)","journal-title":"J. Vis. Commun. Image Represent."},{"key":"9580_CR9","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Cucker, F.: Condition: The geometry of numerical algorithms, vol. 349. Springer Science & Business Media (2013)","DOI":"10.1007\/978-3-642-38896-5"},{"issue":"4","key":"9580_CR10","first-page":"328","volume":"4","author":"JF Cai","year":"2015","unstructured":"Cai, J.F., Xu, W.: Guarantees of total variation minimization for signal recovery. Inf. Inference 4(4), 328\u2013353 (2015)","journal-title":"Inf. Inference"},{"issue":"1","key":"9580_CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.acha.2010.10.002","volume":"31","author":"EJ Cand\u00e8s","year":"2011","unstructured":"Cand\u00e8s, E.J., Eldar, Y.C., Needell, D., Randall, P.: Compressed sensing with coherent and redundant dictionaries. Appl. Comput. Harmon. Anal. 31(1), 59\u201373 (2011)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"6","key":"9580_CR12","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1002\/cpa.21455","volume":"67","author":"EJ Cand\u00e8s","year":"2014","unstructured":"Cand\u00e8s, E.J., Fernandez-Granda, C.: Towards a mathematical theory of super-resolution. Commun. Pur. Appl. Math. 67(6), 906\u2013956 (2014)","journal-title":"Commun. Pur. Appl. Math."},{"issue":"2","key":"9580_CR13","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theor. 52(2), 489-509 (2006)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"8","key":"9580_CR14","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Comm. Pure Appl. Math."},{"issue":"12","key":"9580_CR15","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"9580_CR16","doi-asserted-by":"crossref","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Tao, T.: Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theor. 52(12), 5406\u20135425 (2006)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"2","key":"9580_CR17","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/j.acha.2020.05.006","volume":"49","author":"PG Casazza","year":"2020","unstructured":"Casazza, P.G., Chen, X., Lynch, R.G.: Preserving injectivity under subgaussian mappings and its application to compressed sensing. Appl. Comput. Harmon. Anal. 49(2), 451\u2013470 (2020)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9580_CR18","doi-asserted-by":"crossref","unstructured":"Casazza, P.G., Kutyniok, G. (eds.): Finite Frames: Theory and Applications. Applied and Numerical Harmonic Analysis. Birkh\u00e4user (2013)","DOI":"10.1007\/978-0-8176-8373-3"},{"issue":"6","key":"9580_CR19","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1007\/s10208-012-9135-7","volume":"12","author":"V Chandrasekaran","year":"2012","unstructured":"Chandrasekaran, V., Recht, B., Parrilo, P.A., Willsky, A.S.: The convex geometry of linear inverse problems. Found. Comput. Math. 12(6), 805\u2013849 (2012)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"9580_CR20","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/S1064827596304010","volume":"20","author":"S Chen","year":"1998","unstructured":"Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33\u201361 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"3","key":"9580_CR21","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/j.acha.2014.01.006","volume":"37","author":"X Chen","year":"2014","unstructured":"Chen, X., Wang, H., Wang, R.: A null space analysis of the $$\\ell _1$$-synthesis method in dictionary-based compressed sensing. Appl. Comput. Harmon. Anal. 37(3), 492\u2013515 (2014)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"5","key":"9580_CR22","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1190\/1.1440378","volume":"38","author":"JF Claerbout","year":"1973","unstructured":"Claerbout, J.F., Muir, F.: Robust Modeling With Erratic Data. Geophysics 38(5), 826\u2013844 (1973)","journal-title":"Geophysics"},{"issue":"1","key":"9580_CR23","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1090\/S0894-0347-08-00610-3","volume":"22","author":"A Cohen","year":"2009","unstructured":"Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22(1), 211\u2013231 (2009)","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"9580_CR24","doi-asserted-by":"crossref","first-page":"552","DOI":"10.3150\/15-BEJ756","volume":"23","author":"AS Dalalyan","year":"2017","unstructured":"Dalalyan, A.S., Hebiri, M., Lederer, J.: On the prediction performance of the lasso. Bernoulli 23(1), 552\u2013581 (2017)","journal-title":"Bernoulli"},{"issue":"10","key":"9580_CR25","doi-asserted-by":"crossref","first-page":"6820","DOI":"10.1109\/TIT.2013.2273491","volume":"59","author":"MA Davenport","year":"2013","unstructured":"Davenport, M.A., Needell, D., Wakin, M.B.: Signal space cosamp for sparse recovery with redundant dictionaries. IEEE Trans. Inf. Theory 59(10), 6820\u20136829 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"9580_CR26","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"9580_CR27","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1073\/pnas.0437847100","volume":"100","author":"DL Donoho","year":"2003","unstructured":"Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via $$\\ell ^1$$ minimization. Proc. Natl. Acad. Sci. 100(5), 2197\u20132202 (2003)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"7","key":"9580_CR28","doi-asserted-by":"crossref","first-page":"2845","DOI":"10.1109\/18.959265","volume":"47","author":"DL Donoho","year":"2001","unstructured":"Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47(7), 2845\u20132862 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9580_CR29","unstructured":"Dossal, C.: Estimation de fonctions g\u00e9om\u00e9triques et d\u00e9convolution. Ph.D. thesis, IMB \u2013 Institut de Math\u00e9matiques de Bordeaux (2005). Ph.D. Thesis: https:\/\/tel.archives-ouvertes.fr\/tel-00855128\/"},{"key":"9580_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-7011-4","volume-title":"Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing","author":"M Elad","year":"2010","unstructured":"Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer-Verlag, New York (2010)"},{"issue":"12","key":"9580_CR31","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1109\/TIP.2006.881969","volume":"15","author":"M Elad","year":"2006","unstructured":"Elad, M., Aharon, M.: Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Imag. Proc. 15(12), 3736\u20133745 (2006)","journal-title":"IEEE Trans. Imag. Proc."},{"key":"9580_CR32","doi-asserted-by":"crossref","unstructured":"Elad, M., Bruckstein, A.M.: A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans. Inf. Theory 48(9) (2002)","DOI":"10.1109\/TIT.2002.801410"},{"issue":"6","key":"9580_CR33","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1109\/JPROC.2009.2037655","volume":"98","author":"M Elad","year":"2010","unstructured":"Elad, M., Figueiredo, M.A.T., Ma, Y.: On the role of sparse and redundant representations in image processing. Proc. IEEE 98(6), 972\u2013982 (2010)","journal-title":"Proc. IEEE"},{"issue":"3","key":"9580_CR34","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1088\/0266-5611\/23\/3\/007","volume":"23","author":"M Elad","year":"2007","unstructured":"Elad, M., Milanfar, P., Rubinstein, R.: Analysis versus synthesis in signal priors. Inverse Probl. 23(3), 947\u2013968 (2007)","journal-title":"Inverse Probl."},{"key":"9580_CR35","doi-asserted-by":"crossref","unstructured":"Fernique, X.: Regularit\u00e9 des trajectoires des fonctions al\u00e9atoires gaussiennes. In: Ecole d\u2019Et\u00e9 de Probabilit\u00e9s de Saint-Flour IV-1974, pp. 1\u201396. Springer (1975)","DOI":"10.1007\/BFb0080190"},{"key":"9580_CR36","doi-asserted-by":"crossref","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkh\u00e4user (2013)","DOI":"10.1007\/978-0-8176-4948-7"},{"issue":"1","key":"9580_CR37","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1137\/S105262349732829X","volume":"10","author":"RM Freund","year":"1999","unstructured":"Freund, R.M., Vera, J.R.: Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm. SIAM J. Optim. 10(1), 155\u2013176 (1999)","journal-title":"SIAM J. Optim."},{"issue":"376","key":"9580_CR38","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1080\/01621459.1981.10477729","volume":"76","author":"JH Friedman","year":"1981","unstructured":"Friedman, J.H., Stuetzle, W.: Projection pursuit regression. J. Am. Stat. Assoc. 76(376), 817\u2013823 (1981)","journal-title":"J. Am. Stat. Assoc."},{"issue":"9","key":"9580_CR39","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/T-C.1974.224051","volume":"100","author":"JH Friedman","year":"1974","unstructured":"Friedman, J.H., Tukey, J.W.: A projection pursuit algorithm for exploratory data analysis. IEEE Trans. Comput. 100(9), 881\u2013890 (1974)","journal-title":"IEEE Trans. Comput."},{"issue":"6","key":"9580_CR40","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1109\/TIT.2004.828141","volume":"50","author":"JJ Fuchs","year":"2004","unstructured":"Fuchs, J.J.: On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50(6), 1341\u20131344 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"10","key":"9580_CR41","doi-asserted-by":"crossref","first-page":"3601","DOI":"10.1109\/TIT.2005.855614","volume":"51","author":"JJ Fuchs","year":"2005","unstructured":"Fuchs, J.J.: Recovery of exact sparse representations in the presence of bounded noise. IEEE Trans. Inf. Theory 51(10), 3601\u20133608 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9580_CR42","doi-asserted-by":"crossref","unstructured":"Genzel, M., Kutyniok, G., M\u00e4rz, M.: $$\\ell ^1$$-analysis minimization and generalized (co-)sparsity: When does recovery succeed? Appl. Comput. Harmon. Anal. (2020). Accepted, arXiv:1710.04952","DOI":"10.1016\/j.acha.2020.01.002"},{"key":"9580_CR43","doi-asserted-by":"crossref","unstructured":"Genzel, M., M\u00e4rz, M., Seidel, R.: Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery. Inf. Inference (2020). Accpeted for publication","DOI":"10.1093\/imaiai\/iaab001"},{"key":"9580_CR44","doi-asserted-by":"crossref","unstructured":"Giannopoulos, A.A., Milman, V.D.: Asymptotic convex geometry short overview. In: S.\u00a0Donaldson, Y.\u00a0Eliashberg, M.\u00a0Gromov (eds.) Different Faces of Geometry, pp. 87\u2013162. Springer (2004)","DOI":"10.1007\/0-306-48658-X_3"},{"key":"9580_CR45","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.laa.2013.03.004","volume":"441","author":"R Giryes","year":"2014","unstructured":"Giryes, R., Nam, S., Elad, M., Gribonval, R., Davies, M.E.: Greedy-like algorithms for the cosparse analysis model. Linear Algebra Appl. 441, 22\u201360 (2014)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"9580_CR46","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02759761","volume":"50","author":"Y Gordon","year":"1985","unstructured":"Gordon, Y.: Some inequalities for Gaussian processes and applications. Isr. J. Math. 50(4), 265\u2013289 (1985)","journal-title":"Isr. J. Math."},{"key":"9580_CR47","doi-asserted-by":"crossref","unstructured":"Gordon, Y.: On Milman\u2019s inequality and random subspaces which escape through a mesh in $$\\mathbb{R}^{n}$$. In: J.\u00a0Lindenstrauss, V.D. Milman (eds.) Geometric aspects of functional analysis, Lecture Notes in Mathematics, vol. 1317, pp. 84\u2013106. Springer (1988)","DOI":"10.1007\/BFb0081737"},{"key":"9580_CR48","doi-asserted-by":"crossref","unstructured":"Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: V.\u00a0Blondel, S.\u00a0Boyd, H.\u00a0Kimura (eds.) Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, vol. 371, pp. 95\u2013110. Springer London (2008)","DOI":"10.1007\/978-1-84800-155-8_7"},{"key":"9580_CR49","unstructured":"Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. URL: http:\/\/cvxr.com\/cvx (2014)"},{"issue":"12","key":"9580_CR50","doi-asserted-by":"crossref","first-page":"3320","DOI":"10.1109\/TIT.2003.820031","volume":"49","author":"R Gribonval","year":"2003","unstructured":"Gribonval, R., Nielsen, M.: Sparse representations in unions of bases. IEEE Trans. Inf. Theory 49(12), 3320\u20133325 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9580_CR51","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10444-005-9009-5","volume":"28","author":"R Gribonval","year":"2008","unstructured":"Gribonval, R., Nielsen, M.: Beyond sparsity: Recovering structured representations by $$\\ell ^1$$ minimization and greedy algorithms. Adv. Comput. Math. 28(1), 23\u201341 (2008)","journal-title":"Adv. Comput. Math."},{"issue":"1","key":"9580_CR52","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1214\/18-AOS1799","volume":"48","author":"A Guntuboyina","year":"2020","unstructured":"Guntuboyina, A., Lieu, D., Chatterjee, S., Sen, B.: Adaptive risk bounds in univariate total variation denoising and trend filtering. Ann. Statist. 48(1), 205\u2013229 (2020)","journal-title":"Ann. Statist."},{"key":"9580_CR53","doi-asserted-by":"crossref","unstructured":"Hastie, T., Tibshirani, R., Wainwright, M.: Statistical learning with sparsity: the lasso and generalizations. CRC Press (2015)","DOI":"10.1201\/b18401"},{"key":"9580_CR54","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/s11228-010-0150-z","volume":"18","author":"R Henrion","year":"2010","unstructured":"Henrion, R., Seeger, A.: Inradius and circumradius of various convex cones arising in applications. Set-Valued Anal. 18, 483\u2013511 (2010)","journal-title":"Set-Valued Anal."},{"key":"9580_CR55","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s11228-009-0131-2","volume":"18","author":"R Henrion","year":"2010","unstructured":"Henrion, R., Seeger, A.: On properties of different notions of centers for convex cones. Set-Valued Anal. 18, 205\u2013231 (2010)","journal-title":"Set-Valued Anal."},{"issue":"4","key":"9580_CR56","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1137\/090750391","volume":"52","author":"JB Hiriart-Urruty","year":"2010","unstructured":"Hiriart-Urruty, J.B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52(4), 593\u2013629 (2010)","journal-title":"SIAM Rev."},{"issue":"1","key":"9580_CR57","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/j.jmaa.2007.05.030","volume":"338","author":"A Iusem","year":"2008","unstructured":"Iusem, A., Seeger, A.: Normality and modulability indices. Part i: Convex cones in normed spaces. J. Math. Anal. Appl. 338(1), 365\u2013391 (2008)","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"9580_CR58","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s10440-014-9984-y","volume":"140","author":"M Kabanava","year":"2015","unstructured":"Kabanava, M., Rauhut, H.: Analysis $$\\ell _1$$-recovery with frames and Gaussian measurements. Acta Appl. Math. 140(1), 173\u2013195 (2015)","journal-title":"Acta Appl. Math."},{"issue":"6","key":"9580_CR59","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1017\/S0956792515000236","volume":"26","author":"M Kabanva","year":"2015","unstructured":"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\u2013929 (2015)","journal-title":"Eur. J. Appl. Math."},{"issue":"6","key":"9580_CR60","doi-asserted-by":"crossref","first-page":"4606","DOI":"10.1137\/151005245","volume":"47","author":"F Krahmer","year":"2015","unstructured":"Krahmer, F., Needell, D., Ward, R.: Compressive sensing with redundant dictionaries and structured measurements. SIAM J. Math. Anal. 47(6), 4606\u20134629 (2015)","journal-title":"SIAM J. Math. Anal."},{"key":"9580_CR61","unstructured":"Kre\u01d0n, M.: The L-problem in an abstract normed linear space. In: I.\u00a0Ahiezer, M.\u00a0Kre\u01d0n (eds.) Some questions in the theory of moments, chap.\u00a04. Gos. Nau\u010dno-Tehn. Izdat. Ukraine (1938). English Transl. Amer. Math. Soc., Providence, R.I., 1962. MR 29 # 5073"},{"issue":"11","key":"9580_CR62","doi-asserted-by":"crossref","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86(11), 2278\u20132324 (1998)","journal-title":"Proc. IEEE"},{"key":"9580_CR63","doi-asserted-by":"crossref","unstructured":"Liaw, C., Mehrabian, A., Plan, Y., Vershynin, R.: A simple tool for bounding the deviation of random matrices on geometric sets. In: B.\u00a0Klartag, E.\u00a0Milman (eds.) Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, vol. 2169, pp. 277\u2013299. Springer (2017)","DOI":"10.1007\/978-3-319-45282-1_18"},{"issue":"2135","key":"9580_CR64","first-page":"3088","volume":"467","author":"MA Little","year":"2011","unstructured":"Little, M.A., Jones, N.S.: Generalized methods and solvers for noise removal from piecewise constant signals. I. background theory. Proc. Royal Soc. Lond. A 467(2135), 3088\u20133114 (2011)","journal-title":"Proc. Royal Soc. Lond. A"},{"key":"9580_CR65","doi-asserted-by":"crossref","unstructured":"Liu, Y., Li, S., Mi, T., Lei, H., Yu, W.: Performance analysis of $$\\ell _1$$-synthesis with coherent frames. In: 2012 IEEE International Symposium on Information Theory Proceedings, pp. 2042\u20132046 (2012)","DOI":"10.1109\/ISIT.2012.6283719"},{"issue":"2\u20133","key":"9580_CR66","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1561\/0600000058","volume":"8","author":"J Mairal","year":"2014","unstructured":"Mairal, J., Bach, F., Ponce, J.: Sparse modeling for image and vision processing. Found. Trends. Comput. Graph. Vis. 8(2-3), 85\u2013283 (2014)","journal-title":"Found. Trends. Comput. Graph. Vis."},{"key":"9580_CR67","unstructured":"Mairal, J., Ponce, J., Sapiro, G., Zisserman, A., Bach, F.: Supervised dictionary learning. In: D.\u00a0Koller, D.\u00a0Schuurmans, Y.\u00a0Bengio, L.\u00a0Bottou (eds.) Advances in Neural Information Processing Systems, vol.\u00a021 (2009)"},{"key":"9580_CR68","unstructured":"Mallat, S.: A Wavelet Tour of Signal Processing: The Sparse Way, 3rd edition edn. Elsevier (2009)"},{"issue":"12","key":"9580_CR69","doi-asserted-by":"crossref","first-page":"3397","DOI":"10.1109\/78.258082","volume":"41","author":"SG Mallat","year":"1993","unstructured":"Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397\u20133415 (1993)","journal-title":"IEEE Trans. Signal Process."},{"issue":"4","key":"9580_CR70","doi-asserted-by":"crossref","first-page":"1248","DOI":"10.1007\/s00039-007-0618-7","volume":"17","author":"S Mendelson","year":"2007","unstructured":"Mendelson, S., Pajor, A., Tomczak-Jaegermann, N.: Reconstruction and subgaussian operators in asymptotic geometric analysis. Geom. Funct. Anal. 17(4), 1248\u20131282 (2007)","journal-title":"Geom. Funct. Anal."},{"key":"9580_CR71","doi-asserted-by":"crossref","unstructured":"Milman, V.D.: Random subspaces of proportional dimension of finite dimensional normed spaces: Approach through the isoperimetric inequality. In: N.J. Kalton, E.\u00a0Saab (eds.) Banach Spaces, Lecture Notes in Mathematics, vol. 1166, pp. 106\u2013115. Springer Berlin Heidelberg (1985)","DOI":"10.1007\/BFb0074700"},{"issue":"2","key":"9580_CR72","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some np-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117\u2013129 (1987)","journal-title":"Math. Program."},{"issue":"1","key":"9580_CR73","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.acha.2012.03.006","volume":"34","author":"S Nam","year":"2013","unstructured":"Nam, S., Davies, M.E., Elad, M., Gribonval, R.: The cosparse analysis model and algorithms. Appl. Comput. Harmon. Anal. 34(1), 30\u201356 (2013)","journal-title":"Appl. Comput. Harmon. Anal."},{"issue":"6583","key":"9580_CR74","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1038\/381607a0","volume":"381","author":"BA Olshausen","year":"1996","unstructured":"Olshausen, B.A., Field, D.J.: Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381(6583), 607\u2013609 (1996)","journal-title":"Nature"},{"issue":"23","key":"9580_CR75","doi-asserted-by":"crossref","first-page":"3311","DOI":"10.1016\/S0042-6989(97)00169-7","volume":"37","author":"BA Olshausen","year":"1997","unstructured":"Olshausen, B.A., Field, D.J.: Sparse coding with an overcomplete basis set: A strategy employed by v1? Vis. Res. 37(23), 3311 \u2013 3325 (1997)","journal-title":"Vis. Res."},{"key":"9580_CR76","unstructured":"Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: Proceedings of 27th Asilomar Conference on Signals, Systems and Computers, pp. 40\u201344 vol.1 (1993)"},{"issue":"5","key":"9580_CR77","doi-asserted-by":"crossref","first-page":"2210","DOI":"10.1109\/TIT.2008.920190","volume":"54","author":"H Rauhut","year":"2008","unstructured":"Rauhut, H., Schnass, K., Vandergheynst, P.: Compressed sensing and redundant dictionaries. IEEE Trans. Inf. Theory 54(5), 2210\u20132219 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9580_CR78","first-page":"279","volume":"70","author":"J Renegar","year":"1995","unstructured":"Renegar, J.: Linear programming, complexity theory and elementary functional analysis. Math. Program. 70, 279-351 (1995)","journal-title":"Math. Program."},{"key":"9580_CR79","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press (1970)","DOI":"10.1515\/9781400873173"},{"issue":"6","key":"9580_CR80","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1109\/JPROC.2010.2040551","volume":"98","author":"R Rubinstein","year":"2010","unstructured":"Rubinstein, R., Bruckstein, A.M., Elad, M.: Dictionaries for sparse representation modeling. Proc. IEEE 98(6), 1045\u20131057 (2010)","journal-title":"Proc. IEEE"},{"issue":"8","key":"9580_CR81","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1002\/cpa.20227","volume":"61","author":"M Rudelson","year":"2007","unstructured":"Rudelson, M., Vershynin, R.: On sparse reconstruction from fourier and gaussian measurements. Comm. Pure Appl. Math. 61(8), 1025\u20131045 (2007)","journal-title":"Comm. Pure Appl. Math."},{"issue":"1\u20134","key":"9580_CR82","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0167-2789(92)90242-F","volume":"60","author":"L Rudin","year":"1992","unstructured":"Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1\u20134), 259\u2013268 (1992)","journal-title":"Physica D"},{"key":"9580_CR83","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0024-3795(03)00553-6","volume":"372","author":"A Seeger","year":"2003","unstructured":"Seeger, A., Torki, M.: On eigenvalues induced by a cone constraint. Linear Algebra Appl. 372, 181\u2013206 (2003)","journal-title":"Linear Algebra Appl."},{"key":"9580_CR84","doi-asserted-by":"crossref","unstructured":"Selesnick, I.W., Figueiredo, M.A.T.: Signal restoration with overcomplete wavelet transforms: comparison of analysis and synthesis priors. In: V.K. Goyal, M.\u00a0Papadakis, D.V.D. Ville (eds.) Proceedings of SPIE, Wavelets XIII, vol. 7446 (2009)","DOI":"10.1117\/12.826663"},{"key":"9580_CR85","unstructured":"Stojnic, M.: Various thresholds for $$\\ell _1$$-optimization in compressed sensing (2009). Preprint arXiv:0907.3666"},{"key":"9580_CR86","unstructured":"Sudakov, V.N.: Gaussian random processes and measures of solid angles in Hilbert space. In: Doklady Akademii Nauk, vol. 197, pp. 43\u201345. Russian Academy of Sciences (1971)"},{"issue":"1","key":"9580_CR87","first-page":"79","volume":"1","author":"JJ Sylvester","year":"1857","unstructured":"Sylvester, J.J.: A question in the geometry of situation. Quarterly Journal of Pure and Applied Mathematics 1(1), 79\u201380 (1857)","journal-title":"Quarterly Journal of Pure and Applied Mathematics"},{"key":"9580_CR88","doi-asserted-by":"crossref","unstructured":"Talagrand, M.: Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems. Springer (2014)","DOI":"10.1007\/978-3-642-54075-2"},{"issue":"1","key":"9580_CR89","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1190\/1.1440921","volume":"44","author":"HL Taylor","year":"1979","unstructured":"Taylor, H.L., Banks, S.C., McCoy, J.F.: Deconvolution with the $$\\ell 1$$ norm. Geophysics 44(1), 39\u201352 (1979)","journal-title":"Geophysics"},{"issue":"2","key":"9580_CR90","doi-asserted-by":"crossref","first-page":"1248","DOI":"10.1109\/TIT.2013.2290112","volume":"60","author":"AM Tillmann","year":"2013","unstructured":"Tillmann, A.M., Pfetsch, M.E.: The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans. Inf. Theory 60(2), 1248\u20131259 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"10","key":"9580_CR91","doi-asserted-by":"crossref","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","volume":"50","author":"JA Tropp","year":"2004","unstructured":"Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50(10), 2231\u20132242 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"9580_CR92","doi-asserted-by":"crossref","first-page":"1568","DOI":"10.1109\/TIT.2005.844057","volume":"51","author":"JA Tropp","year":"2005","unstructured":"Tropp, J.A.: Recovery of short, complex linear combinations via $$\\ell ^1$$ minimization. IEEE Trans. Inf. Theory 51(4), 1568\u20131570 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9580_CR93","doi-asserted-by":"crossref","unstructured":"Tropp, J.A.: Convex recovery of a structured signal from independent random linear measurements. In: G.E. Pfander (ed.) Sampling Theory, a Renaissance, Applied and Numerical Harmonic Analysis, pp. 67\u2013101. Birkh\u00e4user (2015)","DOI":"10.1007\/978-3-319-19749-4_2"},{"key":"9580_CR94","unstructured":"van\u00a0den Berg, E., Friedlander, M.P.: Spot \u2013 A Linear-Operator Toolbox. URL: http:\/\/www.cs.ubc.ca\/labs\/scl\/spot\/index.html (2013)"},{"key":"9580_CR95","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Y.C. Eldar, G.\u00a0Kutyniok (eds.) Compressed Sensing Theory and Applications, pp. 210\u2013268. Cambridge University Press (2012)","DOI":"10.1017\/CBO9780511794308.006"},{"key":"9580_CR96","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: Estimation in high dimensions: A geometric perspective. In: G.E. Pfander (ed.) Sampling Theory, a Renaissance, Applied and Numerical Harmonic Analysis, pp. 3\u201366. Birkh\u00e4user Cham (2015)","DOI":"10.1007\/978-3-319-19749-4_1"},{"key":"9580_CR97","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press (2018)","DOI":"10.1017\/9781108231596"},{"key":"9580_CR98","doi-asserted-by":"crossref","unstructured":"Wohlberg, B.: Efficient convolutional sparse coding. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7173\u20137177 (2014)","DOI":"10.1109\/ICASSP.2014.6854992"},{"issue":"6","key":"9580_CR99","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1109\/JPROC.2010.2044470","volume":"98","author":"J Wright","year":"2010","unstructured":"Wright, J., Ma, Y., Mairal, J., Sapiro, G., Huang, T.S., Yan, S.: Sparse representation for computer vision and pattern recognition. Proc. IEEE 98(6), 1031\u20131044 (2010)","journal-title":"Proc. IEEE"},{"issue":"2","key":"9580_CR100","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1109\/TPAMI.2008.79","volume":"31","author":"J Wright","year":"2008","unstructured":"Wright, J., Yang, A.Y., Ganesh, A., Sastry, S.S., Ma, Y.: Robust face recognition via sparse representation. IEEE Trans. Pattern Anal. Mach. Intell. 31(2), 210\u2013227 (2008)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"9580_CR101","unstructured":"Zuhovicki\u012d, S.: Remarks on problems in approximation theory. Mat. Zbirnik KDU pp. 169\u2013183 (1948). (Ukrainian)"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-022-09580-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-022-09580-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-022-09580-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T19:32:56Z","timestamp":1727897576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-022-09580-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,29]]},"references-count":101,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9580"],"URL":"https:\/\/doi.org\/10.1007\/s10208-022-09580-w","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"type":"print","value":"1615-3375"},{"type":"electronic","value":"1615-3383"}],"subject":[],"published":{"date-parts":[[2022,8,29]]},"assertion":[{"value":"9 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}