×

zbMATH — the first resource for mathematics

Sparse recovery under weak moment assumptions. (English) Zbl 1414.62135
The paper is focused on data acquisition framework, addressing the idea of compressed sensing (high-dimensional data being described using low-dimensional approximating structures involving randomness). The identically and independently distributed random vector satisfying weak moment hypothesis are proved to be usable as measurement vectors in compressed sensing, the number of measurements for exact reconstruction being the same as the best possible estimate. The necessity of the moment condition up to a log log factor is also proved. In the end, two conditions are analyzed in the noisy setup (compatibility and restricted eigenvalue condition) and also the properties of neighbourly random polytopes.

MSC:
62G08 Nonparametric regression and quantile regression
62J05 Linear regression; mixed models
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adamczak, R., Litvak, A. E., Pajor, A., Tomczak-Jaegermann, N.: Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Constr. Approx. 34, 61-88 (2011)Zbl 1222.52009 MR 2796091 · Zbl 1222.52009
[2] Ball, K.: Cube slicing in Rn. Proc. Amer. Math. Soc. 97, 465-473 (1986)Zbl 0601.52005 MR 0840631 · Zbl 0601.52005
[3] Bickel, P. J., Ritov, Y., Tsybakov, A. B.: Simultaneous analysis of LASSO and Dantzig selector. Ann. Statist. 37, 1705-1732 (2009)Zbl 1173.62022 MR 2533469 · Zbl 1173.62022
[4] Birg´e, L., Massart, P.: Gaussian model selection. J. Eur. Math. Soc. 3, 203-268 (2001) Zbl 1037.62001 MR 1848946 · Zbl 1037.62001
[5] Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford Univ. Press (2013)Zbl 1279.60005 MR 3185193 · Zbl 1279.60005
[6] B¨uhlmann, P., van de Geer, S. A.: Statistics for High-Dimensional Data. Springer Ser. Statist., Springer, Heidelberg (2011)Zbl 1273.62015 MR 2807761
[7] Cand‘es, E. J.: The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris 346, 589-592 (2008)Zbl 1153.94002 MR 2412803 · Zbl 1153.94002
[8] Cand‘es, E. J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52, 489-509 (2006)Zbl 1231.94017 MR 2236170 · Zbl 1231.94017
[9] Cand‘es, E. J., Romberg, J. K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 59, 1207-1223 (2006)Zbl 1098.94009 MR 2230846 · Zbl 1098.94009
[10] Cand‘es, E. J., Tao, T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inform. Theory 52, 5406-5425 (2006)Zbl 1309.94033 MR 2300700 · Zbl 1309.94033
[11] Cand‘es, E. J., Tao, T.: The Dantzig selector: statistical estimation when p is much larger than n. Ann. Statist. 35, 2313-2351 (2007)Zbl 1139.62019 MR 2382644 · Zbl 1139.62019
[12] Chafa¨ı, D., Gu´edon, O., Lecu´e, G., Pajor, A.: Interactions between Compressed Sensing Random Matrices and High Dimensional Geometry. Panoramas Synth‘eses 37, Soc. Math. France, Paris (2012)Zbl 06208972 MR 3113826
[13] Chen, S. S., Donoho, D. L., Saunders, M. A.: Atomic decomposition by basis pursuit. SIAM Rev. 43, 129-159 (2001)Zbl 0919.94002 MR 1639094 · Zbl 0979.94010
[14] Claerbout, J. F., Muir, F.: Robust modeling with erratic data. Geophysics 38, 826-844 (1973) Sparse recovery under weak moment assumptions903
[15] de la Pe˜na, V. H., Gin´e, E.: Decoupling. Probab. Appl. (New York), Springer, New York (1999) Zbl 0918.60021 MR 1666908
[16] Donoho, D. L.: Neighborly polytopes and sparse solutions of underdetermined linear equations. Technical report, Department of Statistics, Stanford Univ. (2005)
[17] Donoho, D. L.: Compressed sensing. IEEE Trans. Inform. Theory 52, 1289-1306 (2006) Zbl 1288.94016 MR 2241189 · Zbl 1288.94016
[18] Donoho, D. L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via l1minimization. Proc. Nat. Acad. Sci. USA 100, 2197-2202 (2003) Zbl 1064.94011 MR 1963681 · Zbl 1064.94011
[19] Donoho, D. L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory 47, 2845-2862 (2001)Zbl 1019.94503 MR 1872845 · Zbl 1019.94503
[20] Donoho, D. L., Logan, B. F.: Signal recovery and the large sieve. SIAM J. Appl. Math. 52, 577-591 (1992)Zbl 0768.42001 MR 1154788 · Zbl 0768.42001
[21] Dudley, R. M.: Central limit theorems for empirical measures. Ann. Probab. 6, 899-929 (1978)Zbl 0404.60016 MR 0512411 · Zbl 0404.60016
[22] Foucart, S.: Stability and robustness of ‘1-minimizations with Weibull matrices and redundant dictionaries. Linear Algebra Appl. 441, 4-21 (2014)Zbl 1332.94042 MR 3134335 · Zbl 1332.94042
[23] Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Appl. Numer. Harmonic Anal., Birkh¨auser/Springer, New York (2013)Zbl 1315.94002 MR 3100033 · Zbl 1315.94002
[24] Koltchinskii, V.: Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. Lecture Notes in Math. 2033, Springer, Heidelberg (2011)Zbl 1223.91002 MR 2829871 · Zbl 1223.91002
[25] Koltchinskii, V., Mendelson, S.: Bounding the smallest singular value of a random matrix without concentration. Int. Math. Res. Notices 2015, 12991-13008Zbl 1331.15027 MR 3431642 · Zbl 1331.15027
[26] Latała, R.: Estimation of moments of sums of independent real random variables. Ann. Probab. 25, 1502-1513 (1997)Zbl 0885.60011 MR 1457628 · Zbl 0885.60011
[27] Ledoux, M., Talagrand, M.: Probability in Banach Spaces. Ergeb. Math. Grenzgeb. (3) 23, Springer, Berlin (1991)Zbl 0748.60004 MR 1102015 · Zbl 0748.60004
[28] Logan, B.: Properties of high-pass signals. PhD thesis, Columbia Univ., New York (1965)
[29] Massart, P.: Concentration Inequalities and Model Selection. Lecture Notes in Math. 1896, Springer, Berlin (2007)Zbl 1170.60006 MR 2319879 · Zbl 1170.60006
[30] Mendelson, S.: Learning without concentration. J. ACM 62, no. 3, art. 21, 25 pp. (2015) Zbl 1333.68232 MR 3367000 · Zbl 1333.68232
[31] Mendelson, S.: A remark on the diameter of random sections of convex bodies. In: Geometric Aspects of Functional Analysis (GAFA Seminar Notes), Lecture Notes in Math. 2116, Springer, 395-404 (2014)Zbl 1317.52011 MR 3364699 · Zbl 1317.52011
[32] Mendelson, S., Pajor, A., Tomczak-Jaegermann, N.: Uniform uncertainty principle for Bernoulli and subgaussian ensembles. Constr. Approx. 28, 277-289 (2008)Zbl 1230.46011 MR 2453368 · Zbl 1230.46011
[33] Natarajan, B. K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227- 234 (1995)Zbl 0827.68054 MR 1320206 · Zbl 0827.68054
[34] Oliveira, R. I.: The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties. Probab. Theory Related Fields 166, 1175-1194 (2016)Zbl 06657184 MR 3568047 · Zbl 1360.60075
[35] Raskutti, G., Wainwright, M. J., Yu, B.: Restricted eigenvalue properties for correlated Gaussian designs. J. Machine Learn. Res. 11, 2241-2259 (2010)Zbl 1242.62071 MR 2719855 · Zbl 1242.62071
[36] Rogozin, B. A.: An estimate for the maximum of the convolution of bounded densities. Teor. Veroyatnost. i Primenen. 32, 53-61 (1987) (in Russian)Zbl 0624.60024 MR 0890930 904Guillaume Lecu´e, Shahar Mendelson · Zbl 0624.60024
[37] Rudelson, M., Vershynin, R: On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math. 61, 1025-1045 (2008)Zbl 1149.94010 MR 2417886 · Zbl 1149.94010
[38] Rudelson, M., Vershynin, R.: Small ball probabilities for linear images of high dimensional distributions. Int. Math. Res. Notices 2015, 9594-9617Zbl 1330.60029 MR 3431603 · Zbl 1330.60029
[39] Rudelson, M., Zhou, S.: Reconstruction from anisotropic random measurements. IEEE Trans. Inform. Theory 59, 3434-3447 (2013)MR 3061256 · Zbl 1364.94158
[40] Santosa, F., Symes, W. W.: Linear inversion of band-limited reflection seismograms. SIAM J. Sci. Statist. Comput. 7, 1307-1330 (1986)Zbl 0602.73113 MR 0857796 · Zbl 0602.73113
[41] Srivastava, N., Vershynin, R.: Covariance estimation for distributions with 2 + ε moments. Ann. Probab. 41, 3081-3111 (2013)Zbl 1293.62121 MR 3127875 · Zbl 1293.62121
[42] Taylor, H. L., Banks, S. C., McCoy, J. F.: Deconvolution with the l1norm. Geophysics 44, 39-52 (1979)
[43] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B 58, 267-288 (1996)Zbl 0850.62538 MR 1379242 · Zbl 0850.62538
[44] van de Geer, S. A.: The deterministic Lasso.http://stat.ethz.ch/˜geer/lasso.pdf · Zbl 06982337
[45] van de Geer, S. A.: Weakly decomposable regularization penalties and structured sparsity. Scand. J. Statist. 41, 72-86 (2014)Zbl 1349.62325 MR 3181133 · Zbl 1349.62325
[46] van de Geer, S. A., Muro, A.: On higher order isotropy conditions and lower bounds for sparse quadratic forms. Electron. J. Statist. 8, 3031-3061 (2014)Zbl 1308.62148 MR 3301300 · Zbl 1308.62148
[47] van der Vaart, A. W., Wellner, J. A.: Weak Convergence and Empirical Processes. Springer Ser. Statist., Springer, New York (1996)Zbl 0862.60002 MR 1385671 · Zbl 0862.60002
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.