• Search

×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

### System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
No Access

# On the geometry of polytopes generated by heavy-tailed random vectors

We study the geometry of centrally symmetric random polytopes, generated by $N$ independent copies of a random vector $X$ taking values in $ℝn$. We show that under minimal assumptions on $X$, for $N≳n$ 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 $X$, we derive estimates in cases that were out of reach, involving random polytopes generated by heavy-tailed random vectors (e.g., when $X$ is $q$-stable or when $X$ has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing — noise blind sparse recovery.

AMSC: primary: 52A22, primary: 46B06, primary: 60B20, primary: 65K10, secondary: 52A23, secondary: 46B09, secondary: 15B52

## References

• [1] R. Adamczak, A. Litvak, A. Pajor and N. Tomczak-Jaegermann, 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
• [2] R. Adamczak, A. E. Litvak, A. Pajor and N. Tomczak-Jaegermann, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constr. Approx. 34 (2011) 61–88. Crossref, ISI
• [3] I. Bárány, Random polytopes, convex bodies, and approximation, in Stochastic Geometry, Volume 1892 of Lecture Notes in Mathematics (Springer, Berlin, 2007), pp. 77–118. Google Scholar
• [4] A. Blumer, A. Ehrenfeucht, D. Haussler and M. K. Warmuth, Learnability and the Vapnik–Chervonenkis dimension, J. ACM 36 (1989) 929–965. Crossref, ISI
• [5] C. Borell, Convex measures on locally convex spaces, Ark. Mat. 12(1) (1974) 239–252. Crossref
• [6] O. Bousquet, A Bennett concentration inequality and its application to suprema of empirical processes, C. R. Math. 334(6) (2002) 495–500. Crossref, ISI
• [7] S. Brazitikos, A. Giannopoulos, P. Valettas and B.-H. Vritsiou, Geometry of Isotropic Convex Bodies (American Mathematical Society, Providence, Rhode Island, 2014). Crossref
• [8] S. Brugiapaglia and B. Adcock, Robustness to unknown error in sparse regularization, IEEE Trans. Inform. Theory 64(10) (2018) 6638–6661. Crossref, ISI
• [9] D. Chafaï, O. Guédon, G. Lecué and A. Pajor, 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] N. Dafnis, A. Giannopoulos and A. Tsolomitis, Asymptotic shape of a random polytope in a convex body, J. Funct. Anal. 257(9) (2009) 2820–2839. Crossref, ISI
• [11] V. De la Peña and E. Giné, Decoupling. From dependence to independence. Randomly Stopped Processes, U-Statistics and Processes, Martingales and Beyond (Springer Science & Business Media, 2012). Google Scholar
• [12] R. DeVore, G. Petrova and P. Wojtaszczyk, Instance-optimality in probability with an $ℓ1$-minimization decoder, Appl. Comput. Harmon. Anal. 27(3) (2009) 275–288. Crossref, ISI
• [13] S. Dirksen, G. Lecué and H. Rauhut, On the gap between restricted isometry properties and sparse recovery conditions, IEEE Trans. Inform. Theory 64(8) (2018) 5478–5487. Crossref, ISI
• [14] D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52(4) (2006) 1289–1306. Crossref, ISI
• [15] S. Foucart, Stability and robustness of $ℓ1$-minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl. 441 (2014) 4–21. Crossref, ISI
• [16] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis (Springer New York, 2013). Crossref
• [17] A. Giannopoulos and M. Hartzoulaki, Random spaces generated by vertices of the cube, Discrete Comput. Geom. 28(2) (2002) 255–273. Crossref, ISI
• [18] E. D. Gluskin, Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces, Sb. Math. 64(1) (1989) 85. Crossref
• [19] O. Guédon, A. Litvak and K. Tatarko. Random polytopes obtained by matrices with heavy tailed entries, Commun. Contemp. Math. 22 (2020) 1950027. Link, ISI
• [20] O. Guédon, P. Nayar and T. Tkocz, Concentration inequalities and geometry of convex bodies, in Analytical and Probabilistic Methods in the Geometry of Convex Bodies, Volume 2 of IMPAN Lecture Notes (Polish Acad. Sci. Inst. Math., Warsaw, 2014), pp. 9–86. Google Scholar
• [21] D. Haussler, 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
• [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] F. Krahmer, S. Mendelson and H. Rauhut, Suprema of chaos processes and the restricted isometry property, Comm. Pure Appl. Math. 67(11) (2014) 1877–1904. Crossref, ISI
• [24] S. Kwapień and W. A. Woyczyński, Random Series and Stochastic Integrals: Single and Multiple. Probability and its Applications (Birkhäuser Boston, Inc., Boston, MA, 1992). Crossref
• [25] M. Ledoux and M. Talagrand. Probability in Banach Spaces, Classics in Mathematics. (Springer-Verlag, Berlin, 2011). Isoperimetry and Processes, Reprint of the 1991 Edition. Google Scholar
• [26] A. Litvak, A. Pajor, M. Rudelson and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195(2) (2005) 491–523. Crossref, ISI
• [27] E. Lutwak and G. Zhang, Blaschke-Santaló inequalities, J. Diff. Geom. 45 (1997) 1–16. Google Scholar
• [28] S. Mendelson, 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
• [29] S. Mendelson, Learning without concentration, J. ACM 62(3) (2015) 21:1–21:25. Crossref, ISI
• [30] S. Mendelson, On the geometry of random polytopes, preprint (2019), arXiv:1902.01664. Google Scholar
• [31] S. Mendelson and G. Lecué, Sparse recovery under weak moment assumptions, J. Eur. Math. Soc. 19(3) (2017) 881–904. Crossref, ISI
• [32] M. Meyer and S. Reisner, Characterizations of affinely-rotation-invariant log-concave measures by section-centroid location, in Geometric Aspects of Functional Analysis (1989–90), Volume 1469 of Lecture Notes in Mathematics (Springer, Berlin, 1991), pp. 145–152. Crossref
• [33] M. Mohri, A. Rostamizadeh and A. Talwalkar, Foundations of Machine Learning (MIT Press, 2012). Google Scholar
• [34] S. J. Montgomery-Smith, The distribution of Rademacher sums, Proc. Amer. Math. Soc. 109(2) (1990) 517–522. Crossref, ISI
• [35] G. Paouris, Concentration of mass on convex bodies, Geom. Funct. Anal. 16(5) (2006) 1021–1049. Crossref, ISI
• [36] C. Schütt and E. Werner, The convex floating body, Math. Scand. 66(2) (1990) 275–290. Crossref
• [37] M. Talagrand, Sharper bounds for Gaussian and empirical processes, Ann. Prob. 22(1) (1994) 28–76. Crossref, ISI
• [38] M. Talagrand, New concentration inequalities in product spaces, Invent. Math. 126(3) (1996) 505–563. Crossref, ISI
• [39] V. N. Vapnik and A. Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theor. Probab. Appl. 16 (1971) 264–280. Crossref, ISI
• [40] P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10(1) (2010) 1–13. Crossref, ISI
Remember to check out the Most Cited Articles!

Be inspired by these NEW Mathematics books for inspirations & latest information in your research area!