No Access

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

Olivier Guédon

LAMA, Univ Gustave Eiffel, UPEM, Univ Paris Est Creteil, CNRS, F-77447, Marne-la-Vallée, France

E-mail Address: [email protected]

Search for more papers by this author

Felix Krahmer

Department of Mathematics, Technical University of Munich, 85748 Garching bei München, Germany

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

Christian Kümmerle

Department of Applied Mathematics & Statistics, Johns Hopkins University, Baltimore, United States

E-mail Address: [email protected]

Search for more papers by this author

Shahar Mendelson

LPSM, Sorbonne University, Paris, France

Mathematical Sciences Institute, The Australian National University, Canberra, Australia

E-mail Address: [email protected]

Search for more papers by this author

and

Holger Rauhut

Chair for Mathematics of Information Processing, RWTH Aachen University, 52056 Aachen, Germany

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0219199721500565Cited by:1

Abstract

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.

Keywords:

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, Google 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, ISI, Google 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, ISI, Google Scholar
[5] C. Borell, Convex measures on locally convex spaces, Ark. Mat. 12(1) (1974) 239–252. Crossref, Google 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, ISI, Google Scholar
[7] S. Brazitikos, A. Giannopoulos, P. Valettas and B.-H. Vritsiou, Geometry of Isotropic Convex Bodies (American Mathematical Society, Providence, Rhode Island, 2014). Crossref, Google Scholar
[8] S. Brugiapaglia and B. Adcock, Robustness to unknown error in sparse regularization, IEEE Trans. Inform. Theory 64(10) (2018) 6638–6661. Crossref, ISI, Google 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, ISI, Google 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, ISI, Google 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, ISI, Google Scholar
[14] D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52(4) (2006) 1289–1306. Crossref, ISI, Google Scholar
[15] S. Foucart, Stability and robustness of $ℓ_{1}$ -minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl. 441 (2014) 4–21. Crossref, ISI, Google Scholar
[16] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis (Springer New York, 2013). Crossref, Google Scholar
[17] A. Giannopoulos and M. Hartzoulaki, Random spaces generated by vertices of the cube, Discrete Comput. Geom. 28(2) (2002) 255–273. Crossref, ISI, Google 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. Crossref, Google 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, ISI, Google 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, 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] 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, Google 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). Crossref, Google 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, ISI, Google 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. Crossref, Google Scholar
[29] S. Mendelson, 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] S. Mendelson and G. Lecué, Sparse recovery under weak moment assumptions, J. Eur. Math. Soc. 19(3) (2017) 881–904. Crossref, ISI, Google 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. Crossref, Google 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, ISI, Google Scholar
[35] G. Paouris, Concentration of mass on convex bodies, Geom. Funct. Anal. 16(5) (2006) 1021–1049. Crossref, ISI, Google Scholar
[36] C. Schütt and E. Werner, The convex floating body, Math. Scand. 66(2) (1990) 275–290. Crossref, Google Scholar
[37] M. Talagrand, Sharper bounds for Gaussian and empirical processes, Ann. Prob. 22(1) (1994) 28–76. Crossref, ISI, Google Scholar
[38] M. Talagrand, New concentration inequalities in product spaces, Invent. Math. 126(3) (1996) 505–563. Crossref, ISI, Google 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, ISI, Google Scholar
[40] P. Wojtaszczyk, 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!

Vol. 24, No. 03

Metrics

History

Received 9 February 2021

Accepted 22 March 2021

Published: 31 May 2021

Keywords

PDF download

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

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

Abstract

References

Recommended