Breaking the coherence barrier: A new theory for compressed sensing
arXiv:1302.0561
Abstract
This paper provides an extension of compressed sensing which bridges a substantial gap between existing theory and its current use in real-world applications. It introduces a mathematical framework that generalizes the three standard pillars of compressed sensing - namely, sparsity, incoherence and uniform random subsampling - to three new concepts: asymptotic sparsity, asymptotic incoherence and multilevel random sampling. The new theorems show that compressed sensing is also possible, and reveals several advantages, under these substantially relaxed conditions. The importance of this is threefold. First, inverse problems to which compressed sensing is currently applied are typically coherent. The new theory provides the first comprehensive mathematical explanation for a range of empirical usages of compressed sensing in real-world applications, such as medical imaging, microscopy, spectroscopy and others. Second, in showing that compressed sensing does not require incoherence, but instead that asymptotic incoherence is sufficient, the new theory offers markedly greater flexibility in the design of sensing mechanisms. Third, by using asymptotic incoherence and multi-level sampling to exploit not just sparsity, but also structure, i.e. asymptotic sparsity, the new theory shows that substantially improved reconstructions can be obtained from fewer measurements.
References in corpus (12)
- Message Passing Algorithms for Compressed Sensing
- Sparsity and Incoherence in Compressive Sampling
- Structured Compressed Sensing: From Theory to Applications
- Compressive Fluorescence Microscopy for Biological and Hyperspectral Imaging
- Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
- Measure What Should be Measured: Progress and Challenges in Compressive Sensing
- Spread spectrum magnetic resonance imaging
- On asymptotic structure in compressed sensing
- Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum
- The STONE Transform: Multi-Resolution Image Enhancement and Real-Time Compressive Video
- The Effect of Spatial Coupling on Compressive Sensing
- Quantitative Estimates for the Finite Section Method
Cited by in corpus (16)
- Learning-based Compressive Subsampling
- Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems
- On asymptotic structure in compressed sensing
- Classification and Reconstruction of High-Dimensional Signals from Low-Dimensional Features in the Presence of Side Information
- Computing Spectra -- On the Solvability Complexity Index Hierarchy and Towers of Algorithms
- On the absence of the RIP in real-world applications of compressed sensing and the RIP in levels
- Optimal Sparse Recovery for Multi-Sensor Measurements
- A note on compressed sensing of structured sparse wavelet coefficients from subsampled Fourier measurements
- Sparsity and Parallel Acquisition: Optimal Uniform and Nonuniform Recovery Guarantees
- Analyzing the structure of multidimensional compressed sensing problems through coherence
- Reconstruction of sparse wavelet signals from partial Fourier measurements
- Bayesian Optimization of Sampling Densities in MRI
- On stable reconstructions from nonuniform Fourier measurements
- On the role of total variation in compressed sensing - structure dependence
- On the role of total variation in compressed sensing
- Complexity Issues in Computing Spectra, Pseudospectra and Resolvents