Restricted isometry property for random matrices with heavy-tailed columns

Guédon, Olivier; Litvak, Alexander E.; Pajor, Alain; Tomczak-Jaegermann, Nicole

doi:10.1016/j.crma.2014.03.005

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]

Présenté par : Gilles Pisier

Guédon, Olivier ¹ ; Litvak, Alexander E.² ; Pajor, Alain ¹ ; Tomczak-Jaegermann, Nicole ²

¹ Université Paris-Est, Laboratoire d'analyse et de mathématiques appliquées (UMR 8050), UPEMLV, 77454 Marne-la-Vallée, France
² Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada

Comptes Rendus. Mathématique, Tome 352 (2014) no. 5, pp. 431-434.

Résumé
Abstract

Soit A une matrice dont les colonnes $X_{1}, \dots, X_{N}$ sont des vecteurs indépendants de $R^{n}$ . On suppose que les moments d'ordre p des $〈 X_{i}, a 〉$ , $a \in S^{n - 1}$ , $1 ⩽ i ⩽ N$ sont uniformément bornés pour $p > 4$ . On démontre que si les normes euclidiennes des $| X_{i} |$ se concentrent autour de $\sqrt{n}$ , la matrice A vérifie une propriété d'isométrie restreinte avec grande probabilité et que si $\max_{i} | X_{i} | ⩽ C {(n N)}^{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 ϕ (| 〈 X_{i}, a 〉 |) ⩽ 1$ pour tout $a \in S^{n - 1}$ , $1 ⩽ i ⩽ N$ avec $ϕ (t) = (1 / 2) \exp (t^{α})$ et $α \in (0, 2]$ .

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 $〈 X_{i}, a 〉$ , $a \in S^{n - 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 $| 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} | ⩽ C {(n N)}^{1 / 4}$ . We also provide estimates for RIP when $E ϕ (| 〈 X_{i}, a 〉 |) ⩽ 1$ for $ϕ (t) = (1 / 2) \exp (t^{α})$ , with $α \in (0, 2]$ .

Reçu le : 2014-01-23
Accepté le : 2014-03-06
Publié le : 2014-03-27

DOI : 10.1016/j.crma.2014.03.005

Affiliations des auteurs :

Guédon, Olivier ¹ ; Litvak, Alexander E. ² ; Pajor, Alain ¹ ; Tomczak-Jaegermann, Nicole ²

@article{CRMATH_2014__352_5_431_0,
     author = {Gu\'edon, Olivier and Litvak, Alexander E. and Pajor, Alain and Tomczak-Jaegermann, Nicole},
     title = {Restricted isometry property for random matrices with heavy-tailed columns},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {431--434},
     publisher = {Elsevier},
     volume = {352},
     number = {5},
     year = {2014},
     doi = {10.1016/j.crma.2014.03.005},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2014.03.005/}
}

TY  - JOUR
AU  - Guédon, Olivier
AU  - Litvak, Alexander E.
AU  - Pajor, Alain
AU  - Tomczak-Jaegermann, Nicole
TI  - Restricted isometry property for random matrices with heavy-tailed columns
JO  - Comptes Rendus. Mathématique
PY  - 2014
SP  - 431
EP  - 434
VL  - 352
IS  - 5
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2014.03.005/
DO  - 10.1016/j.crma.2014.03.005
LA  - en
ID  - CRMATH_2014__352_5_431_0
ER  -

%0 Journal Article
%A Guédon, Olivier
%A Litvak, Alexander E.
%A Pajor, Alain
%A Tomczak-Jaegermann, Nicole
%T Restricted isometry property for random matrices with heavy-tailed columns
%J Comptes Rendus. Mathématique
%D 2014
%P 431-434
%V 352
%N 5
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2014.03.005/
%R 10.1016/j.crma.2014.03.005
%G en
%F CRMATH_2014__352_5_431_0

Guédon, Olivier; Litvak, Alexander E.; Pajor, Alain; Tomczak-Jaegermann, Nicole. Restricted isometry property for random matrices with heavy-tailed columns. Comptes Rendus. Mathématique, Tome 352 (2014) no. 5, pp. 431-434. doi : 10.1016/j.crma.2014.03.005. http://www.numdam.org/articles/10.1016/j.crma.2014.03.005/

Bibliographie
Cité par

[1] Adamczak, R.; Litvak, A.E.; Pajor, A.; Tomczak-Jaegermann, N. Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, J. Amer. Math. Soc., Volume 23 (2010) no. 2, pp. 535-561

[2] Adamczak, R.; Litvak, A.E.; Pajor, A.; Tomczak-Jaegermann, N. Sharp bounds on the rate of convergence of empirical covariance matrix, C. R. Acad. Sci. Paris, Ser. I, Volume 349 (2011), pp. 195-200

[3] Adamczak, R.; Litvak, A.; Pajor, A.; Tomczak-Jaegermann, N. Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constr. Approx., Volume 34 (2011), pp. 61-88

[4] Bai, Z.D.; Yin, Y.Q. Limit of the smallest eigenvalue of a large dimensional sample covariance matrix, Ann. Probab., Volume 21 (1993), pp. 1275-1294

[5] Bai, Z.D.; Silverstein, J.W.; Yin, Y.Q. A note on the largest eigenvalue of a large dimensional sample covariance matrix, J. Mult. Anal., Volume 26 (1988), pp. 166-168

[6] Candés, E.J.; Tao, T. Decoding by linear programming, IEEE Trans. Inform. Theory, Volume 51 (2005), pp. 4203-4215

[7] Donoho, D.L. Compressed sensing, IEEE Trans. Inform. Theory, Volume 52 (2006), pp. 1289-1306

[8] Chafaï, D.; Guédon, O.; Lecué, G.; Pajor, A. Interactions Between Compressed Sensing Random Matrices and High Dimensional Geometry, Collection “Panoramas et Synthèses”, vol. 37, Société mathématique de France, Paris, 2012

[9] Mendelson, S.; Paouris, G. On the singular values of random matrices, J. Eur. Math. Soc. (2014) (in press)

[10] Vershynin, R. How close is the sample covariance matrix to the actual covariance matrix?, J. Theoret. Probab., Volume 25 (2012), pp. 655-686

Cité par Sources :