Norms of random submatrices and sparse approximation

Many problems in the theory of sparse approximation require bounds on operator norms of a random submatrix drawn from a fixed matrix. The purpose of this Note is to collect estimates for several different norms that are most important in the analysis of ℓ1 minimization algorithms. Several of these bounds have not appeared in detail. To cite this article: J.A. Tropp, C. R. Acad. Sci. Paris, Ser. I 346 (2008).

RésuméDe nombreux problèmes en théorie de l'approximation non linéaire exigent des majorations la norme d'une matrice aléatoirement extraite d'une matrice donnée de plus grande dimension. L'objectif de cette Note est de présenter des estimations de ces normes qui se révèlent être importantes pour l'étude des algorithmes de minimisation de type ℓ1. La plupart de ces bornes n'ont pas encore été publiées explicitement. Pour citer cet article : J.A. Tropp, C. R. Acad. Sci. Paris, Ser. I 346 (2008).