Sampling convex bodies: a random matrix approach

Aubrun, Guillaume

doi:10.1090/S0002-9939-06-08615-1

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