On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels

Abstract

The purpose of this paper is twofold. The first is to point out that the Restricted Isometry Property (RIP) does not hold in many applications where compressed sensing is successfully used. This includes fields like Magnetic Resonance Imaging (MRI), Computerized Tomography, Electron Microscopy, Radio Interferometry and Fluorescence Microscopy. We demonstrate that for natural compressed sensing matrices involving a level based reconstruction basis (e.g. wavelets), the number of measurements required to recover all $s$-sparse signals for reasonable $s$ is excessive. In particular, uniform recovery of all $s$-sparse signals is quite unrealistic. This realisation shows that the RIP is insufficient for explaining the success of compressed sensing in various practical applications. The second purpose of the paper is to introduce a new framework based on a generalised RIP-like definition that fits the applications where compressed sensing is used. We show that the shortcomings that show that uniform recovery is unreasonable no longer apply if we instead ask for structured recovery that is uniform only within each of the levels. To examine this phenomenon, a new tool, termed the 'Restricted Isometry Property in Levels' is described and analysed. Furthermore, we show that with certain conditions on the Restricted Isometry Property in Levels, a form of uniform recovery within each level is possible. Finally, we conclude the paper by providing examples that demonstrate the optimality of the results obtained.

References in corpus (4)

• Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
• On asymptotic structure in compressed sensing
• Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

Cited by in corpus (7)

• Compressed sensing with sparse corruptions: Fault-tolerant sparse collocation approximations
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Correcting for unknown errors in sparse high-dimensional function approximation
• Compressed sensing with structured sparsity and structured acquisition
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• Single-Pixel Compressive Imaging in Shift-Invariant Spaces via Exact Wavelet Frames