Restricted Isometry Property of Random Subdictionaries

Alexander Barg, Arya Mazumdar, Rongrong Wang

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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.

Original languageEnglish (US)
Article number7131508
Pages (from-to)4440-4450
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number8
StatePublished - Aug 2015

Bibliographical note

Publisher Copyright:
© 1963-2012 IEEE.


  • Binary codes
  • Coherence
  • Linear matrix inequalities
  • Random variables
  • Sensors
  • Sparse matrices
  • Strips


Dive into the research topics of 'Restricted Isometry Property of Random Subdictionaries'. Together they form a unique fingerprint.

Cite this