Restricted Isometry Property of Random Subdictionaries

DOI10.1109/TIT.2015.2448658zbMATH Open1359.94061arXiv1506.06345OpenAlexW3104389152MaRDI QIDQ2977352FDOQ2977352

Authors: Alexander Barg, Arya Mazumdar, Rongrong Wang 

Publication date: 28 April 2017

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

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.

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

Mathematics Subject Classification ID

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

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)