PaperlayerView exact revision on arXiv

Source-linked AI summary

LS-CS-residual (LS-CS): Compressive Sensing on Least Squares Residual

Namrata Vaswani

arXiv:0911.5524v2cs.IT

TL;DR

The paper studies causal reconstruction of sparse signal sequences with unknown, slowly changing supports from few noisy linear measurements. It proposes LS-CS, which applies compressed sensing to a least-squares residual based on the previous support, and derives error and stability guarantees supported by simulations. These guarantees require sufficiently small support changes and model-specific conditions.

  • Problem

    The problem is to recursively reconstruct sparse signal sequences with unknown, time-varying supports from limited noisy measurements while using temporal support dependence.

  • Method

    LS-CS computes a least-squares residual using the previous support estimate, applies compressed sensing to that residual, and updates the support through detection, deletion, and least-squares steps.

  • Results

    The paper derives CS-residual error bounds that are much smaller than CS bounds when measurements are scarce and support changes are small, and establishes time-uniform support-error and reconstruction-error bounds under its signal model.

  • Takeaways & Limitations

    Using slowly changing support information turns the dynamic reconstruction problem into noisy CS with partly known support and can improve accuracy while retaining simple-CS complexity.

  • Takeaways & Limitations

    The stability model assumes support changes occur every d time instants; with d=1, stability can still be ensured, but support errors may never become zero.

Abstract

from arXiv · show

We consider the problem of recursively and causally reconstructing time sequences of sparse signals (with unknown and time-varying sparsity patterns) from a limited number of noisy linear measurements. The sparsity pattern is assumed to change slowly with time. The idea of our proposed solution, LS-CS-residual (LS-CS), is to replace compressed sensing (CS) on the observation by CS on the least squares (LS) residual computed using the previous estimate of the support. We bound CS-residual error and show that when the number of available measurements is small, the bound is much smaller than that on CS error if the sparsity pattern changes slowly enough. We also obtain conditions for "stability" of LS-CS over time for a signal model that allows support additions and removals, and that allows coefficients to gradually increase (decrease) until they reach a constant value (become zero). By "stability", we mean that the number of misses and extras in the support estimate remain bounded by time-invariant values (in turn implying a time-invariant bound on LS-CS error). The concept is meaningful only if the bounds are small compared to the support size. Numerical experiments backing our claims are shown.

I. INTRODUCTION

The paper addresses causal reconstruction of temporally varying sparse signals from few noisy measurements, where support changes slowly. LS-CS uses prior support information through least-squares residuals to improve on online simple CS while retaining its complexity.

  • Problem setting: The target problem is recursively reconstructing sparse signal sequences with unknown, time-varying supports from limited noisy incoherent measurements.Applications include dynamic MRI, sensor-network field estimation, single-pixel video, and video compression.
  • Problem setting: Slow support change is a central modeling assumption for exploiting temporal dependence.For the medical-image examples, support changes remain below 2% of support size.
  • Motivation: Existing batch methods are non-causal and computationally expensive, whereas simple CS is online but can have much larger error when measurements are scarce.Simple CS does not use past observations.
  • Contribution: LS-CS replaces CS on the current observation with CS on a least-squares residual computed from the previous support estimate.Its complexity matches simple CS, O(Nm^3), rather than the batch complexity O(N^3m^3).
  • Contribution: The paper develops error bounds, stability conditions, and numerical experiments for LS-CS, using Dantzig selector-based CS.The stability analysis and notation rely on sparsity, slow support changes, and incoherence conditions.

1) More Notation:

LS-CS uses the previous support estimate to form an initial least-squares estimate and residual, then applies CS to that residual before detecting additions and deletions. Because the residual is approximately sparse when support changes are small, this can reduce reconstruction error relative to simple CS.

  • More Notation: The previous support estimate T is partitioned into the unknown current support component ∆ and erroneous component ∆e.∆ contains current support indices outside T, while ∆e contains indices in T absent from the current support.
  • Core idea: Simple CS discards past observations, while LS-CS uses the previous support to compute an initial LS estimate and its residual.The residual-based formulation treats the current signal as having a partly known support.
  • Core idea: When support errors are small and the sensing matrix is sufficiently incoherent, the residual is approximately sparse on ∆ rather than on the full current support.This is the mechanism behind the expected reduction in CS error.
  • Estimation: LS-CS applies Dantzig-selector CS to the residual, then uses detection and least-squares steps to estimate newly added coefficients.The residual estimate can be biased toward zero, motivating the subsequent least-squares refinement.
  • Estimation: If the detected support equals the true support, the resulting least-squares estimate is unbiased and minimizes mean squared error among linear unbiased estimates.A roughly accurate detected support still reduces bias and mean squared error.
  • Support maintenance: Deletion is needed to remove false detections and actual removals; otherwise the estimated support can grow and make the LS system ill-conditioned.Deletion uses the refined estimate rather than the typically higher-error residual estimate.

A. LS CS-residual (LS-CS) Algorithm and More Notation

LS-CS initializes with standard compressed sensing, then recursively estimates the current signal by applying compressed sensing to a least-squares residual based on the previous support estimate. The procedure detects support additions and deletions, updates the least-squares estimate, and includes threshold and robustness heuristics.

  • Algorithm: At t = 0, LS-CS runs standard compressed sensing with n0 > n measurements, then performs support estimation and least-squares estimation.The resulting estimate and support are fed into the recursive procedure.
  • Algorithm: For t > 0, the algorithm computes an initial least-squares estimate and residual using the previous support, then applies compressed sensing to that residual.The residual CS output is combined with the initial estimate before support processing.
  • Algorithm: LS-CS detects support additions, recomputes least-squares estimates, detects deletions, and outputs the updated signal and measurement estimate while feeding back the support.The recursive loop repeats these steps after incrementing t.
  • Implementation: Threshold selection depends on conditioning and noise: larger deletion thresholds can speed removal of extras, while detection caps improve robustness to occasional large noise.When n is small, detections can instead be added until a condition-number threshold is met; a related KF-CS variant uses coefficient-change information.
  • Notation: The analysis bounds CS-residual error in terms of |T| and |∆| and compares it with compressed-sensing error under increasingly strong assumptions.A tighter CS-residual bound is introduced later in the analysis.
  • Notation: The current support is represented using a known part T, additions ∆, and previously estimated elements that are no longer active, ∆e.The notation defines T as the previous-time support estimate and writes N = (T ∪∆) \ ∆e.

A. Bounding CS-residual Error

The paper bounds CS-residual reconstruction error for residuals that are sparse and compressible, including the low-measurement regime where standard CS bounds may not apply. The bound depends on support-estimate size, support changes, and noise.

  • Residual error bound: CS-residual applies CS to the residual ỹ = Aβ + w, where β = x − x̂init is sparse and compressible on the previous support estimate.The residual has support size |T| + |∆|, while its component on T is bounded separately.
  • Residual error bound: When n is large enough that |T| + |∆| ≤ S∗∗, standard CS-residual bounds from prior theorems can be used directly.The paper emphasizes that CS-residual is primarily intended for smaller n.
  • Residual error bound: The analysis first proves a sparse-compressible CS error lemma, then bounds ∥βT∥2, and combines them to obtain the CS-residual error bound.The bound on ∥βT∥2 is small when noise and support changes are small enough.
  • Residual error bound: The resulting corollary assumes bounded noise, |∆| ≤ S∗∗, and |T| ≤ S∗, and is used to prove LS-CS stability.The corollary retains a minimum over candidate values of S; choosing S = |∆| is often useful when |∆| > 0.
  • Scope: Gaussian-noise analogues are possible, but omitted because high-probability results would make stability over time difficult to study.The presented analysis therefore focuses on bounded-noise guarantees.

B. Comparing CS-residual and CS error bounds

Under assumptions of small support changes, suitable coefficient magnitudes, low noise, and few measurements, the CS-residual error bound is significantly smaller than the CS bound. Simulations support this comparison except when measurements are plentiful.

  • Analytical comparison: When measurements are insufficient for standard sparse-signal CS bounds, the sparse-compressible residual analysis remains applicable.This distinction is important in the intended small-n regime.
  • Analytical comparison: The comparison assumes recently added coefficients are no larger than previously established coefficients, support changes and noise are small, and n is small but sufficient for S∗ ≥ 1.1|N|.These assumptions imply that the residual component on the previous support is compressible enough.
  • Analytical comparison: Under these assumptions, FCSres(S) is significantly smaller than FCS(S) for every admissible S, so the corresponding upper bounds are also smaller.The residual bound improves the guarantee rather than directly proving that realized errors are smaller.
  • Scope: If |∆| = 0, the stated analytical comparison does not hold, although B0 is much smaller than the CS bound at sufficiently high SNR.This is an explicit boundary on the comparison argument.
  • Simulation comparison: For m = 200, |N| = 20, |∆| = |∆e| = 2, and n = 45, 59, 100, simulations found much smaller normalized MSE for CS-residual except at n = 100.At n = 100, the two errors were roughly equal.

1) Monte Carlo Comparison:

A tighter CS-residual error bound removes a term proportional to |T|, but it requires a stronger assumption controlling the residual’s compressible component.

  • Tighter bound: The tighter bound is introduced specifically to eliminate a term proportional to |T|, under a stronger assumption.The section is presented as optional for quick reading.
  • Tighter bound: When noise and |∆| are small, the residual’s component on T has a small ℓ1 norm and can be bounded relative to ∥x∆∥1.This stronger control supports applying the sparse-compressible error lemma with S = |∆|.
  • Scope: If |∆| = 0, the stronger condition used for this tighter bound cannot hold.Thus the tighter result excludes the zero-support-change case.
  • Tighter bound: The first term of the tighter minimum does not contain |T| and is tighter when b is small, as can occur with small |∆| and large ∥x∆∥∞.The improvement depends on the stronger residual-compressibility condition.

IV. LS-CS STABILITY

The stability analysis asks when LS-CS keeps misses and extras bounded over time and when support errors disappear after additions. It uses a signal model with gradual additions and removals and three detection/deletion requirements.

  • Stability goals: Stability means bounding misses and extras by time-invariant values, which in turn yields a time-invariant LS-CS error bound.The analysis also asks whether support errors vanish within finite delay after additions.
  • Signal Model: The signal model separates additions, removals, and constant coefficients, with new coefficients increasing gradually and removed coefficients decreasing gradually to zero.Additions and removals occur at scheduled times separated by a nonzero delay.
  • Signal Model: The support size remains roughly constant, equal to S0 or S0 − Sa, and the maximum signal power is bounded by S0M^2.This keeps the modeled sequence from accumulating unbounded support or power.
  • Stability conditions: The stability proof requires large undetected coefficients to be detected, sufficiently large detected coefficients not to be falsely deleted, and extras to be deleted periodically.These conditions control misses and extras across time.
  • Stability conditions: Detection, no-false-deletion, and deletion lemmas provide sufficient conditions based on support-error sizes, noise, and restricted-isometry quantities.The lemmas respectively address detecting undetected coefficients, preserving large detected ones, and removing extras.

C. The Main Result

Theorem 2 establishes LS-CS stability under initialization, threshold, measurement, and signal-model conditions by tracking detections and deletions across four time subintervals. It yields bounded support errors and time-invariant LS-CS and CS-residual error bounds.

  • Stability proof: The proof partitions each interval between support changes into four subintervals and enforces no-false-deletion, detection, and deletion conditions.The construction tracks constant, increasing, and decreasing coefficients through the interval.
  • Initialization: The initialization assumption can be obtained by using more measurements at t = 0 and choosing a sufficiently small detection-error bound.If this is not possible, the authors state that the result changes only slightly.
  • Theorem 2 conditions: Theorem 2 requires correct initialization, suitable thresholds, bounded noise, sufficient measurements, and signal conditions for additions and deletions.The signal conditions include sufficiently rapid coefficient increases, adequate constant magnitudes, and sufficiently spaced support changes.
  • Stability guarantees: Under these conditions, LS-CS has at most Sa misses and f(Sa + d0) extras at every time.The same bounds also apply to the corresponding support errors relative to the true support.
  • Stability guarantees: Within detection delay d0 + Sa − 1, all new additions are detected, extras are removed, and the LS-CS support equals the genie-LS support.This holds over the stated interval after each addition time.
  • Error bounds: Corollary 3 converts the stability result into time-invariant bounds for both LS-CS error and CS-residual error.The bounds use parameters evaluated at ST = S0 + f(d0 + Sa) and S∆ = Sa.
  • Extensions: The authors note that the stability conditions could be weakened using Corollary 2, but do not pursue this to keep the proof simpler.

D. Discussion and Extensions

The discussion interprets the theorem as requiring bounded noise, appropriate thresholds, sufficiently strong coefficient growth and magnitudes, and adequately spaced support changes. Under these assumptions, support errors and reconstruction errors remain bounded, with exact recovery of the genie-LS support after finite delay.

  • Interpretation: The theorem requires bounded noise, enough measurements, suitable thresholds, sufficiently rapid coefficient growth, sufficiently large constant coefficients, and spaced addition times.
  • Interpretation: Stability bounds misses by Sa and extras by f(Sa + d0), while LS-CS reaches the genie-LS support within finite detection delay.The LS-CS and CS-residual errors are also bounded by time-invariant values.
  • Comparison with CS: The measurement requirement Sa ≤ S∗∗ is weaker than the standard CS requirement S0 ≤ S∗∗.
  • Comparison with CS: The condition S0 + f(d0 + Sa) ≤ S∗ is weaker than 2S0 ≤ S∗, and condition 3b is also weaker when f, d0, and Sa are small.
  • Limitations: Assuming support changes every d time instants is somewhat restrictive but is needed to guarantee that support errors eventually become zero.With d = 1, stability can still be shown, but support errors may never vanish.
  • Limitations: A large coefficient-decrease time r makes condition 6 difficult to satisfy and can permit false deletion of small decreasing coefficients.The authors state that such deletions would only slightly increase next-step CS-residual error and may still permit a stability proof after modifications.

V. NUMERICAL EXPERIMENTS

The experiments compare CS-residual with CS and test LS-CS stability under lower SNRs and faster support additions. Across these settings, LS-CS achieves substantially lower or stable reconstruction error.

  • A. Comparing CS-residual with CS: 100 simulations compare CS-residual and CS using normalized MSE across three measurement counts and four noise levels.CS-residual uses λ = 4σ, while CS uses three λ choices.
  • A. Comparing CS-residual with CS: Except when n = 100, CS-residual significantly outperforms CS; at n = 100, CS is better for σ = 0.04 and both methods are similar for σ = 0.09.
  • B. Verifying LS-CS stability: LS-CS achieved NMSE ≤0.4%, compared with 30-40% for CS with small λ in the stability experiment.
  • C. Lower SNR and faster additions: For slow additions, LS-CS NMSE remained stable at 2.5%, while CS errors were 40-60%.The slow-adds setting used d = 8, n = 59, and lower SNRs than the stability simulation.

D. Dynamic MRI reconstruction example

The paper applies LS-CS to reconstruct a sparsified cardiac image sequence from 35% simulated MRI measurements. The authors place this example within broader comparisons using actual MR data and BPDN reported elsewhere.

  • D. Dynamic MRI reconstruction example: LS-CS accurately reconstructs a sparsified cardiac image sequence from only 35% simulated MRI measurements.
  • D. Dynamic MRI reconstruction example: Detailed comparisons for actual, nonsparsified image sequences and practical MR acquisition schemes, including BPDN, are given in.
  • D. Dynamic MRI reconstruction example: The example uses a two-level Daubechies-4 2D DWT on 32x32 images, with 106-110 retained support coefficients and 1-3 support changes per time step.

APPENDIX

The appendix develops the CS-residual error and stability machinery used by the paper. Its lemmas connect residual error, support size, detection thresholds, and conditioning assumptions.

  • Proof of Lemma 1: The proof framework uses restricted-isometry and restricted-orthogonality quantities δ and θ, with S∗∗ defined by δ+θ < 1.
  • Proofs of the stability lemmas: Detection is guaranteed when an undetected coefficient exceeds a threshold determined by the addition threshold α and the CS-residual error.
  • Proofs of the stability lemmas: Detected nonzero coefficients avoid false deletion under a coefficient-size condition, while zero extras are deleted when α_del exceeds the relevant LS estimation error.
  • Proofs of the key lemmas: Under ∥w∥∞≤λ/∥A∥1, |T|≤S∗, and |∆|≤S∗∗, Lemma 2 bounds CS-residual error by C′ + C′′θ^2|∆|(x∆)2(1).

C. LS-CS Stability: Proof of Theorem 2

The stability proof uses induction over addition intervals to bound misses and extras, then shows that the estimated support becomes exact before subsequent removals and additions under the theorem’s conditions.

  • Initial post-addition interval: During the first d0 time units after an addition, misses remain at most Sa and extras at most (i + 1)f.
  • Detection interval: At t = tj + d0 + i −1, the first i largest increasing coefficients are detected, misses are at most Sa −i, and extras are at most (d0 + i)f.
  • Deletion interval: At t = tj + d0 + Sa −1, all false detects are deleted, so extras become zero.
  • Stable-support interval: From tj + d0 + Sa −1 through tj+1−r−1, misses and extras remain zero and the estimated support equals Nt.
  • Removal interval: During the coefficient-decrease interval [tj+1 −r, tj+1 −1], the estimated support remains exact despite removals.
  • Error bound: The LS-CS error bound is obtained by combining interval-wise bounds on missed-support energy with the CS-residual corollary.
Loading 0911.5524v2…