Restricted isometry property for random matrices with heavy-tailed columns

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

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

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

¹ 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, Volume 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 :

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

@article{CRMATH_2014__352_5_431_0,
     author = {Olivier Gu\'edon and Alexander E. Litvak and Alain Pajor and Nicole Tomczak-Jaegermann},
     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},
}

TY  - JOUR
AU  - Olivier Guédon
AU  - Alexander E. Litvak
AU  - Alain Pajor
AU  - Nicole Tomczak-Jaegermann
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
DO  - 10.1016/j.crma.2014.03.005
LA  - en
ID  - CRMATH_2014__352_5_431_0
ER  -

%0 Journal Article
%A Olivier Guédon
%A Alexander E. Litvak
%A Alain Pajor
%A Nicole Tomczak-Jaegermann
%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
%R 10.1016/j.crma.2014.03.005
%G en
%F CRMATH_2014__352_5_431_0

Olivier Guédon; Alexander E. Litvak; Alain Pajor; Nicole Tomczak-Jaegermann. Restricted isometry property for random matrices with heavy-tailed columns. Comptes Rendus. Mathématique, Volume 352 (2014) no. 5, pp. 431-434. doi : 10.1016/j.crma.2014.03.005. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2014.03.005/

Bibliographie
Cité par

[1] R. Adamczak; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann 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] R. Adamczak; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann 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] R. Adamczak; A. Litvak; A. Pajor; N. Tomczak-Jaegermann Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constr. Approx., Volume 34 (2011), pp. 61-88

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

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

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

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

[8] D. Chafaï; O. Guédon; G. Lecué; A. Pajor 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] S. Mendelson; G. Paouris On the singular values of random matrices, J. Eur. Math. Soc. (2014) (in press)

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

Cité par Sources :

Commentaires - Politique