Let A be a matrix whose columns are independent random vectors in . Assume that p-th moments of , , , are uniformly bounded. For , we prove that with high probability A has the Restricted Isometry Property (RIP) provided that Euclidean norms are concentrated around and that the covariance matrix is well approximated by the empirical covariance matrix provided that . We also provide estimates for RIP when for , with .
Soit A une matrice dont les colonnes sont des vecteurs indépendants de . On suppose que les moments d'ordre p des , , sont uniformément bornés pour . On démontre que si les normes euclidiennes des se concentrent autour de , la matrice A vérifie une propriété d'isométrie restreinte avec grande probabilité et que si , 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 pour tout , avec et .
Accepted:
Published online:
Olivier Guédon 1; Alexander E. Litvak 2; Alain Pajor 1; Nicole Tomczak-Jaegermann 2
@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] 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] 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] Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constr. Approx., Volume 34 (2011), pp. 61-88
[4] Limit of the smallest eigenvalue of a large dimensional sample covariance matrix, Ann. Probab., Volume 21 (1993), pp. 1275-1294
[5] A note on the largest eigenvalue of a large dimensional sample covariance matrix, J. Mult. Anal., Volume 26 (1988), pp. 166-168
[6] Decoding by linear programming, IEEE Trans. Inform. Theory, Volume 51 (2005), pp. 4203-4215
[7] Compressed sensing, IEEE Trans. Inform. Theory, Volume 52 (2006), pp. 1289-1306
[8] 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] On the singular values of random matrices, J. Eur. Math. Soc. (2014) (in press)
[10] 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