World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
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

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.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

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 Nn 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


    • [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, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [5] C. Borell, Convex measures on locally convex spaces, Ark. Mat. 12(1) (1974) 239–252. CrossrefGoogle Scholar
    • [6] O. Bousquet, A Bennett concentration inequality and its application to suprema of empirical processes, C. R. Math. 334(6) (2002) 495–500. Crossref, ISIGoogle Scholar
    • [7] S. Brazitikos, A. Giannopoulos, P. Valettas and B.-H. Vritsiou, Geometry of Isotropic Convex Bodies (American Mathematical Society, Providence, Rhode Island, 2014). CrossrefGoogle Scholar
    • [8] S. Brugiapaglia and B. Adcock, Robustness to unknown error in sparse regularization, IEEE Trans. Inform. Theory 64(10) (2018) 6638–6661. Crossref, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [14] D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52(4) (2006) 1289–1306. Crossref, ISIGoogle Scholar
    • [15] S. Foucart, Stability and robustness of 1-minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl. 441 (2014) 4–21. Crossref, ISIGoogle Scholar
    • [16] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis (Springer New York, 2013). CrossrefGoogle Scholar
    • [17] A. Giannopoulos and M. Hartzoulaki, Random spaces generated by vertices of the cube, Discrete Comput. Geom. 28(2) (2002) 255–273. Crossref, ISIGoogle Scholar
    • [18] E. D. Gluskin, Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces, Sb. Math. 64(1) (1989) 85. CrossrefGoogle Scholar
    • [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, ISIGoogle Scholar
    • [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, ISIGoogle 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] 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, ISIGoogle Scholar
    • [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). CrossrefGoogle Scholar
    • [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, ISIGoogle Scholar
    • [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. CrossrefGoogle Scholar
    • [29] S. Mendelson, Learning without concentration, J. ACM 62(3) (2015) 21:1–21:25. Crossref, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [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. CrossrefGoogle Scholar
    • [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, ISIGoogle Scholar
    • [35] G. Paouris, Concentration of mass on convex bodies, Geom. Funct. Anal. 16(5) (2006) 1021–1049. Crossref, ISIGoogle Scholar
    • [36] C. Schütt and E. Werner, The convex floating body, Math. Scand. 66(2) (1990) 275–290. CrossrefGoogle Scholar
    • [37] M. Talagrand, Sharper bounds for Gaussian and empirical processes, Ann. Prob. 22(1) (1994) 28–76. Crossref, ISIGoogle Scholar
    • [38] M. Talagrand, New concentration inequalities in product spaces, Invent. Math. 126(3) (1996) 505–563. Crossref, ISIGoogle Scholar
    • [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, ISIGoogle Scholar
    • [40] P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10(1) (2010) 1–13. Crossref, ISIGoogle Scholar
    Remember to check out the Most Cited Articles!

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