SAMPLING CONVEX BODIES: A RANDOM MATRIX APPROACH

Marie Curie

Description

SAMPLING CONVEX BODIES: A RANDOM MATRIX APPROACH GUILLAUME AUBRUN Abstract. We prove the following result: for any ? > 0, only C(?)n sample points are enough to obtain (1+?)-approximation of the inertia ellipsoid of an unconditional convex body in Rn. Moreover, for any ? > 1, already ?n sample points give isomorphic approximation of the inertia ellipsoid. The proofs rely on an adaptation of the moments method from the Random Matrix Theory. Warning: this version differs from the (to be) published one (the proof of the main theorem is actually slightly simpler here). 1. Introduction and the main results Notation kept throughout the paper: The letters C, c, C ?... denote absolute positive constants, notably independent of the dimension. The value of such constants may change from line to line. Similarly, C(?) denotes a constant depending only on the parameter ?. The canonical basis of Rn is (e1, . . . , en), and the Euclidean norm and scalar product are denoted by | · | and ?·, ·?. The operator norm of a matrix is denoted by ? · ?. For a real symmetric matrix A, we write ?max(A) (respectively ?min(A)) for the largest (respectively smallest) eigenvalue of A.

• following general


• rudelson's inequality


• random matrix


• convex body


• urn when


• all indices


• when matrices involved


• denote absolute positive

Sujets

• Random matrix
• Convex body

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 10
• Langue: English

Extrait

SAMPLING CONVEX BODIES: A RANDOM MATRIX APPROACH

GUILLAUME AUBRUN

Abstract.We prove the following result: for anyε >0, onlyC(ε)nsample points are enough to n obtain(1+ε)-approximation of the inertia ellipsoid of an unconditional convex body inR. Moreover, for any >1, alreadynsample points give isomorphic approximation of the inertia ellipsoid. The proofs rely on an adaptation of the moments method from the Random Matrix Theory.

Warning: this version differs from the (to be) published one (the proof of the main theorem is actually slightly simpler here).

1.Introduction and the main results 0 Notation kept throughout the paper:The letters...C, c, C denote absolute positive constants, notably independent of the dimension. The value of such constants may change from line to line. n Similarly,C(ε)denotes a constant depending only on the parameterε. The canonical basis ofRis (e 1 , . . . , e n ), and the Euclidean norm and scalar product are denoted by||
andh
,
i. The operator norm of a matrix is denoted bykk
. For a real symmetric matrixA, we write max (A)(respectively  min (A)) for the largest (respectively smallest) eigenvalue ofA. Aconvex bodyis a convex compact n subset ofRwith non-empty interior. A convex bodyKis said to beunconditionalif it is invariant n under sign flips of the coordinates: for any= ( 1 , . . . ,  n )∈ {1,1}, (x 1 , . . . , x n )∈K⇐⇒( 1 x 1 , . . . ,  n x n )∈K. n We reserve the lettersX, Yto denote anR-valued random vector;X 1 , . . . , X N copies ofare i.i.d. X. IfEX= 0,Xis said to becentered. The random vectorXis said to beisotropicif it is centered n and for ally∈R 2 2 EhX, yi=|y|. This is equivalent to theinertia matrixEXXbeing is the identity matrix. We will consider the special case whenXis uniformly distributed on a convex bodyK. We will then say “inertia matrix 1 ofK”, “Kfor “inertia matrix ofis isotropic ”... X”, “XTheis isotropic”... . inertia ellipsoidofKis the unique ellipsoid with the same inertia matrix asKrecent results on isotropic convex bodies,. For a good reference is the survey [9]. Any random vector has an affine image which is isotropic, and this image is unique up to orthogonal transformation. Thus, for affinely invariant problems we can restrict ourselves to isotropic random vectors. If we do not know the law but onlyNsamples of the random vectorX, we can only consider theempirical inertia matrix N X 1 N A(X) :=X i X i . N i=1

1991Mathematics Subject Classification.Primary 15A52,52A20. Key words and phrases.Isotropic, random matrix, convex body, moments method. 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. 1 This terminology slightly differs from [16, 9] where isotropic convex bodies are normalized to have volume 1. 1