The gap between the null space property and the restricted isometry property
From MaRDI portal
Publication:273151
DOI10.1016/J.LAA.2016.03.022zbMATH Open1334.15015arXiv1506.03040OpenAlexW2963109107MaRDI QIDQ273151FDOQ273151
Xuemei Chen, Jameson Cahill, Rongrong Wang
Publication date: 21 April 2016
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: The null space property (NSP) and the restricted isometry property (RIP) are two properties which have received considerable attention in the compressed sensing literature. As the name suggests, NSP is a property that depends solely on the null space of the measurement procedure and as such, any two matrices which have the same null space will have NSP if either one of them does. On the other hand, RIP is a property of the measurement procedure itself, and given an RIP matrix it is straightforward to construct another matrix with the same null space that is not RIP. %Furthermore, RIP is known to imply NSP and therefore RIP is a strictly stronger assumption than NSP. We say a matrix is RIP-NSP if it has the same null space as an RIP matrix. We show that such matrices can provide robust recovery of compressible signals under Basis pursuit which in many applicable settings is comparable to the guarantee that RIP provides. More importantly, we constructively show that the RIP-NSP is stronger than NSP with the aid of this robust recovery result, which shows that RIP is fundamentally stronger than NSP.
Full work available at URL: https://arxiv.org/abs/1506.03040
Cites Work
- Decoding by Linear Programming
- Compressed sensing and best 𝑘-term approximation
- Recovery of sparsest signals via \(\ell^q \)-minimization
- A remark on compressed sensing
- Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
- On sparse reconstruction from Fourier and Gaussian measurements
- Sparse representations in unions of bases
- Sparse Approximation Property and Stable Recovery of Sparse Signals From Noisy Measurements
- Stable and Robust Sampling Strategies for Compressive Imaging
- Restricted Isometry Constants Where $\ell ^{p}$ Sparse Recovery Can Fail for $0≪ p \leq 1$
- Sparse recovery under weak moment assumptions
- An Improved Estimate in the Restricted Isometry Problem
- Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
- Phase transitions for greedy sparse approximation algorithms
- A null space analysis of the \(\ell_1\)-synthesis method in dictionary-based compressed sensing
- The restricted isometry property and its implications for compressed sensing
Cited In (6)
- A Data-Independent Distance to Infeasibility for Linear Conic Systems
- Stability analysis of a class of sparse optimization problems
- On the Gap Between Restricted Isometry Properties and Sparse Recovery Conditions
- Weak Stability of ℓ1-Minimization Methods in Sparse Data Reconstruction
- Preserving injectivity under subgaussian mappings and its application to compressed sensing
- Robust and stable region-of-interest tomographic reconstruction using a robust width prior
This page was built for publication: The gap between the null space property and the restricted isometry property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q273151)
