Source-linked AI summary
Breaking the coherence barrier: A new theory for compressed sensing
Ben Adcock, Anders C. Hansen, Clarice Poon, Bogdan Roman
TL;DR
Compressed sensing has been used successfully in coherent real-world inverse problems that standard theory does not explain. The paper introduces asymptotic sparsity, asymptotic incoherence, and multilevel random sampling, with theorems showing compressed sensing under these relaxed conditions and enabling better reconstructions from fewer measurements. Its scope is primarily mathematical, and some estimates can worsen because sparsity levels interfere across sampling blocks.
Problem
Standard compressed-sensing theory does not explain successful applications such as MRI because incoherence and uniform random subsampling often fail, while structure-dependent sampling lacks theoretical justification.
Method
The paper generalizes sparsity, incoherence, and uniform random subsampling to asymptotic sparsity, asymptotic incoherence, and multilevel random subsampling.
Results
The new theory shows compressed sensing is possible under substantially more general conditions and explains empirical usage in coherent applications.
Takeaways & Limitations
Asymptotic incoherence and multilevel sampling offer greater sensing flexibility and can exploit signal structure for better reconstructions from fewer measurements.
Takeaways & Limitations
Interference between different sparsity levels can make the theorem's cumulative quantities S_k much larger than individual level sparsities s_k, increasing required measurements.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops a compressed-sensing theory for coherent real-world inverse problems, replacing sparsity, incoherence, and uniform random subsampling with asymptotic sparsity, asymptotic incoherence, and multilevel sampling.
- Motivation: Compressed sensing often succeeds in applications where standard assumptions fail, including MRI, CT, microscopy, spectroscopy, and radio interferometry.In many such problems, incoherence is lacking, making the standard theory inapplicable despite successful use of compressed sensing.
- Motivation: The standard theory does not explain why optimal sampling can depend on signal structure rather than overall sparsity alone.The paper identifies this as a gap between mature theory and empirical sampling strategies used in applications.
- New framework: The proposed framework generalizes the three traditional pillars to asymptotic sparsity, asymptotic incoherence, and multilevel random subsampling.Its theorems establish compressed sensing under these substantially more general conditions and address structure-dependent sampling.
- Practical implications: The theory explains empirical compressed-sensing usage, relaxes sensing-design requirements, and targets better reconstructions from fewer measurements.It argues that asymptotic incoherence suffices and that combining it with multilevel sampling exploits asymptotic sparsity.
- Practical implications: Real-world problems often impose coherent sensing operators, yet asymptotic incoherence and multilevel sampling can exploit structure and outperform universal operators.The paper discusses imposed operators such as Fourier sampling in MRI and computationally efficient implementations using fast transforms.
- Scope of standard theory: The paper notes that RIP does not hold in the practical applications considered, limiting its relevance to those inverse problems.This conclusion is supported by the paper's later flip-test confirmation.
2 The need for a new theory
Standard compressed-sensing theory does not explain its empirical success in coherent applications. The paper motivates replacing uniform sampling, incoherence, and ordinary sparsity with structure-aware concepts and sampling strategies.
- Standard CS asks whether its theory explains empirical success in applications such as MRI, but the paper argues that a substantial theory–practice gap remains.
- Uniform random subsampling can require full sampling for Fourier–wavelet problems because their coherence has the worst possible asymptotic behavior.
- The coherence barrier arises because discretizations of infinite-dimensional problems cannot remain incoherent as their size increases, affecting MRI, CT, microscopy, and seismology.
- Variable-density or multilevel subsampling empirically improves these coherent problems, although standard theory does not explain why.
- The paper therefore replaces incoherence, uniform random subsampling, and sparsity with asymptotic incoherence, multilevel sampling, and structure-aware sparsity concepts.
- The flip test shows that flipped reconstructions are substantially worse, so sparsity alone does not govern reconstruction quality.
3 New principles
The paper replaces standard compressed sensing assumptions with asymptotic incoherence, asymptotic sparsity, and multilevel random sampling to handle coherent, structured problems.
- New principles: The new framework generalizes sparsity, incoherence, and uniform random subsampling to asymptotic sparsity, asymptotic incoherence, and multilevel random sampling.These concepts are intended to explain compressed sensing performance when standard assumptions fail.
- Asymptotic incoherence: Fourier/wavelet, Fourier/Legendre, and Hadamard/wavelet systems are coherent but have large matrix entries concentrated in a leading submatrix.Figure 4 encodes larger absolute matrix entries as light regions and smaller entries as dark regions.
- Multilevel random sampling: Asymptotic incoherence permits full sampling of initial high-coherence rows followed by random subsampling where coherence decreases.The two-level scheme samples the first N1 rows fully and randomly selects m additional rows from N1 +1 through N.
- Multilevel random sampling: Multilevel sampling divides measurements into index blocks and independently chooses a prescribed number uniformly at random within each block.The scheme uses boundaries N1,...,Nr and sample counts m1,...,mr.
- Asymptotic sparsity: Sparsity in levels limits nonzero coefficients separately within successive index ranges, while asymptotic sparsity requires sk/(Mk −Mk−1) →0 as k →∞.This structure captures changing sparsity across levels rather than treating all coefficients identically.
4 Main theorems I: the finite-dimensional case
The finite-dimensional theorems allocate measurements across levels using local coherence and structured sparsity, showing that coherent systems can still support recovery with substantially fewer samples.
- Two-level sampling schemes: The two-level theorem fully samples an initial block and randomly samples a later block, with recovery controlled by sparsity, coherence, noise, and approximation error.The noisy-measurement goal is recovery up to an error proportional to δ and σs,M(f).
- Two-level sampling schemes: Fully sampling the first N1 measurements allows recovery of the first M1 coefficients when ∥P⊥N1UPM1∥≤ 2/(5√M1).The condition is stated as always being satisfied for some N1.
- Two-level sampling schemes: For wavelets with Fourier measurements, only m2 ≳s2 additional measurements are required when the relevant asymptotic coherence satisfies µN1 = O(1).This applies when N1 is a fixed fraction of N, up to logarithmic factors.
- Two-level sampling schemes: In the asymptotically sparse case, a fixed N1 recovers the nonsparse part, while additional measurements depend on s2 and µN1 for the sparse part.The theorem separates the measurement burden between early nonsparse content and later sparse content.
- Multilevel sampling schemes: The multilevel theorem replaces global quantities with local coherences, local sparsities, and relative sparsities when determining measurements mk.Its estimates are reported as sharp in several important cases and provide near-optimal guarantees for wavelet sparsity with Fourier sampling.
- Sharpness of the estimates: Relative sparsities Sk can greatly exceed local sparsities sk because interference between levels may make Sk proportional to total sparsity.The paper presents this dependence as intrinsic rather than merely an artifact of the proof.
- Structured sparsity: Structured sparsity reduces total measurements from m ≳rs log(N) to m ≳s log(N), a factor-of-r saving.The comparison contrasts unstructured s-sparsity in every block with sk-sparsity within each level.
- Structured sparsity: For a 512 × 512 image with r = 9 wavelet scales, standard sparsity-based estimates can overestimate practical sampling by nine-fold, from roughly 5–10% to 45–90%.The passage notes that the simplified block-diagonal model approximates the Fourier/wavelets recovery problem.
5 Main theorems II: the infinite-dimensional case
The infinite-dimensional theory extends compressed sensing to Hilbert-space signals and multilevel sampling, with recovery guarantees under balancing conditions and without requiring finite support.
- Infinite-dimensional formulation: Infinite-dimensional compressed sensing recovers Hilbert-space signals from sampled coefficients using an orthonormal sampling basis and sparsity system.Measurements are modeled as inner products with the sampling basis, while recovery uses coefficients in the sparsity system.
- Recovery guarantees: Recovery is stable up to an error determined by σs,M(f) when the sampling parameters satisfy a weak or strong balancing property.The balancing requirement controls the relationship between truncation, sampling, and sparsity parameters.
- Multilevel sampling: The multilevel theorem allows sampling across several index levels with level-specific sparsities and measurement counts.The framework uses vectors N, m, M, and s to describe sampling and sparsity across levels.
- Theorem extensions: The stronger theorem removes the zero-tail condition, at the cost of replacing M by the larger quantity ˜M in a logarithmic factor.For Fourier sampling with wavelets, ˜M is finite and scales as O(KN).
- Numerical illustration: For smooth phantoms, infinite-dimensional recovery is more accurate because its error is dominated by wavelet approximation rather than Fourier approximation error.The comparison uses identical sampling information with 6.15% subsampling and DB4 wavelets.
6 Recovery of wavelet coefficients from Fourier samples
Fourier sampling with wavelet sparsity is globally coherent but asymptotically incoherent, so multilevel sampling can exploit wavelet-scale structure for accurate recovery.
- Coherence structure: Fourier sampling with wavelets is globally coherent yet asymptotically incoherent, motivating multilevel rather than uniform sampling.The coherence is concentrated in leading matrix regions, while the asymptotic behavior supports level-dependent sampling.
- Recovery theorem: The Fourier/wavelet theorem explains observed application success because each level’s measurements depend mainly on nearby local sparsities, with exponentially diminishing off-level influence.The near-block-diagonal structure accounts for the off-diagonal interference terms in the sampling estimate.
- Measurement comparison: At 12.5% subsampling and 256×256 resolution, multilevel Hadamard or Fourier measurements yield an error almost 50% smaller than random Bernoulli measurements.The comparison uses DB4 wavelets and a fixed total of 8192 measurements.
- Practical implication: The theory indicates that structured sparsity can substantially improve reconstructions when measurements are designed for both sparsity and signal structure.Uniformly universal Gaussian or Bernoulli measurements cannot exploit the same structure because they satisfy an RIP.
7 Proofs
The proofs establish the paper’s main compressed-sensing results by reducing them to propositions for multilevel sampling and verifying their balancing and coherence conditions. Technical probability tools and Fourier/wavelet estimates then complete the theorem proofs.
- Balancing conditions: Weak or strong balancing conditions with respect to the isometry U provide sufficient conditions for the recovery propositions.Proposition 7.3 uses weak balancing, whereas Proposition 7.4 uses strong balancing and specifies the corresponding probability and sampling requirements.
- Sampling guarantees: Full sampling at every level makes the proposition conclusions hold with probability one.This is stated for both the weak-balancing and strong-balancing results when m_k = N_k − N_{k−1} for all levels.
- Main theorem proofs: The main theorems are derived from propositions for two-level and multilevel sampling schemes.The proof of Theorems 4.1 and 5.2 applies Proposition 7.3 to a two-level scheme, while Theorems 4.4 and 5.3 follow from Propositions 7.4 and 7.1.
- Probabilistic tools: The multilevel Bernoulli model samples each level independently with prescribed probabilities and supplies the probabilistic framework used in the propositions.The sampling set is formed from Bernoulli variables with P(δ_k = 1) = q, and subsequent propositions establish bounds for this model.
- Fourier/wavelet estimates: Fourier/wavelet decay and vanishing moments make the balancing relation closer to linear and the change-of-basis matrix closer to block diagonal.These estimates support the application of the abstract propositions to the Fourier/wavelets pair.