C. R. Acad. Sci. Paris, Ser. I 352 (2014) 431–434 Contents lists available at S

C. R. Acad. Sci. Paris, Ser. I 352 (2014) 431–434 Contents lists available at ScienceDirect C. R. Acad. Sci. Paris, Ser. I www.sciencedirect.com Functional analysis/Probability theory Restricted isometry property for random matrices with heavy-tailed columns Propriété d’isométrie restreinte de matrices aléatoires dont les colonnes sont à queues lourdes Olivier Guédon a, Alexander E. Litvak b, Alain Pajor a, Nicole Tomczak-Jaegermann b,1 a Université Paris-Est, Laboratoire d’analyse et de mathématiques appliquées (UMR 8050), UPEMLV, 77454 Marne-la-Vallée, France b Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada a r t i c l e i n f o a b s t r a c t Article history: Received 23 January 2014 Accepted 6 March 2014 Available online 27 March 2014 Presented by Gilles Pisier Let A be a matrix whose columns X1,..., XN are independent random vectors in Rn. Assume that p-th moments of ⟨Xi,a⟩, a ∈Sn−1, i ⩽N, are uniformly bounded. For p > 4, we prove that with high probability A has the Restricted Isometry Property (RIP) provided that Euclidean norms |Xi| are concentrated around √ n and that the covariance matrix is well approximated by the empirical covariance matrix provided that maxi |Xi| ⩽C(nN)1/4. We also provide estimates for RIP when Eφ(|⟨Xi,a⟩|) ⩽1 for φ(t) = (1/2) exp(tα), with α ∈(0, 2]. © 2014 Published by Elsevier Masson SAS on behalf of Académie des sciences. r é s u m é Soit A une matrice dont les colonnes X1,..., XN sont des vecteurs indépendants de Rn. On suppose que les moments d’ordre p des ⟨Xi,a⟩, a ∈Sn−1, 1 ⩽i ⩽N sont uniformément bornés pour p > 4. On démontre que si les normes euclidiennes des |Xi| se concentrent autour de √ n, la matrice A vérifie une propriété d’isométrie restreinte avec grande probabilité et que si maxi |Xi| ⩽C(nN)1/4, la matrice de covariance empirique est une bonne approximation de la matrice de covariance. On démontre aussi une propriété d’isométrie restreinte quand Eφ(|⟨Xi,a⟩|) ⩽1 pour tout a ∈Sn−1, 1 ⩽i ⩽N avec φ(t) = (1/2) exp(tα) et α ∈(0, 2]. © 2014 Published by Elsevier Masson SAS on behalf of Académie des sciences. E-mail addresses: olivier.guedon@u-pem.fr (O. Guédon), aelitvak@gmail.com (A.E. Litvak), alain.pajor@u-pem.fr (A. Pajor), nicole.tomczak@ualberta.ca (N. Tomczak-Jaegermann). 1 This author holds the Canada Research Chair in Geometric Analysis. http://dx.doi.org/10.1016/j.crma.2014.03.005 1631-073X/© 2014 Published by Elsevier Masson SAS on behalf of Académie des sciences. 432 O. Guédon et al. / C. R. Acad. Sci. Paris, Ser. I 352 (2014) 431–434 1. Introduction Our two main results go in two parallel directions: the Restricted Isometry Property abbreviated as RIP and a question of Kannan–Lovász–Simonovits about an approximation of a covariance matrix by empirical covariance matrices referred to below as KLS problem. In this note, X1,..., XN denote independent random vectors in Rn satisfying for some function φ ∀1 ⩽i ⩽N ∀a ∈Sn−1 Eφ  ⟨Xi,a⟩   ⩽1. (1) We will focus on two choices of the function φ: φ(t) = t p, with p > 4, or φ(t) = (1/2) exp(tα), with α ∈(0, 2]. The n × N matrix whose columns are X1,..., XN will be denoted by A. As usual, C, C1, . . . , c, c1, . . . will always denote absolute positive constants, whose values may change from line to line. 2. Restricted Isometry Property (RIP) We first recall the definition of the RIP, which was introduced in [6], in order to study the exact reconstruction problem by ℓ1 minimization. It is noteworthy that the problem of reconstruction can be reformulated in terms of convex geometry, namely in terms of neighborliness of the symmetric convex hull of X1,..., XN, as was shown in [7]. Let T be an arbitrary n × N matrix. For 1 ⩽m ⩽N, the isometry constant of T is defined as the smallest number δm = δm(T) satisfying (1 −δm)|z|2 ⩽|T z|2 ⩽(1 + δm)|z|2, for z ∈RN with  supp(z)   ⩽m. (2) Let δ ∈(0, 1). The matrix T is said to satisfy the RIP of order m with parameter δ if 0 ⩽δm(T) < δ. Returning to the vectors X1,..., XN (independent and satisfying (1)) the concentration of |Xi|’s around their average is controlled by the function P(θ) := P  max i⩽N     |Xi|2 n −1     ⩾θ  for θ ∈(0, 1). (3) Note that in order to have RIP, we need P(θ) < 1, as the maximum under the probability equals to δ1(A/√ n), which is less than or equal to δm(A/√ n). Conditions saying that a random matrix satisfies RIP were investigated in many works. We refer to [8] and references therein. In [3] the authors studied the model when a random matrix consists of independent columns. It was proved that if Xi’s are centered of variance 1 and satisfy assumption (1) with φ(t) = (1/2) exp(tα), α ⩾1, then A satisfies RIP with high probability. However, due to technical reasons, the case α < 1 was left open. Moreover, it was not clear if RIP can hold under assumptions on moments of Xi’s. In this note, we show that A satisfies RIP not only in the case α < 1, but also when the marginals of Xi’s satisfy moments condition only, that is condition (1) with φ(t) = t p, p > 4. Note that in view of a result by Bai, Silverstein and Yin [5], it seems that one cannot expect similar bounds when p < 4. Theorem 1. Case 1. Let p > 4 and φ(t) = t p. Let 0 < ε < min{1,(p −4)/4} and 0 < θ < 1. Assume that 28/(εθ) ⩽N ⩽ cθ(cεθ)p/2np/4 and set m =  C(ε, p)θ2p/(p−4−2ε)n  N n −2(2+ε)/(p−4−2ε) . Case 2. Let φ(t) = (1/2) exp(tα). Assume that 8/θ ⩽N ⩽cθ exp((1/2)(cθ√ n)α) and set m = C−2/αθ2n  ln  C2/αN/  θ2n −2/α . In both cases, we have P(δm(A/√ n) ⩽θ) ⩾1 −2−9θ −P(θ/2). 3. Kannan–Lovász–Simonovits problem (KLS) Let Xi’s and A be as above and assume additionally that Xi’s are identically distributed as a centered random vec- tor X. KLS problem asks how fast the empirical covariance matrix T := (1/N)A A⊤converges to the covariance matrix Σ := (1/N)EA A⊤(originally it was asked about so-called log-concave random vectors). In particular, is it true that with high probability, the operator norm ∥T −Σ∥⩽ε∥Σ∥for N being proportional to n? The corresponding important question in Random Matrix Theory is about the limit behavior of smallest and largest singular values. In the case of Wishart matrices, that is when the coordinates of X are i.i.d. random variables with finite fourth moment, the Bai–Yin theorem [4] states that the limits of minimal and maximal singular numbers of T are (1 ± √β)2 as n, N →∞and n/N →β ∈(0, 1). Moreover, it is known [5] that boundedness of fourth moment is needed in order to have the convergence of the largest singular value. The asymptotic non-limit behavior (also called “non-asymptotic” in Statistics), i.e., sharp upper and lower bounds for singular O. Guédon et al. / C. R. Acad. Sci. Paris, Ser. I 352 (2014) 431–434 433 values in terms of n and N, when n and N are sufficiently large, were studied in several works. To keep the notation more compact and clear we set M := max i⩽N |Xi|, S := sup a∈Sn−1      1 N N i=1  ⟨Xi,a⟩2 −E⟨Xi,a⟩2     . Note that the bound S ⩽ε is equivalent to bounds 1 ± ε for minimal/maximal singular values. For Gaussian matrices, it is known that singular values satisfy with probability close to one S := sup a∈Sn−1      1 N N i=1  ⟨Xi,a⟩2 −E⟨Xi,a⟩2      ⩽C n/N. (4) In [1,2] the same estimates were obtained for a large class of random matrices, which in particular does not require that entries of the columns are independent or that Xi’s are identically distributed. In particular it solves the original KLS problem. More precisely, under assumptions that Xi’s satisfy condition (1) with φ(t) = et/2 and that M ⩽C(Nn)1/4 with high probability (both conditions hold for log-concave vectors). Of course, in view of Bai–Yin theorem, the question raises if one can substitute the function φ(t) = et/2 with the function φ = t p for the “right” restriction p ⩾4. The first attempt in this direction was done in [10], where the bound S ⩽C(p, K)(n/N)1/2−2/p(ln lnn)2 was obtained for every p > 4 provided that M ⩽K√ n. Clearly, ln lnn is a “parasitic” term, which, in particular, does not allow one to solve the KLS problem with N proportional to n. Very recently, the “right” upper bound S ⩽C(n/N)1/2 was proved for p > 8 provided that M ⩽ C(Nn)1/4 [9]. The purpose of our note is to show that one can solve the KLS problem in the case p uploads/Science et Technologie/ restricted-isometry-property-for-random-matrices-with-heavy-tailed-columns.pdf

Tags
Science et Technologierandom matrix covariance independent theorem
Documents similaires
  • 24
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager