Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Sampling convex bodies: a random matrix approach

Author: Guillaume Aubrun
Journal: Proc. Amer. Math. Soc. 135 (2007), 1293-1303
MSC (2000): Primary 15A52, 52A20
Published electronically: November 14, 2006
MathSciNet review: 2276637
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. G. Aubrun.
    Random points in the unit ball of $ \ell_p^n$.
    Positivity, to appear.
  • 2. Z. D. Bai and Y. Q. Yin.
    Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix.
    Ann. Probab., 21(3):1275-1294, 1993. MR 1235416 (94j:60060)
  • 3. K. Ball and I. Perissinaki.
    The subindependence of coordinate slabs in $ \ell \sp n\sb p$ balls.
    Israel J. Math., 107:289-299, 1998. MR 1658571 (99k:52012)
  • 4. S. G. Bobkov and F. L. Nazarov.
    Large deviations of typical linear functionals on a convex body with unconditional basis.
    In Stochastic inequalities and applications, volume 56 of Progr. Probab., pages 3-13. Birkhäuser, Basel, 2003. MR 2073422 (2005f:52013)
  • 5. C. Borell.
    The Brunn-Minkowski inequality in Gauss space.
    Invent. Math., 30(2):207-216, 1975. MR 0399402 (53:3246)
  • 6. J. Bourgain.
    Random points in isotropic convex sets.
    In Convex geometric analysis (Berkeley, CA, 1996), volume 34 of Math. Sci. Res. Inst. Publ., pages 53-58. Cambridge Univ. Press, Cambridge, 1999.MR 1665576 (99m:60021)
  • 7. K. R. Davidson and S. J. Szarek.
    Local operator theory, random matrices and Banach spaces.
    In Handbook of the geometry of Banach spaces, Vol. I, pages 317-366. North-Holland, Amsterdam, 2001. MR 1863696 (2004f:47002a)
  • 8. S. Geman.
    A limit theorem for the norm of random matrices.
    Ann. Probab., 8(2):252-261, 1980. MR 0566592 (81m:60046)
  • 9. A. Giannopoulos.
    Notes on isotropic convex bodies (preprint)., 2003.
  • 10. A. Giannopoulos, M. Hartzoulaki, and A. Tsolomitis.
    Random points in isotropic unconditional convex bodies. J. London Math. Soc. (2) 72(3):779-798, 2005. MR 2190337
  • 11. D. Hensley.
    Slicing convex bodies--bounds for slice area in terms of the body's covariance.
    Proc. Amer. Math. Soc., 79(4):619-625, 1980. MR 0572315 (81j:52008)
  • 12. R. Kannan, L. Lovász, and M. Simonovits.
    Random walks and an $ O\sp *(n\sp 5)$ volume algorithm for convex bodies.
    Random Structures Algorithms, 11(1):1-50, 1997. MR 1608200 (99h:68078)
  • 13. V. F. Kolchin, B. A. Sevast$ '$yanov, and V. P. Chistyakov.
    Random allocations.
    V. H. Winston & Sons, Washington, D.C., 1978.
    Translated from Russian, translation edited by A. V. Balakrishnan, Scripta Series in Mathematics. MR 0471016 (57:10758b)
  • 14. R. Lata\la.
    Estimation of moments of sums of independent real random variables.
    Ann. Probab., 25(3):1502-1513, 1997. MR 1457628 (98h:60021)
  • 15. M. Ledoux.
    Deviation inequalities on largest eigenvalues., 2005.
  • 16. 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):491-523, 2005. MR 2146352
  • 17. V. D. Milman and A. Pajor.
    Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed $ n$-dimensional space.
    In Geometric aspects of functional analysis (1987-88), volume 1376 of Lecture Notes in Math., pages 64-104. Springer, Berlin, 1989.MR 1008717 (90g:52003)
  • 18. V. D. Milman and G. Schechtman.
    Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics.
    Springer-Verlag, Berlin, 1986.
    With an appendix by M. Gromov. MR 0856576 (87m:46038)
  • 19. G. Paouris.
    Concentration of mass on isotropic convex bodies.
    C. R. Math. Acad. Sci. Paris, 342(3):179-182, 2006. MR 2198189
  • 20. G. Pisier.
    The volume of convex bodies and Banach space geometry, volume 94 of Cambridge Tracts in Mathematics.
    Cambridge University Press, Cambridge, 1989. MR 1036275 (91d:52005)
  • 21. M. Rudelson.
    Random vectors in the isotropic position.
    J. Funct. Anal., 164(1):60-72, 1999. MR 1694526 (2000c:60059)
  • 22. 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''.
  • 23. 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(4):509-521, 1988. MR 0950344 (89g:60117)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 15A52, 52A20

Retrieve articles in all journals with MSC (2000): 15A52, 52A20

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

Keywords: Isotropic, random matrix, convex body, moments method
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
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society