Restricted isometry property of random subdictionaries

Abstract

We study statistical restricted isometry, a property closely related to sparse signal recovery, of deterministic sensing matrices of size $m\times N$. A matrix is said to have a statistical restricted isometry property (StRIP) of order $k$ if most submatrices with $k$ columns define a near-isometric map of ${\mathbb{R}}^k$ into ${\mathbb{R}}^m$. As our main result, we establish sufficient conditions for the StRIP property of a matrix in terms of the mutual coherence and mean square coherence. We show that for many existing deterministic families of sampling matrices, $m=O(k)$ rows suffice for $k$-StRIP, which is an improvement over the known estimates of either $m=\Theta (k\log N)$ or $m=\Theta (k\log k)$. We also give examples of matrix families that are shown to have the StRIP property using our sufficient conditions.

To appear in the IEEE Transactions on Information Theory, 2015. A detailed draft which is a predecessor of this paper appears as arXiv:1303.1847

References in corpus (1)

• Near-ideal model selection by ${\ell }_1$ minimization

Cited by in corpus (3)

• Approximating matrices and convex bodies through Kadison-Singer
• Low rank approximation and decomposition of large matrices using error correcting codes
• Convergence Rate of Empirical Spectral Distribution of Random Matrices from Linear Codes