PaperlayerView exact revision on arXiv

Source-linked AI summary

Stable and robust sampling strategies for compressive imaging

Felix Krahmer, Rachel Ward

arXiv:1210.2380v3cs.CVcs.ITmath.NA

TL;DR

The paper addresses how to sample frequency-domain measurements for images sparse in wavelet or gradient domains despite Fourier–sparsity coherence. It uses local coherence to design variable-density Fourier sampling and obtains stable, noise-robust recovery guarantees for ℓ1-minimization and total variation minimization.

  • Problem

    Fourier and wavelet bases are correlated at low orders, so standard incoherence-based compressive sensing theory does not directly provide sampling strategies or guarantees for these imaging problems.

  • Method

    The paper bounds local Fourier–Haar coherence and uses a suitable variable-density Fourier sampling strategy for wavelet- and gradient-sparse images.

  • Results

    The resulting measurements admit stable reconstruction through ℓ1-minimization or total variation minimization, with errors controlled by best s-term approximation and measurement noise.

  • Takeaways & Limitations

    The local-coherence framework shows that adapted sampling can support sparse recovery using bounded average coherence rather than bounded maximal coherence.

  • Takeaways & Limitations

    The paper does not address errors caused by discretizing the image and Fourier measurements, which can be a significant source of compressive-sensing error.

Abstract

from arXiv · show

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 $\ell_1$-minimization and by total variation minimization. The local coherence framework developed in this paper should be of independent interest in sparse recovery problems more generally, as it implies that for optimal sparse recovery results, it suffices to have bounded \emph{average} coherence from sensing basis to sparsity basis -- as opposed to bounded maximal coherence -- as long as the sampling strategy is adapted accordingly.

1 Introduction

The paper studies frequency-domain sampling for images sparse in wavelet or gradient domains, where Fourier and sparsity bases are not fully incoherent. It develops local-coherence-based variable-density sampling with stable reconstruction guarantees.

  • Motivation: Frequency-domain measurements arise in imaging applications including radar, sonar, astronomy, computed tomography, and MRI, motivating measurement reduction without degrading reconstruction.Natural images offer approximately sparse representations in suitable bases or dictionaries.
  • Background: Compressive sensing recovers sparse or approximately sparse signals from relatively few linear measurements when the measurements are sufficiently incoherent with the sparsity basis.This standard theory does not directly resolve Fourier sampling for wavelet-sparse images because the bases are correlated.
  • Prior observations: Empirical studies report better restoration when frequency measurements are sampled from variable densities that prefer low frequencies, although no optimal density had been established.This pattern was observed particularly in compressive sensing MRI and related medical-imaging work.
  • Contributions: The paper derives near-optimal reconstruction bounds for variable-density subsampled Fourier measurements under both wavelet sparsity and gradient sparsity.The bounds cover approximately sparse images through best s-term approximation error, unlike uniform-frequency guarantees stated for exactly sparse images.
  • Local coherence: Local coherence measures correlations between individual sensing vectors and sparsity-basis elements, guiding frequency-dependent sampling densities and Fourier–Haar wavelet estimates.The analysis uses explicit bounds on inner products between discrete Fourier and Haar wavelet rows.
  • Reconstruction: Total variation minimization is shown to provide stable image recovery from variable-density frequency samples when the sensing matrix is suitably related to the Haar wavelet basis.The paper also develops corresponding ℓ1-minimization results in the Haar wavelet domain.

2 Preliminaries

The preliminaries define discrete-image notation, sparsity and approximation error, gradient-based total variation, and the Haar wavelet and discrete Fourier systems used for compressive imaging.

  • Notation: Images are represented as N × N discrete functions f ∈ C^N×N, with pixelwise products described by the Hadamard product.The notation also introduces vector norms and the complex inner product.
  • Sparsity: The ℓ0 count measures nonzero entries, an image is s-sparse when ∥f∥0 ≤ s, and σ_s(f)_p denotes its best s-term approximation error in ℓp.Compressibility corresponds informally to rapid decay of σ_s(f)_1 as s increases.
  • Gradient and total variation: The discrete gradient maps an image to its directional derivatives, and the anisotropic total variation semi-norm is the ℓ1 norm of that gradient.The isotropic and anisotropic versions are equivalent up to a factor of √2.
  • Haar wavelets: The Haar wavelet basis is used because it provides good sparse approximations of natural images and supplies the building blocks for the bivariate construction.The bivariate system is formed from tensor products of univariate functions with matching scaling parameters.
  • Haar wavelets: The univariate Haar system is an orthonormal basis containing a constant function, a step function, and dyadic step functions indexed by scale and location.The paper then extends this system to define the bivariate Haar basis.
  • Fourier measurements: Discrete Fourier measurements use a one-dimensional orthonormal Fourier system and its two-dimensional tensor-product basis, with F_Ω denoting restriction to sampled frequencies Ω.The associated Fourier transform and unitary matrix are used as the measurement system.

3 Main results

The paper establishes stable recovery from appropriately variable-density partial Fourier measurements for both total variation and Haar-wavelet sparsity. The guarantees tolerate measurement noise and sparsity defects, with near-optimal error rates up to logarithmic factors in image dimension.

  • Variable-density partial Fourier sampling yields stable image reconstruction through both total variation minimization and ℓ1-minimization.The result applies to noisy measurements and is obtained with high probability.
  • Total variation minimization: The total-variation estimate approximates the image up to measurement noise and the best s-term approximation error of its gradient.The bound is ∥f − f#∥2 ≲ ∥∇f − (∇f)s∥1 / √s + ε.
  • The error rate is optimal up to logarithmic factors in ambient image dimension when measurement noise is disregarded.The comparison follows from classical lower bounds for the ℓ1-ball; the paper notes that its non-standard noisy model is not covered by those lower bounds.
  • Haar wavelet ℓ1-minimization: m ≳ s log^3(s) log^2(N) measurements support stable Haar-wavelet recovery with high probability.The reconstruction error is controlled by the noise level and the best s-term approximation error in the bivariate Haar basis.
  • The authors identify excess logarithmic factors and their weighted noise model as practical limitations requiring further study.They suspect the additional logarithmic factors are proof artifacts, while empirical studies favor a standard uniform noise model over the weighted model used for the guarantees.

4 Compressive sensing background

Compressive sensing recovers sparse or compressible signals from few measurements when the sensing matrix satisfies suitable incoherence or restricted-isometry conditions. These conditions support stable reconstruction and robustness to measurement noise, including for structured random measurements.

  • Restricted isometry property: ℓ1-minimization relaxes the NP-hard sparsity problem when the sensing matrix has suitable restricted-isometry properties.The RIP requires subsets of columns to be well-conditioned and underpins sparse recovery guarantees.
  • Recovery guarantees: ∥x − x#∥2 ≤ 2σs(x)/√s + ε under noisy measurements satisfying the stated RIP condition.The bound combines the best s-term approximation error with the measurement-noise level.
  • Recovery guarantees: Exact recovery holds for sparse signals under noiseless measurements, while RIP-based recovery also extends to compressible signals.The supplied results state exact recovery when the signal is s-sparse and ε = 0, and stability for broader signal classes.
  • Structured random measurements: Uniformly subsampled Fourier measurements can stably reconstruct sparse signals when the Fourier and sparsity bases are mutually incoherent.The resulting matrices have the RIP with high probability, yielding stable reconstruction through the stated recovery results.
  • Structured random measurements: Bounded orthonormal systems provide RIP guarantees for matrices whose rows are independent random samples from a bounded orthonormal system.The guarantee applies with high probability when the sampling dimension meets the stated sparsity, bound, and logarithmic conditions.

5 Local coherence

Local coherence measures sensing-to-sparsity correlations separately for each sensing vector, enabling sampling distributions adapted to nonuniform coherence. Replacing maximal coherence with its ℓ2 aggregate can reduce measurements while preserving RIP guarantees.

  • Definition: The local coherence function records, for each sensing-basis vector, its largest correlation with any sparsity-basis vector.It is defined coordinate-wise as µloc,j(Φ, Ψ) = sup_k |⟨ϕj, ψk⟩|.
  • Sampling strategy: Adaptive sampling replaces the uniform coherence bound with an ℓ2 bound on local coherence to reduce the number of measurements.Rows are sampled according to a probability measure derived from pointwise upper bounds κ, with diagonal preconditioning D using dj = ∥κ∥2/κj.
  • RIP guarantee: 1 − N^-c log^3(s) is the stated success probability for the preconditioned matrix to have RIP of level δ.The guarantee concerns the restricted isometry constant of (1/√m)DA under the local-coherence sampling scheme.
  • Caveat: The local coherence controls both the embedding dimension and the sampling measure, so suboptimal upper bounds may prevent an a priori optimal dimension guarantee.The paper therefore uses known bounds κ and ∥κ∥2 rather than usually unknown exact local-coherence values.
  • Relation to mutual coherence: For uniformly incoherent bases, the local-coherence theorem generalizes the standard result and is stronger when local coherence is nonconstant.If µ ≤ K N^-1/2, then ∥µloc∥2 ≤ K; equality holds only when µloc is constant.

6 Local coherence estimates for frequencies and wavelets

The paper derives frequency-dependent local coherence bounds between Fourier measurements and Haar wavelets, using tensor-product structure to extend one-dimensional estimates to two dimensions.

  • Theorem 6.2 bounds the local coherence between the two-dimensional Fourier basis and bivariate Haar wavelets.The estimate applies for N = 2^p with p ≥ 8.
  • Bivariate Fourier coefficients decompose into products of univariate coefficients, enabling the two-dimensional bounds to follow from Lemma 6.1.
  • A log_2 N factor in the bound is attributed to the lack of smoothness of Haar wavelets.The authors suggest smoother wavelets might remove this factor.
  • Corollary 6.4 provides corresponding frequency-dependent incoherence estimates for one-dimensional Fourier and Haar bases.

7 Recovery guarantees

The recovery proofs combine local coherence estimates with RIP-based guarantees to establish stable reconstruction for wavelet and gradient sparsity models.

  • Recovery guarantees: The ℓ1-minimization result combines Theorem 6.2 with local-coherence reconstruction guarantees and then applies an RIP recovery theorem.Preconditioning produces the weighted ℓ2 noise norm.
  • Recovery guarantees: Proposition 7.1 supplies decay information for ordered Haar coefficients of mean-zero images.The coefficient ordering is modified because the proposition applies only to mean-zero images.
  • Recovery guarantees: At most 6p Haar wavelets can change across a specified neighboring-edge configuration at a fixed scale, supporting the gradient-to-wavelet constraint argument.
  • Recovery guarantees: The proof assumes a preconditioned Fourier-Haar matrix has the restricted isometry property at a sufficient order and level.
  • Recovery guarantees: The total-variation proof derives cone constraints on the gradient and Haar coefficients before applying an RIP-based stable recovery proposition.

8 Numerical illustrations

Numerical experiments illustrate reconstruction quality under variable-density Fourier sampling, showing comparable errors across several nonuniform schemes and better preservation of fine details than low-frequency-only sampling.

  • MRI image: For the spine image, uniform sampling performs worse visually, whereas variable-density and low-frequency-only sampling have less apparent differences in quality and error.
  • Wet paint image: With 12,000 samples for the 1024^2-pixel wet paint image, inverse quadratic, inverse cubic, and low-frequency sampling have comparable relative ℓ2 errors, while variable-density reconstructions recover more fine details.
  • MRI image: The 256 × 256 MRI reconstructions have relative errors .18, .21, and .19 for the shown distributions.
  • Noise experiments: At a high noise level, uniform sampling fails to recover the image, while power-law and low-frequency sampling yield comparable relative ℓ2 errors around 0.6.
  • Noise experiments: At high noise, inverse quadratic-law sampling reconstructs fine image details better than low-frequency-only sampling.
  • Experimental scope: The experiments omit preconditioning in the regularization term, although the theoretical results include it.The authors identify comparison of noise models and weighting as future work.

9 Summary and outlook

The paper establishes variable-density Fourier recovery guarantees for wavelet and gradient sparsity using local coherence, while identifying several extensions and scope boundaries for future work.

  • The results provide stable reconstruction guarantees for variable-density discrete Fourier measurements in both wavelet and gradient sparsity settings.
  • The local coherence estimates can extend to higher dimensions by induction through the tensor-product structure of the Fourier and wavelet bases.
  • The theory does not directly use the tree-like sparsity structure of natural images in wavelet bases.Incorporating that structure into sampling or reconstruction remains future work.
  • The recovery guarantees are uniform, whereas non-uniform guarantees may reduce the required measurements by several logarithmic factors.
  • The paper does not address errors caused by discretizing images and Fourier measurements.Discrete rather than continuous Fourier representations can be a significant error source.
  • Applying the approach to infinite-dimensional image models is left for future work.
Loading 1210.2380v3…