Restricted isometry property for random matrices with heavy-tailed columns

Let A   be a matrix whose columns X1,…,XNX1,…,XN are independent random vectors in RnRn. Assume that p  -th moments of 〈Xi,a〉〈Xi,a〉, a∈Sn−1a∈Sn−1, i⩽Ni⩽N, are uniformly bounded. For p>4p>4, we prove that with high probability A   has the Restricted Isometry Property (RIP) provided that Euclidean norms |Xi||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/4maxi|Xi|⩽C(nN)1/4. We also provide estimates for RIP when Eϕ(|〈Xi,a〉|)⩽1Eϕ(|〈Xi,a〉|)⩽1 for ϕ(t)=(1/2)exp(tα)ϕ(t)=(1/2)exp(tα), with α∈(0,2]α∈(0,2].

RésuméSoit A   une matrice dont les colonnes X1,…,XNX1,…,XN sont des vecteurs indépendants de RnRn. On suppose que les moments d'ordre p   des 〈Xi,a〉〈Xi,a〉, a∈Sn−1a∈Sn−1, 1⩽i⩽N1⩽i⩽N sont uniformément bornés pour p>4p>4. On démontre que si les normes euclidiennes des |Xi||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/4maxi|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〉|)⩽1Eϕ(|〈Xi,a〉|)⩽1 pour tout a∈Sn−1a∈Sn−1, 1⩽i⩽N1⩽i⩽N avec ϕ(t)=(1/2)exp(tα)ϕ(t)=(1/2)exp(tα) et α∈(0,2]α∈(0,2].