Bounds of restricted isometry constants in extreme asymptotics: Formulae for Gaussian matrices

Restricted isometry constants (RICs) provide a measure of how far from an isometry a matrix can be when acting on sparse vectors. This, and related quantities, provide a mechanism by which standard eigen-analysis can be applied to topics relying on sparsity. RIC bounds have been presented for a variety of random matrices and matrix dimension and sparsity ranges. We provide explicitly formulae for RIC bounds, of n × N Gaussian matrices with sparsity k, in three settings: (a) n/N fixed and k/n approaching zero, (b) k/n fixed and n/N approaching zero, and (c) n/N approaching zero with k/n decaying inverse logarithmically in N/n; in these three settings the RICs (a) decay to zero, (b) become unbounded (or approach inherent bounds), and (c) approach a non-zero constant. Implications of these results for RIC based analysis of compressed sensing algorithms are presented.