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
×

System Upgrade on Tue, May 28th, 2024 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

    https://doi.org/10.1142/S0219199721500565Cited by:5 (Source: Crossref)

    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

    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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • [5] C. Borell, Convex measures on locally convex spaces, Ark. Mat. 12(1) (1974) 239–252. Crossref, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • [14] D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52(4) (2006) 1289–1306. Crossref, Web of ScienceGoogle Scholar
    • [15] S. Foucart, Stability and robustness of 1-minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl. 441 (2014) 4–21. Crossref, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • [35] G. Paouris, Concentration of mass on convex bodies, Geom. Funct. Anal. 16(5) (2006) 1021–1049. Crossref, Web of ScienceGoogle Scholar
    • [36] C. Schütt and E. Werner, The convex floating body, Math. Scand. 66(2) (1990) 275–290. Crossref, Web of ScienceGoogle Scholar
    • [37] M. Talagrand, Sharper bounds for Gaussian and empirical processes, Ann. Prob. 22(1) (1994) 28–76. Crossref, Web of ScienceGoogle Scholar
    • [38] M. Talagrand, New concentration inequalities in product spaces, Invent. Math. 126(3) (1996) 505–563. Crossref, Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • [40] P. Wojtaszczyk, Stability and instance optimality for Gaussian measurements in compressed sensing, Found. Comput. Math. 10(1) (2010) 1–13. Crossref, Web of ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

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