On the geometry of polytopes generated by heavy-tailed random vectors
Abstract
We study the geometry of centrally symmetric random polytopes, generated by independent copies of a random vector taking values in . We show that under minimal assumptions on , for and with high probability, the polytope contains a deterministic set that is naturally associated with the random vector — namely, the polar of a certain floating body. This solves the long-standing question on whether such a random polytope contains a canonical body. Moreover, by identifying the floating bodies associated with various random vectors, we recover the estimates that were obtained previously, and thanks to the minimal assumptions on , we derive estimates in cases that were out of reach, involving random polytopes generated by heavy-tailed random vectors (e.g., when is -stable or when has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing — noise blind sparse recovery.
References
- [1] , Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, J. Am. Math. Soc. 23(2) (2010) 535–561. Crossref, ISI, Google Scholar
- [2] , Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constr. Approx. 34 (2011) 61–88. Crossref, ISI, Google Scholar
- [3] ,
Random polytopes, convex bodies, and approximation , in Stochastic Geometry, Volume 1892 ofLecture Notes in Mathematics (Springer, Berlin, 2007), pp. 77–118. Google Scholar - [4] , Learnability and the Vapnik–Chervonenkis dimension, J. ACM 36 (1989) 929–965. Crossref, ISI, Google Scholar
- [5] , Convex measures on locally convex spaces, Ark. Mat. 12(1) (1974) 239–252. Crossref, Google Scholar
- [6] , A Bennett concentration inequality and its application to suprema of empirical processes, C. R. Math. 334(6) (2002) 495–500. Crossref, ISI, Google Scholar
- [7] , Geometry of Isotropic Convex Bodies (American Mathematical Society, Providence, Rhode Island, 2014). Crossref, Google Scholar
- [8] , Robustness to unknown error in sparse regularization, IEEE Trans. Inform. Theory 64(10) (2018) 6638–6661. Crossref, ISI, Google Scholar
- [9] , Interactions Between Compressed Sensing Random Matrices and High Dimensional Geometry, Volume 37 of
Panoramas and Syntheses (Société Mathématique de France, Paris, 2012). Google Scholar - [10] , Asymptotic shape of a random polytope in a convex body, J. Funct. Anal. 257(9) (2009) 2820–2839. Crossref, ISI, Google Scholar
- [11] , Decoupling. From dependence to independence. Randomly Stopped Processes, U-Statistics and Processes, Martingales and Beyond (Springer Science & Business Media, 2012). Google Scholar
- [12] , Instance-optimality in probability with an -minimization decoder, Appl. Comput. Harmon. Anal. 27(3) (2009) 275–288. Crossref, ISI, Google Scholar
- [13] , On the gap between restricted isometry properties and sparse recovery conditions, IEEE Trans. Inform. Theory 64(8) (2018) 5478–5487. Crossref, ISI, Google Scholar
- [14] , Compressed sensing, IEEE Trans. Inform. Theory 52(4) (2006) 1289–1306. Crossref, ISI, Google Scholar
- [15] , Stability and robustness of -minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl. 441 (2014) 4–21. Crossref, ISI, Google Scholar
- [16] , A Mathematical Introduction to Compressive Sensing,
Applied and Numerical Harmonic Analysis (Springer New York, 2013). Crossref, Google Scholar - [17] , Random spaces generated by vertices of the cube, Discrete Comput. Geom. 28(2) (2002) 255–273. Crossref, ISI, Google Scholar
- [18] , Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces, Sb. Math. 64(1) (1989) 85. Crossref, Google Scholar
- [19] .
Random polytopes obtained by matrices with heavy tailed entries , Commun. Contemp. Math. 22 (2020) 1950027. Link, ISI, Google Scholar - [20] ,
Concentration inequalities and geometry of convex bodies , in Analytical and Probabilistic Methods in the Geometry of Convex Bodies, Volume 2 ofIMPAN Lecture Notes (Polish Acad. Sci. Inst. Math., Warsaw, 2014), pp. 9–86. Google Scholar - [21] , Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik–Chervonenkis dimension, J. Combinat. Theory, Ser. A 69 (1995) 217–232. Crossref, ISI, Google Scholar
- [22] F. Krahmer, C. Kümmerle and H. Rauhut, A quotient property for matrices with heavy-tailed entries and its application to noise-blind compressed sensing, preprint (2018), arXiv:1806.04261. Google Scholar
- [23] , Suprema of chaos processes and the restricted isometry property, Comm. Pure Appl. Math. 67(11) (2014) 1877–1904. Crossref, ISI, Google Scholar
- [24] , Random Series and Stochastic Integrals: Single and Multiple. Probability and its Applications (Birkhäuser Boston, Inc., Boston, MA, 1992). Crossref, Google Scholar
- [25] . Probability in Banach Spaces,
Classics in Mathematics . (Springer-Verlag, Berlin, 2011). Isoperimetry and Processes, Reprint of the 1991 Edition. Google Scholar - [26] , Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195(2) (2005) 491–523. Crossref, ISI, Google Scholar
- [27] , Blaschke-Santaló inequalities, J. Diff. Geom. 45 (1997) 1–16. Google Scholar
- [28] ,
A few notes on statistical learning theory , in Advanced Lectures on Machine Learning, eds. S. MendelsonA. Smola, Vol. 2600 (Springer, 2003), pp. 1–40. Crossref, Google Scholar - [29] , Learning without concentration, J. ACM 62(3) (2015) 21:1–21:25. Crossref, ISI, Google Scholar
- [30] S. Mendelson, On the geometry of random polytopes, preprint (2019), arXiv:1902.01664. Google Scholar
- [31] , Sparse recovery under weak moment assumptions, J. Eur. Math. Soc. 19(3) (2017) 881–904. Crossref, ISI, Google Scholar
- [32] ,
Characterizations of affinely-rotation-invariant log-concave measures by section-centroid location , in Geometric Aspects of Functional Analysis (1989–90), Volume 1469 ofLecture Notes in Mathematics (Springer, Berlin, 1991), pp. 145–152. Crossref, Google Scholar - [33] , Foundations of Machine Learning (MIT Press, 2012). Google Scholar
- [34] , The distribution of Rademacher sums, Proc. Amer. Math. Soc. 109(2) (1990) 517–522. Crossref, ISI, Google Scholar
- [35] , Concentration of mass on convex bodies, Geom. Funct. Anal. 16(5) (2006) 1021–1049. Crossref, ISI, Google Scholar
- [36] , The convex floating body, Math. Scand. 66(2) (1990) 275–290. Crossref, Google Scholar
- [37] , Sharper bounds for Gaussian and empirical processes, Ann. Prob. 22(1) (1994) 28–76. Crossref, ISI, Google Scholar
- [38] , New concentration inequalities in product spaces, Invent. Math. 126(3) (1996) 505–563. Crossref, ISI, Google Scholar
- [39] , On the uniform convergence of relative frequencies of events to their probabilities, Theor. Probab. Appl. 16 (1971) 264–280. Crossref, ISI, Google Scholar
- [40] , Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10(1) (2010) 1–13. Crossref, ISI, Google Scholar
Remember to check out the Most Cited Articles! |
---|
Be inspired by these NEW Mathematics books for inspirations & latest information in your research area! |