PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-Based Compressive Sensing

Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, Chinmay Hegde

arXiv:0808.3572v5cs.IT

TL;DR

Conventional CS recovers sparse or compressible signals from undersampled measurements, but its measurement requirements do not exploit dependencies among coefficient values and locations. This paper develops model-based CS theory and structured recovery algorithms, introducing structured compressible signals and RAmP. Wavelet-tree and block-sparsity examples provide robust recovery with measurement requirements that scale linearly in the relevant sparsity quantities.

  • Problem

    Standard CS treats coefficients independently, leaving an opportunity to reduce measurements and improve recovery by modeling structured dependencies among coefficient values and locations.

  • Method

    The paper develops model-based CS theory with structured sparse approximation in CoSaMP and IHT, and introduces structured compressible signals with the restricted amplification property.

  • Results

    Wavelet-tree recovery requires M = O(K) measurements, while block-sparse recovery requires M = O(JK), with robust guarantees for structured sparse and compressible signals.

  • Takeaways & Limitations

    Exploiting wavelet-tree and block structure can substantially reduce measurement requirements while supporting robust recovery and better discrimination of signal information from artifacts.

Abstract

from arXiv · show

Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K << N elements from an N-dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm. Standard CS dictates that robust signal recovery is possible from M = O(K log(N/K)) measurements. It is possible to substantially decrease M without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including structural dependencies between the values and locations of the signal coefficients. This paper introduces a model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. A highlight is the introduction of a new class of structured compressible signals along with a new sufficient condition for robust structured compressible signal recovery that we dub the restricted amplification property, which is the natural counterpart to the restricted isometry property of conventional CS. Two examples integrate two relevant signal models - wavelet trees and block sparsity - into two state-of-the-art CS recovery algorithms and prove that they offer robust recovery from just M=O(K) measurements. Extensive numerical simulations demonstrate the validity and applicability of our new theory and algorithms.

I. INTRODUCTION

Model-based compressive sensing extends conventional CS by exploiting dependencies among coefficient values and locations, aiming to reduce measurements while improving recovery robustness. The paper develops theory, algorithms, and examples for wavelet-tree and block-sparse models.

  • Contribution: Structured sparsity can reduce measurement needs and help distinguish true signal information from recovery artifacts.The paper identifies both lower measurement requirements and more robust recovery as benefits of restricting admissible coefficient configurations.
  • Motivation: M = O(K log(N/K)) measurements suffice in standard CS, but richer signal models can reduce the required number by exploiting structured dependencies.Structured models restrict the configurations of large and small coefficients beyond independent sparsity assumptions.
  • Contribution: The theory introduces structured compressible signals and the restricted amplification property as a sufficient condition for robust recovery.RAmP generalizes the role of the conventional restricted isometry property to structured compressible signals.
  • Algorithms: Structured CoSaMP and IHT replace conventional sparse approximation with structured sparse approximation while retaining provable robustness guarantees.The modification is applied to two state-of-the-art greedy CS recovery algorithms.
  • Wavelet trees: M = O(K) measurements suffice for robust recovery of tree-sparse and tree-compressible signals, versus M = O(K log(N/K)) for standard CS.The tree model exploits the smaller number of connected wavelet-tree supports, especially as signal length N increases.
  • Block sparsity: M = O(JK) measurements suffice for block-sparse and block-compressible signals, reducing dependence on signal length N relative to standard CS.For block sparsity, JK is the signal sparsity and the benefit is especially pronounced for large block sizes J.

B. Compressive measurements and the restricted isometry property

Compressive sensing acquires sparse or compressible signals through fewer linear measurements than their ambient dimension, then uses sparsity-aware recovery to reconstruct them. The section establishes the RIP-based measurement and recovery framework and motivates structured models.

  • CS acquires x through M < N linear measurements y = Φx rather than direct or periodic samples.
  • The RIP requires measurement matrices to preserve distances for sparse signals, enabling stable recovery from compressive measurements.Practical algorithms may require higher-order RIP conditions such as 2K-RIP or 3K-RIP.
  • Random Gaussian, Rademacher, or subgaussian matrices satisfy the K-RIP with high probability when M = O(K log(N/K)).
  • Finding the sparsest signal exactly is combinatorial and unstable under noise, motivating polynomial-time convex and greedy recovery methods.
  • Given M = O(K log(N/K)) measurements, ℓ1-based and greedy algorithms provide provably stable recovery near the optimal K-term approximation.
  • Structured sparsity restricts allowable supports or coefficient configurations, including rooted wavelet trees and clustered blocks.These models reduce the degrees of freedom beyond ordinary sparsity.

B. Model-based RIP

The model-based RIP restricts the near-isometry requirement to subspaces allowed by a structured sparsity model. Structured compressibility extends this framework by measuring approximation-error decay within the restricted model.

  • The MK-RIP relaxes the conventional RIP requirement while retaining stable recovery for K-structured sparse signals.
  • Random subgaussian matrices satisfy the MK-RIP with high probability under a measurement bound determined by the number of model subspaces.
  • Fewer measurements are needed when the structured model has substantially fewer subspaces than the conventional sparse model.
  • Structured compressible signals lie near the restricted union of subspaces MK, with their best structured approximation error defining structured compressibility.
  • The paper defines structured compressible classes by requiring approximation errors to decay according to a power-law bound parameterized by s and G.

D. Nested model approximations and residual subspaces

Nested model approximations organize structured compressible signals into residual subspaces whose norms decay across successive approximations. The RAmP controls how measurement amplification grows across these residual components.

  • Structured compressible signals require a recovery condition beyond the model-based RIP because their class is larger than structured sparse signals.
  • The nested approximation property requires each best K-term support to be contained in every larger best K′-term support.
  • Under NAP, a signal decomposes into K-sparse residual partitions belonging to unions of K-dimensional residual subspaces.
  • For structured compressible signals, residual-partition norms decay with the partition index, enabling weaker measurement conditions than unrestricted RIP requirements.
  • The restricted amplification property limits measurement amplification across residual subspaces and balances that growth against residual-norm decay.
  • Random subgaussian matrices satisfy the RAmP with high probability, and its measurement bound is below O(K log(N/K)) when residual-subspace counts grow slowly enough.
  • Model-based recovery algorithms replace best K-term approximation with best structured approximation, reducing measurements or improving accuracy at a fixed measurement count.

A. Model-based CoSaMP

Model-based CoSaMP incorporates structured sparse approximation into a greedy recovery algorithm and provides robustness guarantees for structured sparse and structured compressible signals. Its guarantees remain controlled under small model mismatch, while arbitrary signals revert to conventional measurement scaling.

  • Model-based CoSaMP replaces ordinary best BK-term approximation with best BK-term structured approximation within its iterative greedy steps.
  • The algorithm’s structured sparse recovery guarantee matches standard CoSaMP’s guarantee, but applies only to structured sparse signals.
  • For structured compressible signals, the recovery error decays geometrically with iteration and includes measurement noise and structured approximation-tail terms.
  • The structured compressible guarantee differs from standard CoSaMP’s analogous bound through a constant of 35 instead of 20.
  • Small deviations from structured sparse or structured compressible classes preserve recovery guarantees within a small bounded constant factor.
  • For arbitrary signals far from the model, using M = O(K log(N/K)) measurements yields recovery controlled by the best K-term structured approximation error.

E. Computational complexity of model-based recovery

Model-based recovery trades fewer measurements for structured approximation costs, using tree-structured wavelet coefficients to impose connected-support constraints and enable efficient recovery algorithms.

  • Computational complexity: Structured recovery has two complexity factors: fewer measurements reduce algorithmic cost, while structured sparse approximation adds model-specific computation.Current recovery algorithms are often linear in the number of measurements, but structured approximation can introduce an additional cost.
  • Tree-structured models: Wavelet coefficients from smooth and piecewise smooth signals often cluster along tree branches, motivating a connected tree model.Discontinuities produce chains of large coefficients along tree branches, whereas smooth regions produce small coefficients.
  • Tree-structured models: The tree-sparse model T_K is the union of K-dimensional subspaces whose supports are connected subtrees of the wavelet coefficient tree.A connected subtree includes each selected coefficient’s parent and defines a subspace with coefficients outside the subtree set to zero.
  • Model complexity: T_K contains at most 4^K+4 subspaces for K < log2 N and is bounded more generally by (2e)^K+1.These bounds quantify how restricting supports to connected subtrees reduces the number of possible signal subspaces.
  • Recovery algorithms: The condensing sort and select algorithm solves the tree-constrained K-term approximation through a greedy search over subtree energies, with O(N log N) computations.An alternative Lagrangian formulation can be solved in O(N) computations using coarse-to-fine dynamic programming, but its tuning parameter does not transparently determine K.

C. Tree-compressible signals

Tree-compressible signals are modeled through wavelet-tree structure, enabling stable recovery with measurement counts linear in sparsity. Experiments show lower measurement requirements than standard recovery, while preserving noise robustness and offering image-recovery gains.

  • Tree-compressible signal model: Tree approximation classes model wavelet coefficients with loose decay across coarse-to-fine scales and connect to Besov-space signals.For sampled Besov signals under the stated smoothness conditions, wavelet coefficients belong to the tree approximation space.
  • Measurement guarantees: M = O(K) measurements suffice for robust recovery of tree-sparse and tree-compressible signals, improving on conventional M = O(K log(N/K)).The resulting stable-recovery measurement bound is linear in K and independent of N.
  • Numerical recovery performance: Model-based recovery attains near-perfect recovery at M = 3K measurements, while CoSaMP matches this performance at M = 5K.At M = 3K, tree-based recovery also requires fewer iterations and yields much smaller recovery error than standard recovery.
  • Numerical recovery performance: The model-based measurement requirement remains constant as signal length N grows, whereas standard recovery requires increasing measurements.For the tested target error, doubling N increases standard recovery’s required measurements by K, while model-based recovery remains constant.
  • Noise robustness: Model-based recovery has similar noise-stability curves to CoSaMP and ℓ1-norm minimization while using significantly fewer measurements.The comparison measures maximum normalized recovery error over 200 noisy trials as a function of expected measurement signal-to-noise ratio.
  • Image example: For the 16384-pixel Peppers image, wavelet tree-based recovery is compared with conventional CoSaMP using M = 5000 compressive measurements.The experiment uses a 128 × 128 image and evaluates both recovery methods under the same measurement count.

VI. EXAMPLE: BLOCK-SPARSE SIGNALS AND SIGNAL ENSEMBLES

The block-sparse model groups significant coefficients into shared-support blocks or signal ensembles and supplies corresponding approximation and recovery procedures. Its block-compressible extension characterizes power-law block decay and supports robust recovery guarantees.

  • Block-sparse model: Block-sparse signals restrict entire columns to be zero or nonzero, with sparsity measured by the number K of nonzero columns.A K-block sparse signal has coefficient sparsity KJ because each active block contains J entries.
  • Block-sparse model: The model also represents ensembles of J length-N signals that share a common coefficient support.The ensemble is arranged as a matrix whose rows are the constituent signals and whose structure matches the block-sparse matrix representation.
  • Approximation algorithm: Block-based approximation minimizes ℓ2,2 error subject to at most K nonzero columns and is implemented by retaining the K columns with largest ℓ2 norms.The corresponding sorting implementation has complexity O(NJ + N log N).
  • Block-compressible model: s-block compressible signals have sorted block norms that decay according to a power law, yielding approximation-error bounds in mixed norms.The supplied bounds are ∥X − X_K∥_(2,2) ≤ G1K^-s and ∥X − X_K∥_(2,1) ≤ G2K^(1/2−s).
  • Recovery guarantees: Because block-compressible residual sets are identical across scales, the corresponding restricted amplification property follows from the block-sparse restricted isometry property.This lets the same measurement-matrix requirement support both block-sparse and block-compressible recovery guarantees.
  • Recovery guarantees: The block-based recovery theorem guarantees estimates comparable to approximations using a small number of nonzero columns, with exact block-sparse signals eliminating the approximation term.For K-block sparse signals, the mixed-norm approximation error is zero, yielding the theorem’s sparse-signal specialization up to a constant factor.

D. Stable block-based recovery from compressive measurements

The paper develops block-structured recovery guarantees and experiments showing that model-based CoSaMP improves recovery quality, measurement efficiency, and runtime over conventional recovery for block-sparse and block-compressible signals.

  • Stable recovery guarantees: M = O(JK + K log(N/K)) measurements suffice for robust block-sparse recovery, improving on conventional O(JK log(N/K)) scaling.When J > log(N/K), this becomes O(KJ), linear in the signal sparsity JK.
  • Block-sparse experiments: At N = 4096, K = 6, J = 64, and M = 960, block-based recovery avoids the spurious nonzeros and magnitude attenuation observed with conventional CoSaMP.The experiment directly illustrates the advantage of enforcing the block-sparsity model.
  • Block-compressible experiments: For block-compressible signals, structured recovery produces a solution close to the best 5-block approximation even with measurements below conventional stable-recovery requirements.The corresponding example uses M = 200 measurements.
  • Comparative performance: CoSaMP matches model-based recovery only for M ≥ 5K, while block-based recovery generally converges faster.The runtime advantage is attributed to sorting fewer coefficients and requiring fewer iterations.
  • Recovery algorithms: The model-based framework integrates structured sparse approximation into CoSaMP and IHT while retaining provable robustness for structured sparse and compressible signals.The approach replaces each algorithm’s nonlinear sparse approximation step with a structured sparse approximation.
  • Scope and future work: The framework is limited to union-of-subspaces models and motivates future structured models with efficient structured sparse approximation algorithms.The authors identify more complex geometries, including high-dimensional polytopes and nonlinear manifolds, as possible extensions.

APPENDIX A PROOF OF THEOREM 2

This appendix establishes a theorem for structured compressible recovery by bounding measurement amplification over structured residual subspaces and deriving the required measurement conditions. It then applies the theorem to model-based IHT, whose experiments show improved accuracy and convergence over standard IHT.

  • Proof of Theorem 2: The proof bounds the probability that a subgaussian measurement matrix violates the restricted amplification property on fixed supports and residual subspace sets.It uses singular-value concentration and union bounds over structured supports and residual subspaces.
  • Structured compressible signals: The theorem decomposes a structured compressible signal into successive structured sparse approximation differences and bounds their measured norms.Each residual piece lies in a structured model class, allowing the restricted amplification property to control it.
  • Proof conclusion: The proof concludes by combining the residual bounds with an approximation-tail estimate to establish the stated recovery guarantee.The appendix explicitly closes the argument after the approximation and norm estimates.
  • Model-based IHT: Model-based IHT replaces hard thresholding with structured sparse approximation and updates the residual iteratively from the measurement error.Each iteration forms a gradient-like estimate, prunes it according to the model, and updates the measurement residual.
  • IHT experiment: For the HeaviSine experiment with N = 1024 and M = 80, model-based IHT converges in fewer steps and yields more accurate recovery than standard IHT.Figure 10 compares the two reconstructions using normalized RMSE.

APPENDIX D PROOF OF THEOREM 4

This appendix proves the model-based CoSaMP recovery theorem by adapting the conventional proof to structured sparsity. The argument combines structured identification, support merging, estimation, pruning, and a contraction recursion.

  • Proof structure: The proof adapts the conventional CoSaMP lemmas to structured sparsity, while retaining the same six-lemma proof architecture.Lemma 4 is unchanged; the other lemmas are restricted or modified for the structured model.
  • Residual formulation: At each iteration, the residual is written as r = Φs + n, where s is the current signal error and n is measurement noise.This representation supplies the input for structured identification.
  • Identification: Structured identification selects a support corresponding to a model subspace from a structured approximation of the proxy Φ^T r.The selected support is used to construct the candidate support for subsequent estimation.
  • Estimation and pruning: Support merger, least-squares estimation, and structured pruning produce the next K-structured approximation.The appendix states these operations as the merger, estimation, and pruning lemmas.
  • Recovery bound: The error recursion contracts geometrically, yielding ∥x − bxi∥2 ≤ 2^-i∥x∥2 + 15∥n∥2.The bound separates an iteration-decaying signal term from a noise-dependent term.

APPENDIX E PROOF OF PROPOSITION 1

This appendix proves a proposition by counting structured binary-tree supports across different size regimes and bounding the resulting combinatorial sums. The derivation uses subtree enumeration, asymptotic identities, and Gaussian-moment calculations.

  • Small-support regime: When K < log2 N, the number of binary-tree subtrees of size K is counted using Catalan numbers.This provides the small-K support-counting regime.
  • Large-support regime: When K > log2 N, the subtree count is partitioned by height h and analyzed through the numbers tK,h of subtrees of size K and height h.The appendix invokes an asymptotic identity before simplifying the resulting sum.
  • Sum bounding: The proof bounds the dominant sum term by locating its maximum and comparing the increasing and decreasing portions around that maximum.The analysis treats multiple cases depending on the relationship between the maximizing point and the integration bounds.
  • Auxiliary calculation: A change of variables and the fourth central moment of a Gaussian distribution are used in the auxiliary calculation.The appendix defines u = 2πx and σ before evaluating the relevant expression.
  • Conclusion: The proposition follows after the asymptotic and integral estimates are combined.The appendix ends by stating that the derived bound proves the proposition.

APPENDIX F PROOF OF PROPOSITION 3

The appendix completes the proof of Proposition 3 by bounding the required measurement count through a subspace-count expression and simplifying its dependence on K and j.

  • Subspace-count bound: The proof begins by expressing the bound as M ≥ max over j from 1 to ⌈N/K⌉ of M_j.This uses the stated subspace count from (17).
  • Final bound components: The resulting algebraic expressions retain terms involving K, Kj, and t in the denominator structure.These terms appear in the displayed forms K(Kj + 1)(Kj + K + 1) + 2t and related expressions.
  • Algebraic simplification: The derivation separates terms linear in K and j to simplify the measurement bound.The resulting expressions include K(3 + 4 ln 2) and 8Kj(1 + ln 2).
  • Monotonicity: The proof uses a decreasing-sequence argument for the relevant expression because the denominators decrease whenever s > 0.5.This establishes the ordering needed for the subsequent bound.
  • Conclusion: The appendix concludes by stating that the proof of Proposition 3 is complete.The proposition proof ends with a formal completion marker.
Loading 0808.3572v5…