Université Paris-Est Université Paris-Est - Marne-la-Vallée Université Paris-Est - Créteil Val-de-Marne Centre National de la Recherche Scientifique

Approximating the covariance matrix with heavy tailed columns and RIP

Site: 
Date: 
17/11/2015 - 10:30 - 12:00
Salle: 
3B081
Orateur: 
LITVAK Alexander
Localisation: 
Université d'Alberta
Localisation: 
Canada
Document(s): 
Résumé: 

Let $A$ be a matrix whose columns $X_1,\dots, X_N$ are independent random vectors in $\R^n$. Assume that $p$-th moments of $\langle X_i, a\rangle$, $a\in S^{n-1}$, $i\leq N$, are uniformly bounded. For $p>4$ we prove that with high probability $A$ has the Restricted Isometry Property (RIP) provided that Euclidean norms $|X_i|$ are concentrated around $\sqrt{n}$ and that the covariance matrix is well approximated by the empirical covariance matrix provided that $\max _i |X_i|\leq C(nN)^{1/4}$. We also provide estimates for RIP when $\mathbb{E} \, \phi \left(|\langle X_i, a\rangle|\right) \leq 1$ for $\phi (t)=(1/2) \exp(t^{\alpha})$, with $\alpha \in (0,2]$.

Joint work with O. Gu\'edon, A. Pajor, N. Tomczak-Jaegermann