Restricted Isometry Property of Random Subdictionaries

DOI10.1109/TIT.2015.2448658MaRDI QIDQ2977352zbMATH OpenOpenAlexFDO

Authors Alexander Barg, Arya Mazumdar, Rongrong Wang

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.06345

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We study statistical restricted isometry, a property closely related to sparse signal recovery, of deterministic sensing matrices of size $mimesN$. 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 ${mathbbR}^k$ into ${mathbbR}^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(klogN)$ or $m=Theta(klogk)$. We also give examples of matrix families that are shown to have the StRIP property using our sufficient conditions.

Cited in

(2)

• Construction of highly redundant incoherent unit norm tight frames as a union of orthonormal bases
• Reed-Muller Codes

This page was built for publication: Restricted Isometry Property of Random Subdictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977352)