Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

Sampling convex bodies: a random matrix approach

Author(s): Guillaume Aubrun
Journal: Proc. Amer. Math. Soc. 135 (2007), 1293-1303.
MSC (2000): Primary 15A52, 52A20
Posted: November 14, 2006
MathSciNet review: 2276637
Retrieve article in: 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:

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).
http://eudoxos.math.uoa.gr/~apgiannop/isotropic-bodies.ps, 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. Sevastyanov, 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 $\l$ a.
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.
http://www.lsp.ups-tlse.fr/Ledoux/Jerusalem.pdf, 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 -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)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|