Stable and Robust Sampling Strategies for Compressive Imaging

Felix Krahmer, Rachel A. WardIEEE TIP 2014 · OpenReview

TL;DR

This paper introduces a novel "local coherence" framework to design optimal sampling strategies for compressive imaging, particularly for MRI. By carefully sampling frequencies based on this metric, they achieve stable and robust image reconstruction using total variation or L1 minimization, even with limited measurements and noisy data.

What Problem Does This Paper Address?

Compressive sensing (CS) allows reconstructing signals from fewer measurements than traditionally required, provided the signal is sparse in some basis and the measurement system is incoherent with that basis. For imaging applications like MRI, images are often sparse in wavelet or gradient domains. However, the Fourier domain measurements used in MRI are not incoherent with these sparsity bases, especially for low-frequency components and low-scale wavelets. This incoherence poses a theoretical challenge for guaranteeing stable and robust reconstruction. Existing empirical evidence suggests variable density sampling (favoring low frequencies) works well, but a theoretical understanding and optimal strategy were lacking. This paper aims to bridge this gap by providing a theoretical framework for designing such sampling strategies.

Methods

The core contribution is the introduction of local coherence as a measure of how correlated each sensing vector (e.g., a specific frequency in Fourier measurements) is to the sparsity basis (e.g., Haar wavelets). This is a refinement of the broader concept of mutual coherence.

The authors then:

  • Develop a theoretical framework: They use local coherence to derive bounds on the incoherence between the discrete Fourier transform (DFT) and the Haar wavelet basis.
  • Propose an optimal sampling strategy: Based on these local coherence estimates, they propose sampling frequencies according to an inverse square power-law density. This strategy is shown to lead to matrices with the Restricted Isometry Property (RIP) with near-optimal dimensions.
  • Prove reconstruction guarantees: They demonstrate that using this variable density sampling, both total variation (TV) minimization and L1 minimization can achieve stable and robust image reconstruction. This means the reconstructed image is close to the true image, even in the presence of noise and if the image is not perfectly sparse (best s-term approximation error).

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees and uses synthetic examples for illustration.

Key Insights and Ideas

  • Local coherence is key: The paper argues that "local coherence" is a more nuanced and useful metric than global mutual coherence for designing sampling strategies in coherent systems. It allows for a more precise understanding of the sensing-basis-to-sparsity-basis relationship.
  • Inverse square power-law sampling is optimal: The proposed sampling strategy, concentrating measurements on low frequencies according to an inverse square power-law, is theoretically shown to be near-optimal for achieving RIP.
  • Coherence doesn't preclude good reconstruction: While Fourier and wavelet bases are inherently coherent, the paper shows that by carefully adapting the sampling strategy based on local coherence, one can still achieve strong theoretical guarantees for reconstruction.
  • TV and L1 minimization are robust: The proposed sampling strategies work well with both total variation and L1 minimization, demonstrating their versatility for different sparsity models (gradient vs. wavelet).

Key Results

  • Theoretical guarantees for reconstruction: The paper provides theorems (Theorem 3.1 and 3.2) that establish stable and robust image reconstruction guarantees for total variation and L1 minimization, respectively, under the proposed variable density sampling schemes.
  • Near-optimal RIP: The sampling strategies are shown to yield matrices with the Restricted Isometry Property (RIP) with near-optimal embedding dimensions, meaning the number of measurements required is close to the theoretical minimum.
  • Numerical validation: Figures in the paper demonstrate that the proposed variable density sampling strategies (especially the inverse square power-law) outperform uniform sampling and low-frequency-only sampling in terms of reconstruction quality and error, particularly for recovering fine details.

Limitations and Future Work

  • Noise model: The theoretical noise model used (weighted L2-norm) is non-standard and might not perfectly reflect real-world noise. Empirical results suggest the standard uniform noise model might yield superior performance.
  • Logarithmic factors: The number of samples required in the TV minimization guarantee has extra logarithmic factors compared to the L1 minimization guarantee. The authors suspect this is an artifact of the proof and could be improved.
  • Smoother wavelets: The current analysis uses Haar wavelets. The authors believe that using smoother wavelets might remove some logarithmic factors in the sampling requirements.
  • Infinite-dimensional models: Extending the approach to infinite-dimensional image models is suggested as an interesting future direction, though challenging for optimization-based methods.
  • Signal statistics: The theory relies on local coherence between bases, not directly on signal statistics (like image content sparsity). Incorporating signal statistics could lead to even stronger guarantees.
  • Discretization errors: The paper does not explicitly address errors arising from the discretization of images and Fourier measurements.

Summary updated

Abstract

In many signal processing applications, one wishes to acquire images that are sparse in transform domains such as spatial finite differences or wavelets using frequency domain samples. For such applications, overwhelming empirical evidence suggests that superior image reconstruction can be obtained through variable density sampling strategies that concentrate on lower frequencies. The wavelet and Fourier transform domains are not incoherent because low-order wavelets and low-order frequencies are correlated, so compressive sensing theory does not immediately imply sampling strategies and reconstruction guarantees. In this paper, we turn to a more refined notion of coherence-the so-called local coherence-measuring for each sensing vector separately how correlated it is to the sparsity basis. For Fourier measurements and Haar wavelet sparsity, the local coherence can be controlled and bounded explicitly, so for matrices comprised of frequencies sampled from a suitable inverse square power-law density, we can prove the restricted isometry property with near-optimal embedding dimensions. Consequently, the variable-density sampling strategy we provide allows for image reconstructions that are stable to sparsity defects and robust to measurement noise. Our results cover both reconstruction by ℓ 1 -minimization and total variation minimization. The local coherence framework developed in this paper should be of independent interest, as it implies that for optimal sparse recovery results, it suffices to have bounded average coherence from sensing basis to sparsity basis-as opposed to bounded maximal coherence-as long as the sampling strategy is adapted accordingly.
BibTeX
@article{krahmer2014stable,
  author = {Felix Krahmer and Rachel A. Ward},
  title = {{Stable and Robust Sampling Strategies for Compressive Imaging}},
  journal = {IEEE Trans. Image Process.},
  year = {2014},
  url = {https://openreview.net/forum?id=rVMTaAKATo},
}
Figure