Sampling convex bodies: a random matrix approach
HTML articles powered by AMS MathViewer
- by Guillaume Aubrun PDF
- Proc. Amer. Math. Soc. 135 (2007), 1293-1303 Request permission
Abstract:
We prove the following result: for any $\varepsilon >0$, only $C(\varepsilon )n$ sample points are enough to obtain $(1+\varepsilon )$-approximation of the inertia ellipsoid of an unconditional convex body in $\mathbf {R}^n$. Moreover, for any $\rho >1$, already $\rho n$ sample points give isomorphic approximation of the inertia ellipsoid. The proofs rely on an adaptation of the moments method from Random Matrix Theory.References
- G. Aubrun. Random points in the unit ball of $\ell _p^n$. Positivity, to appear.
- Z. D. Bai and Y. Q. Yin, Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Ann. Probab. 21 (1993), no. 3, 1275–1294. MR 1235416
- Keith Ball and Irini Perissinaki, The subindependence of coordinate slabs in $l^n_p$ balls, Israel J. Math. 107 (1998), 289–299. MR 1658571, DOI 10.1007/BF02764013
- Sergey G. Bobkov and Fedor L. Nazarov, Large deviations of typical linear functionals on a convex body with unconditional basis, Stochastic inequalities and applications, Progr. Probab., vol. 56, Birkhäuser, Basel, 2003, pp. 3–13. MR 2073422
- Christer Borell, The Brunn-Minkowski inequality in Gauss space, Invent. Math. 30 (1975), no. 2, 207–216. MR 399402, DOI 10.1007/BF01425510
- Jean Bourgain, Random points in isotropic convex sets, Convex geometric analysis (Berkeley, CA, 1996) Math. Sci. Res. Inst. Publ., vol. 34, Cambridge Univ. Press, Cambridge, 1999, pp. 53–58. MR 1665576
- Kenneth R. Davidson and Stanislaw J. Szarek, Local operator theory, random matrices and Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 317–366. MR 1863696, DOI 10.1016/S1874-5849(01)80010-3
- Stuart Geman, A limit theorem for the norm of random matrices, Ann. Probab. 8 (1980), no. 2, 252–261. MR 566592
- A. Giannopoulos. Notes on isotropic convex bodies (preprint). http://eudoxos.math.uoa.gr/~apgiannop/isotropic-bodies.ps, 2003.
- A. Giannopoulos, M. Hartzoulaki, and A. Tsolomitis, Random points in isotropic unconditional convex bodies, J. London Math. Soc. (2) 72 (2005), no. 3, 779–798. MR 2190337, DOI 10.1112/S0024610705006897
- Douglas Hensley, Slicing convex bodies—bounds for slice area in terms of the body’s covariance, Proc. Amer. Math. Soc. 79 (1980), no. 4, 619–625. MR 572315, DOI 10.1090/S0002-9939-1980-0572315-5
- Ravi Kannan, László Lovász, and Miklós Simonovits, Random walks and an $O^*(n^5)$ volume algorithm for convex bodies, Random Structures Algorithms 11 (1997), no. 1, 1–50. MR 1608200, DOI 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X
- V. F. Kolchin, B. A. Sevast′yanov, and V. P. Chistyakov, Sluchaĭ nye razmeshcheniya, Teoriya Veroyatnosteĭ i Matematicheskaya Statistika. [Probability Theory and Mathematical Statistics], Izdat. “Nauka”, Moscow, 1976 (Russian). MR 0471015
- RafałLatała, Estimation of moments of sums of independent real random variables, Ann. Probab. 25 (1997), no. 3, 1502–1513. MR 1457628, DOI 10.1214/aop/1024404522
- M. Ledoux. Deviation inequalities on largest eigenvalues. http://www.lsp.ups-tlse.fr/Ledoux/Jerusalem.pdf, 2005.
- A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491–523. MR 2146352, DOI 10.1016/j.aim.2004.08.004
- V. D. Milman and A. Pajor, Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed $n$-dimensional space, Geometric aspects of functional analysis (1987–88), Lecture Notes in Math., vol. 1376, Springer, Berlin, 1989, pp. 64–104. MR 1008717, DOI 10.1007/BFb0090049
- Vitali D. Milman and Gideon Schechtman, Asymptotic theory of finite-dimensional normed spaces, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov. MR 856576
- Grigoris Paouris, Concentration of mass on isotropic convex bodies, C. R. Math. Acad. Sci. Paris 342 (2006), no. 3, 179–182 (English, with English and French summaries). MR 2198189, DOI 10.1016/j.crma.2005.11.018
- Gilles Pisier, The volume of convex bodies and Banach space geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. MR 1036275, DOI 10.1017/CBO9780511662454
- M. Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164 (1999), no. 1, 60–72. MR 1694526, DOI 10.1006/jfan.1998.3384
- S. Sodin. On the smallest singular value of a Bernoulli random matrix (following Bai and Yin). Appendix to a preprint by Artstein–Friedland–Milman “More geometric applications of Chernoff inequalities”.
- Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah, On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix, Probab. Theory Related Fields 78 (1988), no. 4, 509–521. MR 950344, DOI 10.1007/BF00353874
Additional Information
- Guillaume Aubrun
- Affiliation: Institut de Mathématiques de Jussieu, Projet Analyse Fonctionnelle, Université de Paris 6, 175 rue du Chevaleret, 75013 Paris, France
- Address at time of publication: Institut Camille Jordan, Université de Lyon 1, 21 Avenue Claude Bernard, 69622 Villeurbanne, Cedex France
- Received by editor(s): December 1, 2005
- Received by editor(s) in revised form: December 21, 2005
- Published electronically: November 14, 2006
- Additional Notes: This research was supported in part by the European Network PHD, FP6 Marie Curie Actions, MCRN-511953 and was done in part while the author was visiting the University of Athens.
- Communicated by: N. Tomczak-Jaegermann
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 135 (2007), 1293-1303
- MSC (2000): Primary 15A52, 52A20
- DOI: https://doi.org/10.1090/S0002-9939-06-08615-1
- MathSciNet review: 2276637