Geometry of log-concave ensembles of random matrices and approximate reconstruction

We study the Restricted Isometry Property of a random matrix Γ with independent isotropic log-concave rows. To this end, we introduce a parameter Γk,m that controls uniformly the operator norm of sub-matrices with k rows and m columns. This parameter is estimated by means of new tail estimates of order statistics and deviation inequalities for norms of projections of an isotropic log-concave vector.

RésuméOn étudie la propriété dʼisométrie restreinte dʼune matrice aléatoire Γ dont les lignes sont des vecteurs aléatoires indépendants isotropes log-concave. Pour cela on introduit un paramètre Γk,m qui contrôle uniformément les normes dʼopérateurs des sous-matrices de k lignes et m colonnes. Ce paramètre est estimé à lʼaide de nouvelles inégalités de queue des statistiques dʼordre et dʼinégalités de déviation des normes de projections dʼun vecteur aléatoire log-concave.