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. On étudie la propriéte ́ 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 estime ́ a ̀ 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. Introduction. Let T ⊂ RN and Γ be an n × N matrix. Consider the problem of reconstructing any vector x ∈ T from the data Γx ∈ Rn, with a fast algorithm. Clearly one needs some a priori hypothesis on the subset T and of course, the matrix Γ should be suitably chosen. The common and useful hypothesis is that T consists of sparse vectors, that is vectors with short support. In that setting, Compressed Sensing provides a way of reconstructing the original signal x from its compression Γx with n N by the so