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 xed 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.