PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-Optimal Adaptive Compressed Sensing

Matthew L. Malloy, Robert D. Nowak

arXiv:1306.6239v2cs.ITstat.ML

TL;DR

The paper addresses whether adaptive compressed sensing can achieve lower SNR requirements without increasing the measurement burden. It introduces CASS, a simple adaptive sensing and group testing procedure using order k log n measurements, and reports near-optimal SNR scaling, lower computational intensity, and better simulated performance. The broader result is that adaptive compressive methods can improve detection and estimation relative to non-adaptive approaches, although the method assumes adaptive measurements and additive Gaussian noise.

  • Problem

    Prior work had not established whether adaptive compressed sensing could achieve the necessary log k SNR scaling while using only order k log n measurements.

  • Method

    The paper proposes CASS, a simple adaptive compressed sensing and group testing procedure that progressively partitions the signal and uses prior measurements to guide sensing.

  • Results

    CASS achieves near-optimal SNR dependence with order k log n measurements, and simulations show better performance than standard compressed sensing and non-adaptive direct sensing.

  • Takeaways & Limitations

    Adaptive compressed sensing can improve detection and estimation performance beyond reducing measurement count, including relative to non-adaptive direct sensing.

Abstract

from arXiv · show

This paper proposes a simple adaptive sensing and group testing algorithm for sparse signal recovery. The algorithm, termed Compressive Adaptive Sense and Search (CASS), is shown to be near-optimal in that it succeeds at the lowest possible signal-to-noise-ratio (SNR) levels, improving on previous work in adaptive compressed sensing. Like traditional compressed sensing based on random non-adaptive design matrices, the CASS algorithm requires only k log n measurements to recover a k-sparse signal of dimension n. However, CASS succeeds at SNR levels that are a factor log n less than required by standard compressed sensing. From the point of view of constructing and implementing the sensing operation as well as computing the reconstruction, the proposed algorithm is substantially less computationally intensive than standard compressed sensing. CASS is also demonstrated to perform considerably better in practice through simulation. To the best of our knowledge, this is the first demonstration of an adaptive compressed sensing algorithm with near-optimal theoretical guarantees and excellent practical performance. This paper also shows that methods like compressed sensing, group testing, and pooling have an advantage beyond simply reducing the number of measurements or tests -- adaptive versions of such methods can also improve detection and estimation performance when compared to non-adaptive direct (uncompressed) sensing.

I. INTRODUCTION

Adaptive sensing targets sparse-signal recovery at lower SNR than non-adaptive sensing while retaining about k log n measurements. CASS provides a simple, computationally lighter adaptive procedure with near-optimal guarantees and strong simulated performance, subject to hardware and noise-model assumptions.

  • Motivation: Adaptive sensing can recover k-sparse signals when SNR scales like log k, versus log n for standard non-adaptive sensing.Both approaches require about k log n measurements.
  • CASS contribution: CASS is a simple adaptive sensing algorithm that achieves the log k SNR scaling while using order k log n measurements.The paper presents this as a near-optimal guarantee for adaptive compressed sensing.
  • CASS contribution: CASS is less computationally intensive than standard compressed sensing for sensing construction, implementation, and reconstruction.The algorithm could be realized in existing compressive systems including digital micromirror devices.
  • Empirical results: 2-8 dB: CASS consistently outperforms standard compressed sensing on natural and synthetic image test signals.The paper attributes the practical advantage partly to lower required SNR and partly to reduced post-measurement computation.
  • Broader implication: Adaptive compressed sensing with k log n measurements can be more reliable than non-adaptive direct sensing when signals are sufficiently sparse.This extends the value of compression beyond measurement reduction to detection and estimation performance.
  • Limitations: Adaptive measurements may require more flexible hardware, and the analysis assumes adaptive sensing is feasible under additive Gaussian noise.Digital micromirror systems are cited as an example where adaptive measurements could be realized.

B. Main Results and Contributions

CASS is a simple adaptive compressed sensing procedure that achieves sufficient SNR scaling with order k log n measurements, including exact recovery for non-negative signals and near-complete recovery for signed signals. Its theoretical guarantees are supported by numerical results showing strong performance and removal of logarithmic dependence on dimension.

  • Theoretical guarantees: CASS requires only order k log n measurements and succeeds when the minimum non-zero entry scales with M log k, completing the adaptive compressed sensing result.The paper identifies this scaling as sufficient and optimal in dependence on SNR and dimension.
  • Theoretical guarantees: For non-negative signals, CASS achieves exact support recovery with probability greater than 1 −δ under its minimum-amplitude condition.The guarantee is stated for the proposed CASS procedure.
  • Resource use: CASS requires exactly m = 2k log2(n/k) measurements and has total sensing energy Pm^2 = M in the stated result.The measurement count is paired with the paper’s total sensing-energy constraint.
  • Theoretical guarantees: For signals with positive and negative entries, CASS recovers at least a fraction 1 −ǫ of non-zero components on average under a corresponding magnitude condition.This signed-signal guarantee uses fewer than 2k log2(n/k) + 8k/ǫ measurements.
  • Empirical results: Numerical experiments show CASS outperforms standard compressed sensing on modest-size problems, with performance not deteriorating as dimension grows.The experiments include comparisons involving standard compressed sensing, direct sensing, and approximately sparse signals.

C. Prior Work

Prior work established adaptive sensing’s potential to improve SNR requirements, while earlier adaptive compressed sensing methods approached but did not complete the optimal bound. CASS differs through its sensing-energy allocation and connects adaptive compressed sensing to noisy adaptive group testing.

  • Earlier adaptive compressed sensing: Earlier adaptive compressed sensing procedures approached the lower bound while using order k log n measurements, but their guarantees retained logarithmic factors.The cited procedures include bisection-based and sequential compressed sensing approaches.
  • CASS relative to prior work: CASS distinguishes itself by allocating less sensing energy to initial bisection steps and more to later steps, removing sub-optimal dimension dependence from the SNR requirement.Earlier bisection procedures aimed to equalize the probability of error across steps.
  • Connection to group testing: CASS forms adaptive partial sums and first isolates defective items with groups of size approximately n/k, paralleling generalized binary splitting under a real-valued noisy model.Its main difference from generalized binary splitting is the allocation of sensing energy across passes to handle additive Gaussian noise.
  • Connection to group testing: The paper suggests that CASS’s stage-wise measurement allocation could compensate for a fixed probability of error per measurement in noisy adaptive group testing.This proposed connection extends the discussion beyond the compressed sensing measurement model.
  • Problem setting: The sensing model uses sequentially designed rows of A based on prior observations, under a total sensing-energy constraint that decouples energy from measurement count.The paper assumes n and k are powers of two for presentation, and allows this assumption to be relaxed at increased constants.

III. COMPRESSIVE ADAPTIVE SENSE AND SEARCH

CASS adaptively searches for sparse support by partitioning the signal, measuring partitions, and repeatedly bisecting the most promising ones. Its sensing-energy allocation increases reliability across later search steps while satisfying the total energy constraint.

  • CASS search procedure: CASS partitions the signal, tests each partition, and repeatedly bisects the supports associated with the largest measurements.The procedure ultimately returns k estimated support indices and coefficient estimates.
  • Algorithm inputs: CASS uses inputs k, total sensing budget M, and an initial scale parameter ǫ, with ǫ = 1 as the default.The algorithm initializes its partition list and iterates through the search steps using measurements with Gaussian noise.
  • CASS search procedure: The initial step divides the signal into ℓ0 dyadic partitions, where ℓ0 is the smaller of n or the next power of two above 4k/ǫ.Each initial sensing vector is supported on one dyadic sub-interval.
  • CASS search procedure: After the initial step, CASS takes 2k measurements per step and bisects the k most promising support sets to define the next supports.The final step uses single-index supports and produces the support estimate and coefficient estimates.
  • Sensing-energy allocation: The sensing allocation makes vector amplitudes grow polynomially while supports shrink geometrically, decreasing sensing energy and increasing reliability across steps.The parameter γ enforces equality with the total sensing-energy constraint.

B. Theoretical Guarantees

Theoretical guarantees distinguish non-negative signals from signals with both positive and negative entries. CASS provides exact or approximate support-recovery guarantees with measurement requirements that are near-optimal up to constant factors.

  • Guarantee regimes: CASS theory provides separate guarantees for non-negative signals and signals containing both positive and negative entries.Theorem 1 addresses non-negative signals, while Theorem 2 bounds expected support-recovery error for signed signals.
  • Signed signals: For signed signals, cancellation can occur when two non-zero components share a sensing vector, so Theorem 1 does not apply directly.Reducing ǫ increases the number of initial partitions and reduces cancellation.
  • Signed signals: Theorem 2 guarantees expected support error E[d(Ŝ,S)] ≤ kǫ when the support is chosen uniformly at random.The theorem concerns the expected fraction of recovered components for signed signals.
  • Measurement complexity: When k/ǫ is a power of two, the procedure uses exactly 4k/ǫ + 2k log2(nǫ/4k) measurements.This gives an explicit measurement count for the signed-signal guarantee.

C. Discussion

The discussion compares CASS with lower bounds and prior bisecting-search methods. It emphasizes that CASS removes a doubly logarithmic term in one comparison and achieves theorem bounds that are tight within constant factors.

  • Comparison with lower bounds: CASS requires order k log n measurements when ǫ ≥ 1/log n to recover a fraction 1 − ǫ of the support in expectation.For controlling exact-support error with ǫ < 1/k, the measurement requirement increases to order k^2 while the SNR requirement remains essentially unchanged.
  • Comparison with lower bounds: For exact support recovery, CASS can require order k^2 measurements when ǫ < 1/k, despite an essentially unchanged SNR requirement.The paper identifies signed compressive recovery as more difficult in this setting.
  • Comparison with lower bounds: Theorem 1 implies an expected support-error bound with a 2 log k + log 16 term, and the paper states that the theorems are tight within constant factors.The comparison converts exact-support error into expected support error using δ = ǫ/2k.
  • Relation to prior methods: CASS shares repeated support bisection with earlier adaptive compressed-sensing procedures, while its discussion contrasts different sensing-vector allocations across search steps.Prior work also proposed partitioning strategies to isolate non-zero entries.
  • Comparison with prior work: CASS removes the doubly logarithmic log log^2 n term in a prior bound and comes within a constant factor of the corresponding lower bound.The comparison addresses the single-nonzero-entry recovery setting discussed in the cited prior work.

IV. NUMERICAL EXPERIMENTS

The numerical experiments evaluate CASS against non-adaptive compressed sensing and direct sensing under matched sensing energy. Across synthetic and image experiments, the reported results show stable CASS performance as dimension grows and practical gains over comparison methods in sufficiently large problems.

  • Synthetic signals: CASS remains constant in empirical performance as n increases for 1-sparse recovery, while OMP and direct-sensing error probabilities increase.The comparison uses equal total sensing energy and 10,000 trials for each n.
  • Synthetic signals: For sufficiently large n, CASS outperforms direct sensing in 1-sparse recovery and in the equal-magnitude signed-signal experiments.The signed-signal experiments compare CASS with LASSO and direct sensing as dimension or SNR varies.
  • Signed-signal experiments: Setting ǫ = 1/8 greatly reduces the signed-signal cancellation error floor, which is around d(Ŝ,S)/(2k) = 0.10 with the default scale.The reduction is visible in both SNR- and dimension-based experiments.
  • Computational considerations: LASSO was evaluated only up to n = 2^18 because solving it with a dense sensing matrix becomes computationally prohibitive at larger sizes.The paper contrasts this computational limitation with stable CASS performance as n grows.
  • Natural-image experiments: The image experiment compares CASS, LASSO, G-LASSO, and direct sensing on 20 image classes with equal total sensing energy.The images are approximately sparse in the Haar basis, and results are averaged over each class.

CS (LASSO)

Across image experiments, CASS outperformed traditional compressed sensing with LASSO in reconstruction quality, while using the same measurement counts and offering lower computational burden. The comparison also shows that adaptive compressed sensing can outperform direct sensing under some conditions.

  • CASS universally outperformed both G-LASSO and standard CS on all image sets and SNRs evaluated.
  • At −8 dB, traditional compressed sensing produced an essentially unrecognizable handwritten-eight reconstruction, whereas CASS remained recognizable.
  • 4-8 dB: CASS’s PSNR advantage over compressed sensing on the handwritten-eight experiment.
  • 2-4 dB: CASS’s PSNR advantage over compressed sensing for the Cameraman image.
  • The CASS procedure’s theoretical SNR bound includes a leading constant of 20, which the paper identifies as significant in practice.
  • CASS can outperform direct sensing when the signal is sufficiently sparse, and simulations observed this even for k ≥n1/10.

APPENDIX A

Appendix A establishes CASS’s measurement construction and support-recovery argument, then presents image-comparison settings for CASS, traditional compressed sensing, and direct sensing. The proof uses staged measurements, thresholding, Gaussian tail bounds, and union bounds.

  • CASS’s sensing construction uses an initial measurement stage followed by stages requiring 2k measurements each, with ℓ0 = 4k.
  • Figure 5 compares CASS, Gaussian-ensemble compressed sensing with LASSO, and direct sensing for handwritten-eight recovery at three SNRs.
  • Each sensing vector has support n2−(s−1)/ℓ0 and amplitude Ms/(γn) at step s.
  • Support recovery succeeds if nonzero-containing measurements remain above thresholds while noise-only measurements remain below them across all stages.
  • The proof sets τs = xminas/2, separating nonzero-containing measurements with positive means from zero-mean noise measurements.
  • Figure 6 repeats the comparison for Cameraman with k = 2048 and m = 20480, using CASS, LASSO-based compressed sensing, and direct sensing.

APPENDIX B

Appendix B verifies CASS’s measurement budget and bounds expected support-recovery error through partitioning, isolation, thresholding, and event-probability arguments. The analysis assumes a uniformly random support in part of the proof.

  • The measurement-budget proof bounds the initial partition size using min{n, 4k/ǫ} ≤ℓ0 ≤8k/ǫ.
  • The analysis partitions the signal support and bounds the expected number of nonzero components that become isolated.
  • The event E represents failure to find at least as many true nonzero elements as were isolated in the first partition.
  • Because the procedure returns exactly k indices, the support estimate is constrained to have fixed cardinality.
  • Thresholding isolated components against noise-only measurements allows the proof to bound the probability of event E using Gaussian tail estimates.
  • The proof concludes that the expected symmetric support error satisfies E[d(bS, S)] ≤ kǫ.
Loading 1306.6239v2…