Comptes Rendus
Functional analysis/Probability theory
Restricted isometry property for random matrices with heavy-tailed columns
Comptes Rendus. Mathématique, Volume 352 (2014) no. 5, pp. 431-434.

Let A be a matrix whose columns X1,,XN are independent random vectors in Rn. Assume that p-th moments of Xi,a, aSn1, iN, 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].

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, aSn1, 1iN 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 aSn1, 1iN avec ϕ(t)=(1/2)exp(tα) et α(0,2].

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2014.03.005

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

1 Université Paris-Est, Laboratoire d'analyse et de mathématiques appliquées (UMR 8050), UPEMLV, 77454 Marne-la-Vallée, France
2 Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada
@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/

[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

Cited by Sources:

Comments - Policy