PaperlayerView exact revision on arXiv

Source-linked AI summary

Coherence-Pattern Guided Compressive Sensing with Unresolved Grids

A. Fannjiang, W. Liao

arXiv:1106.5177v1cs.ITmath.NA

TL;DR

Unresolved grids reduce discretization error but create highly coherent sensing matrices that challenge sparse recovery. The paper combines band exclusion and local optimization with existing compressed sensing algorithms and evaluates the resulting methods. BLOOMP performs best for dynamic range and noise stability, while sparsity and resolution advantages vary with dynamic range and algorithm.

  • Problem

    Sparse reconstruction on grids finer than the Rayleigh threshold faces highly coherent sensing matrices and unstable recovery, motivating methods for unresolved grids.

  • Method

    The paper embeds band exclusion and local optimization into OMP, SP, IHT, BP, and Lasso, producing modified BLO-based algorithms.

  • Results

    BLOOMP is the best performer for dynamic range and noise stability; for sparsity, it leads at high dynamic range, while BP-BLOT and Lasso-BLOT lead near unity dynamic range.

  • Takeaways & Limitations

    BLOOMP offers the strongest overall performance on dynamic range and noise stability, while BP-BLOT provides the highest resolving power up to a certain dynamic range.

  • Takeaways & Limitations

    The approach assumes objects are widely separated, and small gridding error requires objects to be a priori close to grid points.

Abstract

from arXiv · show

Highly coherent sensing matrices arise in discretization of continuum imaging problems such as radar and medical imaging when the grid spacing is below the Rayleigh threshold. Algorithms based on techniques of band exclusion (BE) and local optimization (LO) are proposed to deal with such coherent sensing matrices. These techniques are embedded in the existing compressed sensing algorithms such as Orthogonal Matching Pursuit (OMP), Subspace Pursuit (SP), Iterative Hard Thresholding (IHT), Basis Pursuit (BP) and Lasso, and result in the modified algorithms BLOOMP, BLOSP, BLOIHT, BP-BLOT and Lasso-BLOT, respectively. Under appropriate conditions, it is proved that BLOOMP can reconstruct sparse, widely separated objects up to one Rayleigh length in the Bottleneck distance {\em independent} of the grid spacing. One of the most distinguishing attributes of BLOOMP is its capability of dealing with large dynamic ranges. The BLO-based algorithms are systematically tested with respect to four performance metrics: dynamic range, noise stability, sparsity and resolution. With respect to dynamic range and noise stability, BLOOMP is the best performer. With respect to sparsity, BLOOMP is the best performer for high dynamic range while for dynamic range near unity BP-BLOT and Lasso-BLOT with the optimized regularization parameter have the best performance. In the noiseless case, BP-BLOT has the highest resolving power up to certain dynamic range. The algorithms BLOSP and BLOIHT are good alternatives to BLOOMP and BP/Lasso-BLOT: they are faster than both BLOOMP and BP/Lasso-BLOT and shares, to a lesser degree, BLOOMP's amazing attribute with respect to dynamic range. Detailed comparisons with existing algorithms such as Spectral Iterative Hard Thresholding (SIHT) and the frame-adapted BP are given.

1. Introduction

The paper addresses sparse reconstruction on unresolved, highly coherent grids, where finer discretization reduces gridding error but increases column correlation and destabilizes recovery. It proposes band exclusion and related algorithmic approaches for widely separated objects.

  • Compressive sensing reconstructs high-dimensional sparse signals from sparse linear measurements in imaging, inverse problems, and signal processing.
  • The Rayleigh length is the minimum resolvable frequency-domain length for time sampling on [0, 1], and traditional inversion requires grid spacing of at least 1 RL.
  • Refining the grid roughly decreases relative gridding error inversely with the refinement factor, while increasing mutual coherence through highly correlated neighboring columns.
  • For a 100×4000 matrix with F = 20, a persistent coherence band surrounds each diagonal, and the associated 100 × 30 submatrix can have condition number exceeding 10^15.
  • The paper assumes widely separated objects and develops algorithmic approaches with performance guarantees for recovery on unresolved grids.
  • Band exclusion modifies OMP by avoiding coherence bands around previously estimated support, while the paper also embeds related techniques in other compressed sensing algorithms.

2. Band Exclusion (BE)

Band Exclusion uses coherence bands to prevent greedy pursuit from selecting nearby, highly correlated indices. Its BOMP variant has a support-localization guarantee under separation and recovery conditions, with performance depending on dynamic range.

  • Band Exclusion is introduced as a technique embedded in Orthogonal Matching Pursuit to exploit prior information that objects are widely separated.
  • BOMP avoids the double η-band around the previously estimated support during each matching step, assuming coherence bands of true support indices are pairwise disjoint.
  • BOMP reconstructs support inside the η-coherence band of the true support, with every recovered nonzero associated with a unique true nonzero component.
  • When dynamic range xmax/xmin = O(1), Theorem 1 guarantees approximate recovery of an O(η^-1) sparsity pattern by BOMP.
  • Numerically, BOMP degrades for large dynamic ranges but can resolve objects separated by close to 1 RL when dynamic range is near 1.

3. Local Optimization (LO)

Local Optimization (LO) improves a current support estimate by testing nearby locations and choosing amplitudes that reduce the residual. Embedded in BOMP, LO yields BLOOMP and improves practical recovery, especially across dynamic ranges.

  • LO varies one support location at a time within its coherence band while holding other locations fixed, then minimizes the residual over amplitudes.Each local update solves a least-squares problem, keeping the computation relatively inexpensive.
  • BLOOMP combines band exclusion with LO inside Orthogonal Matching Pursuit.At each iteration, it excludes the coherence band of the current support, adds a selected index, applies LO, and recomputes the least-squares estimate.
  • Under the stated assumptions, BLOOMP’s reconstruction support lies within the η-coherence band of the true support, with each recovered component linked to a unique true component.The same support guarantee is inherited from the BOMP and LO analysis.
  • BOMP can fail at moderate dynamic range, whereas LO greatly enhances its practical recovery success and dynamic-range performance.The paper reports that BLOOMP has the best tested performance for noise stability and dynamic range.

4. Band-Excluded Thresholding (BET)

Band-Excluded Thresholding (BET) selects multiple support indices while excluding coherence bands, and its locally optimized form extends this strategy to several recovery algorithms. The resulting methods retain band-based support guarantees under stated conditions and improve reconstruction performance on unresolved grids.

  • BET extends band exclusion to selecting s objects simultaneously.Its two forms are Band-excluded Matched Thresholding (BMT) and Band-excluded Locally Optimized Thresholding (BLOT).
  • BMT selects the s largest matched-filter values outside previously excluded coherence bands and then solves a least-squares problem on the selected support.The support is built iteratively while excluding the double η-band of the current support.
  • Under its assumptions, BMT reconstructs a support contained in the η-coherence band of the true support, with each nonzero recovered component associated uniquely.The guarantee is stated under conditions weaker than those used for BOMP.
  • BLOT adds local optimization to thresholding and can enhance reconstruction with unresolved grids.It applies local optimization to a thresholded estimate before producing the final least-squares reconstruction.
  • BET variants are embedded in SP, CoSaMP, IHT, BP, and Lasso, producing faster alternatives or improved unresolved-grid reconstructions.The paper names BLOSP, BLOCoSaMP, BLOIHT, BP-BLOT, and Lasso-BLOT; BLOT’s novelty is its combination of band exclusion and local optimization.

5. Numerical study

The numerical study compares band-excluded and locally optimized algorithms across dynamic range, noise, measurement count, and resolution. BLOOMP performs especially strongly for dynamic range and noise, while BP-BLOT leads resolution in the tested range and performance depends on task conditions.

  • The experiments evaluate success probability against dynamic range, noise level, measurement count, and resolution using separated sparse objects.Success is based on every reconstructed object lying within 1 RL of the true support, equivalent to a Bottleneck-distance criterion.
  • Band exclusion: BOMP has the strongest band-exclusion-only performance for dynamic range, noise, and higher-dynamic-range measurement counts, while BSP leads at dynamic range 1.
  • Measurements and sparsity: BP/Lasso-BLOT with the optimized regularization choice performs best for dynamic range 1 and measurement count, whereas BLOOMP and LOOMP dominate at dynamic range 10.At 10% noise, performance of the other algorithms deteriorates significantly as dynamic range increases, while BLOOMP and LOOMP remain roughly unchanged.
  • Resolution: BP-BLOT has the best resolution up to dynamic range 10, with nearly zero Bottleneck distance from about 1.5 RL, versus about 1.7 RL for the other methods.BLOOMP/LOOMP resolving power improves with dynamic range, while BP-BLOT’s deteriorates.
  • Resolution: Below 1 RL separation, all algorithms recover objects poorly despite residuals vanishing, indicating nonuniqueness of sparse solutions.

6. Comparison with other algorithms in the literature

The paper compares BLO-based recovery with analysis and synthesis approaches for coherent, redundant dictionaries. Across the reported experiments, BLO-enhanced methods often achieve lower reconstruction error or stronger recovery performance, while their effectiveness depends on signal structure and regularization choices.

  • Comparison with existing methods: SIHT and frame-adapted BP rely on RIP-related assumptions that do not apply when A cannot be decomposed as ΦΨ with Φ satisfying RIP.The paper’s coherent sensing setting therefore differs from the assumptions underlying these comparison methods.
  • Signal representation: The analysis coefficients Ψ∗y are neither sparse nor compressible because each widely separated object contributes about 30 significant components within the DFT frame’s coherence bands.The paper attributes the remaining long tail to pairwise interactions in the redundant frame.
  • Experimental setup: The experiments measure relative error ∥ŷ−y∥2/∥y∥2 while varying dynamic range, noise level, and number of measurements.The compared signals contain 10 randomly phased and located objects with dynamic range 1 in the analysis experiments.
  • Performance comparison: For the analysis comparison, BP-BLOT and Lasso-BLOT achieve the smallest relative error across dynamic range, noise, and measurement-count tests.BLOOMP and BLOSP also perform among the best for dynamic range and noise, and can reach the minimum error as measurements increase.

7. Conclusions and Discussions

The paper introduces band exclusion and local optimization for sparse recovery with highly coherent sensing matrices below the Rayleigh threshold. Systematic tests show that BLOOMP is strongest on dynamic range and noise stability, while other BLO variants offer speed or resolution advantages.

  • Methods and scope: Band exclusion and local optimization are embedded in OMP, SP, CoSaMP, IHT, BP, and Lasso to address unresolved grids.The paper reports stronger effects for the SP, CoSaMP, IHT, BP, and Lasso embeddings than for OMP alone.
  • Performance conclusions: BLOOMP is the best performer for dynamic range and noise stability, while sparsity performance depends on dynamic range.BLOOMP leads at high dynamic range; BP-BLOT and optimally regularized Lasso-BLOT lead near unity dynamic range.
  • Resolution and tuning: BP-BLOT has the highest resolving power up to a certain dynamic range, whereas Lasso-BLOT is sensitive to its regularization parameter.These conclusions concern the reported resolution comparisons and parameter dependence.
  • Performance conclusions: BLOOMP improves sparsity performance at larger dynamic range and low noise.The paper identifies this behavior as one of BLOOMP’s notable attributes.
  • Practical alternatives: BLOSP, BLOCoSaMP, and BLOIHT are faster alternatives that retain part of BLOOMP’s advantage on dynamic range.They are presented as alternatives to BLOOMP and BP/Lasso-BLOT.
  • Comparison with prior methods: BLO-enhanced algorithms outperform SIHT and frame-adapted BP for sparse objects separated above the Rayleigh length.The comparison is specifically reported for the paper’s sparse-object recovery setting.
  • Refinement-factor behavior: For sparse, widely separated objects, BLO-based performance is independent of refinement factor F, while synthesis reconstruction errors decrease as F increases.This contrasts with examples in which synthesis performance degrades with redundancy.
Loading 1106.5177v1…