Approximating the covariance matrix with heavy tailed columns and RIP

Orateur: LITVAK Alexander
Localisation: Université d'Alberta, Canada
Type: Groupe de travail analyse, probabilités et statistique
Site: UPEM
Salle: 3B081
Date de début: 17/11/2015 - 10:30
Date de fin: 17/11/2015 - 10:30

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