PaperlayerView exact revision on arXiv

Source-linked AI summary

Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support

Namrata Vaswani, Wei Lu

arXiv:0903.5066v5cs.ITmath.STstat.ME

TL;DR

The paper addresses sparse reconstruction from limited linear measurements when part of the support is known but may contain errors. It proposes modified-CS, which promotes sparsity outside that support, and develops RegModCS using prior signal estimates. The resulting sufficient conditions for exact recovery are weaker than CS conditions when unknown support changes and support errors are small, while RegModCS improves error when exact recovery is not possible.

  • Problem

    Sparse reconstruction must recover signals from limited linear measurements when part of the support is known but may contain errors, including recursively changing signal sequences.

  • Method

    Modified-CS solves an ℓ1 relaxation that satisfies the data constraint while seeking sparsity outside the known support, and RegModCS additionally uses prior signal-estimate knowledge.

  • Results

    When unknown support changes and known-support errors are small, modified-CS has weaker sufficient exact-recovery conditions than CS; its ℓ0 condition is δs+e+u < 1 versus CS's δ2s < 1.

  • Takeaways & Limitations

    The approach supports recursive reconstruction of sparse or approximately sparse signal sequences, including real-time dynamic MRI, and RegModCS improves error when exact reconstruction is not possible.

Abstract

from arXiv · show

We study the problem of reconstructing a sparse signal from a limited number of its linear projections when a part of its support is known, although the known part may contain some errors. The ``known" part of the support, denoted T, may be available from prior knowledge. Alternatively, in a problem of recursively reconstructing time sequences of sparse spatial signals, one may use the support estimate from the previous time instant as the ``known" part. The idea of our proposed solution (modified-CS) is to solve a convex relaxation of the following problem: find the signal that satisfies the data constraint and is sparsest outside of T. We obtain sufficient conditions for exact reconstruction using modified-CS. These are much weaker than those needed for compressive sensing (CS) when the sizes of the unknown part of the support and of errors in the known part are small compared to the support size. An important extension called Regularized Modified-CS (RegModCS) is developed which also uses prior signal estimate knowledge. Simulation comparisons for both sparse and compressible signals are shown.

I. INTRODUCTION

The paper adapts sparse reconstruction to settings where a partially known, possibly erroneous support is available, including recursive signal sequences. Modified-CS and RegModCS target exact recovery with fewer measurements or improved error than conventional CS under small support changes and support errors.

  • Applications: The motivating recursive setting includes applications such as real-time dynamic MRI, single-pixel camera video imaging, and video compression or decompression.The paper also notes a possible combination with multiscale CS for video compression.
  • Core approach: Modified-CS solves an ℓ1 relaxation that enforces the data constraint while promoting sparsity outside the known support T.The known support may come from prior knowledge or a previous time-step estimate.
  • Exact reconstruction: When the unknown support and known-support errors are small, modified-CS has weaker sufficient exact-recovery conditions than CS.For recursive sequences, slow support change makes these quantities small relative to the support size.
  • Extensions: RegModCS extends modified-CS by incorporating prior signal-estimate knowledge and improves error when exact reconstruction is not possible.The paper also applies the modified-CS idea to recursive reconstruction of sparse or compressible signal sequences.

II. MODIFIED COMPRESSIVE SENSING (MODIFIED-CS)

Modified-CS reconstructs a signal by enforcing the data constraint while minimizing additions outside a possibly imperfect known support. Its exact-recovery conditions can be substantially weaker than CS conditions when support errors and unknown additions are small.

  • Modified-CS formulation: Modified-CS seeks the feasible signal with the fewest new support elements outside the known support T.The ideal formulation minimizes the ℓ0 norm outside T, then replaces it with an ℓ1 relaxation.
  • Modified-CS formulation: If the known support contains no errors, the modified-CS solution is also the sparsest feasible signal whose support contains T.This special case occurs when the missed-support set ∆e is empty.
  • Exact reconstruction: For the ℓ0 formulation, δk+2u < 1 guarantees uniqueness, equivalently δs+e+u < 1 after substituting k = s+e−u.Here k=|T|, u=|∆|, e=|∆e|, and s=|N|.
  • Exact reconstruction: The ℓ1 method returns the unique signal under sufficient conditions involving δk+u, δ2u, δk, θk,2u, and ak(2u,u)+ak(u,u).The theorem requires δk+u < 1, δ2u + δk + θ2 k,2u < 1, and ak(2u,u) + ak(u,u) < 1.
  • Comparison with CS: When u and e are small relative to s, modified-CS may succeed with measurements below the CS requirement, including the range s+u+e < m < 2s.The comparison states that CS’s δ2s condition fails when m<2s, while modified-CS can hold when support uncertainty is sufficiently small.

C. Proof of Theorem 1: Main Lemmas and Proof Outline

The proof establishes exact recovery through a dual-certificate construction. It first characterizes the certificate conditions for modified-CS, then applies an iterative lemma to satisfy them.

  • Lemma 1: The modified-CS objective has gradient zero on T, signs of x on ∆, and subgradient values bounded by one outside T∪∆.The certificate must satisfy w′Aj=0 on T, w′Aj=sgn(xj) on ∆, and |w′Aj|<1 elsewhere.
  • Lemma 1: Lemma 1 guarantees unique recovery when δk+u < 1 and a vector w satisfies the three certificate constraints.These constraints impose the required inner products on T and ∆ and strict boundedness off their union.
  • Lemma 2: Lemma 2 constructs an intermediate certificate for any vector supported on Td disjoint from T and controls its correlations outside T∪Td∪E.The exceptional set E is disjoint from T∪Td and has size below the prescribed bound.
  • Proof outline: The theorem’s proof applies Lemma 2 iteratively, beginning with ∆ and updating the exceptional set, then combines the certificates into w.Condition 1 makes the iterations applicable; condition 2 makes the resulting certificate satisfy Lemma 1.

D. Proofs of Lemmas 1 and 2

The lemma proofs show uniqueness by comparing an arbitrary minimizer with the true signal and using strict dual-certificate inequalities. Full-rank restricted sensing then forces equality.

  • Proof strategy: The proof starts from an arbitrary minimizer β and aims to show β=x whenever the lemma conditions hold.Feasibility of x ensures that a minimizer exists.
  • Proof of Lemma 1: Strict inequalities outside T∪∆ force every off-support coefficient of β to vanish.If |w′Aj|<1 for all j outside T∪∆, equality in the objective comparison is possible only when those coefficients are zero.
  • Proof of Lemma 1: Once β and x share support within T∪∆ and satisfy the same measurements, full rank of A_T∪∆ implies β_T∪∆=x_T∪∆.The condition δk+u < 1 supplies the needed full-rank property.
  • Proof comparison: The proof structure differs significantly from the corresponding lemma in the cited CS work despite a similar final result.This is stated as a comparison of proof methods, not of recovery guarantees.

2) Proof of Lemma 2:

Lemma 2 is proved by constructing a projected certificate and bounding its correlations using restricted-isometry and eigenvalue arguments.

  • Certificate construction: The certificate construction solves a projected linear system for γ using η=(A_Td′MA_Td)^−1c.The projection identity MM′=M^2=M yields γ=M′A_Tdη.
  • Certificate construction: The construction applies to any Td disjoint from T with |Td|≤S and any vector c supported on Td.The resulting vector satisfies the prescribed measurements on Td.
  • RIP bounds: The proof bounds the projected terms through nonnegative-definite matrices and eigenvalue inequalities, with positivity requiring the stated denominator condition.The argument uses λmin(B1−B2)≥λmin(B1)−λmax(B2) and the projection norm ∥M∥=1.
  • Exceptional set: An exceptional set E collects indices whose certificate correlations exceed the bound ak(S,Š), and its size is strictly below Š.If E were too large, selecting Š indices from E would contradict the correlation bound.

IV. COMPARISON OF CS AND MODIFIED-CS

The paper compares sufficient exact-recovery conditions for modified-CS and CS using RIP constants and random-Gaussian measurement bounds. Across the comparisons, modified-CS permits larger sparsity levels when the known support is accurate and its errors are small.

  • Comparison framework: The study compares sufficient conditions for modified-CS and CS, treating them as tools for selecting the required number of measurements.The conditions are expressed using δS quantities.
  • RIP comparison: When u = e = 0.02s, modified-CS requires δ2u < 1/132.5, whereas one CS condition requires δ2u < 1/241.5.The latter condition is explicitly identified as stronger.
  • Random-Gaussian comparison: For fixed m/n, the maximum allowed s/n for ρmodCS < 1 exceeds that for either ρCS < 1 or ρCS,2 < 1.Figure 2 uses u = e = s/50 for modified-CS.
  • Interpretation: The sufficient-condition bounds are much smaller than simulation observations, making the predicted CS–modified-CS difference less significant than the empirical difference may be.The paper attributes this discrepancy to looseness of the bounds.

B. Comparison using Monte Carlo

Monte Carlo experiments compare exact-reconstruction probabilities for modified-CS and CS under random-Gaussian measurements. When the unknown-support and known-support-error sizes are small, modified-CS succeeds with substantially fewer measurements.

  • Experimental setup: The Monte Carlo procedure estimates exact-reconstruction probability over 500 trials for fixed random-Gaussian sensing matrices and varied m, u, and e.Exact reconstruction is counted when the relative ℓ2 error is below 10^-5.
  • Experimental setup: With n = 256 and s = 0.1n, the experiments vary m from 0.16n to 0.4n while varying u from 0.04s to s and e from 0 to 0.4s.The case u = s and e = 0 corresponds to CS.
  • Results: At m = 0.19n = 1.9s, modified-CS reconstructs exactly more than 99.8% of the time when u ≤ 0.08s and e ≤ 0.08s, while CS has zero probability.This is the strongest reported low-measurement comparison.
  • Results: At m = 0.3n = 3s, CS has a 14% exact-reconstruction chance, whereas modified-CS works almost all the time for u ≤ 0.2s and e ≤ 0.4s.CS needs at least m = 0.4n = 4s to work reliably in these experiments.
  • Scope: The simulations show empirical success at smaller m with modified-CS when u, e ≪ s, but do not compute the measurement threshold required by Theorem 1.Monte Carlo averages over the joint distribution of x and y and does not establish universal guarantees.

C. Robustness to noise

The paper examines noisy measurements and extensions for settings where exact reconstruction is unavailable, including compressible signals and recursive signal sequences. RegModCS incorporates prior signal estimates to reduce reconstruction error.

  • Noise robustness: For noisy measurements, the original modified-CS data constraint may be infeasible because the true signal no longer satisfies it.The paper therefore points to relaxed data constraints for noisy modified-CS.
  • Noise robustness: With small enough noise, modified-CS remained feasible in all reported simulations and had small error, while CS had large error when m was too small for CS.The experiment used n = 256, s = 0.1n, u = e = 0.08s, and m = 0.19n.
  • Extensions: RegModCS is intended for cases where exact reconstruction fails because measurements are insufficient or the signal is compressible.It uses prior signal-estimate knowledge in addition to support knowledge.
  • Extensions: For compressible signals, the paper uses a b%-energy support rather than the exact nonzero support.The b%-support contains indices whose coefficients exceed a threshold chosen to capture at least b% of signal energy.
  • Extensions: Dynamic modified-CS applies the method recursively by using the previous time instant’s support estimate as T.Initialization can use CS or prior support knowledge.

C. Setting γ using an MAP interpretation of RegModCS

The paper interprets RegModCS through a probabilistic signal model and uses that interpretation to select its regularization parameter. Under stated modeling and perfect-previous-estimate assumptions, the resulting solution is a causal MAP estimate.

  • MAP interpretation: The MAP interpretation assumes independent coefficients, Laplace-distributed values outside T, and Gaussian values on T with means µi and variance σ2.These assumptions define the prior model associated with the regularized objective.
  • Parameter selection: The model parameters can be estimated in closed form from i.i.d. training data using maximum likelihood.The paper states that the relevant MLEs are given in Appendix C.
  • Recursive use: For recursive reconstruction, RegModCS sets T to the previous support estimate and µT to the previous signal estimate restricted to T.The previous estimates are fed back into the next time step.
  • Guarantee: Under perfect previous-signal estimation and the stated parameter choice, the RegModCS solution is the causal MAP solution under the model.The result depends on the assumptions specified in the paper’s probabilistic formulation.

VI. RECONSTRUCTING SPARSIFIED/TRUE IMAGES FROM SIMULATED MEASUREMENTS

The experiments evaluate modified-CS and RegModCS on sparsified and compressible images and sequences using random Gaussian and partial Fourier measurements. Across these settings, both methods generally outperform CS-based alternatives, with RegModCS strongest when measurements are scarce.

  • Experimental Setup: The study used a 2-level Daubechies-4 2D-DWT, N-RMSE, and comparisons against CS, CS-diff, and LS-CS across Gaussian and partial Fourier measurements.The measurement model was A = HΦ, with H representing acquisition and Φ the sparsity basis.
  • Sparsified and True (Compressible) Single Image: Modified-CS achieved exact reconstruction from 29% random Gaussian and 19% partial Fourier measurements for a sparsified cardiac image.The known support contained approximation-coefficient indices, while the unknown support remained a large fraction of the signal support.
  • Sparsified and True (Compressible) Single Image: For actual cardiac and larynx images, modified-CS outperformed CS, although the improvement was limited because the unknown support was a large fraction of the 99%-energy support.These images were only approximately sparse, and performance was measured using N-RMSE.
  • Sparsified Image Sequences: Modified-CS achieved error of 10^-8 or less with 16% measurements for sparsified cardiac image sequences.Here the unknown support and support-estimation errors were approximately 1% and 0.5% of n, respectively.
  • True (Compressible) Image Sequences: In the full larynx sequence, CS had 8–11% N-RMSE while modified-CS remained stable at 2% or less.The comparison used partial Fourier measurements with m = 0.19n; CS-diff error increased over time.
  • True (Compressible) Image Sequences: Modified-CS and RegModCS significantly outperformed CS and CS-diff in compressible sequences, and RegModCS generally also outperformed LS-CS.RegModCS’s advantage was largest when the measurement count was smallest.

APPENDIX

The appendix establishes uniqueness of the modified-CS solution through a contradiction argument and iterative construction of a dual certificate. The proof uses restricted-isometry and related conditions to ensure the certificate exists and the signal is the unique feasible solution.

  • Proof of Exact Reconstruction: If two feasible solutions have equal ℓ0 norm outside T, their difference is supported on T ∪ ∆1 ∪ ∆2.The support size outside T is u for each candidate, so the union contributes at most 2u additional indices.
  • Proof of Exact Reconstruction: Under δ_k+2u < 1, the measurement matrix is injective on the union support, ruling out two distinct feasible solutions.The contradiction follows because A(β1−β2) = 0 while the restricted matrix has full column rank.
  • Dual-Certificate Construction: The proof constructs a dual certificate iteratively, beginning with the unknown support ∆ and adding exceptional sets of size below u.At later iterations, the construction controls ∆ together with the previous exceptional set, whose total size remains below 2u.
  • Dual-Certificate Construction: The iterative residual terms converge because the coefficient ak(2u, u) is less than one.This makes the defining series absolutely convergent and ensures the constructed certificate is well-defined.
  • Proof of Exact Reconstruction: The final certificate satisfies Lemma 1 when the theorem’s conditions imply δ_k+u < 1, completing the exact-reconstruction proof.The certificate construction and theorem conditions together establish the lemma’s required inequalities.

C. Causal MAP Interpretation of Dynamic RegModCS

Dynamic RegModCS admits a causal MAP interpretation under hidden-Markov and signal-distribution assumptions. The interpretation relies on prior support and signal estimates, with exact sparsity of the previous posterior estimate serving only as an approximation.

  • Causal MAP Assumptions: The causal MAP interpretation assumes an observation model p(y_t|x_t) = δ(y_t − A x_t) within a hidden Markov model.The state and observation processes are assumed to satisfy the hidden Markov property.
  • Causal MAP Assumptions: Given x_t−1, the current support and nonsupport components are conditionally independent, with Gaussian support evolution and zero-mean Laplace nonsupport coefficients.These distributional assumptions define the transition model used for the causal posterior.
  • Posterior Interpretation: The causal posterior uses T := ˆN_t−1, linking the current optimization to the previous support estimate.The method therefore incorporates temporal support information from the preceding time instant.
  • Caveat: The assumption that x_t−1 is perfectly estimated and exactly sparse is acknowledged as an approximation.This qualification limits the literal interpretation of the posterior model.
  • Posterior Interpretation: If the stated assumptions hold, the solution of (32) maximizes p(x_t|y_1, . . . , y_t) and is a causal MAP solution.The claim depends on the observation, transition, and estimation assumptions introduced in the appendix.
Loading 0903.5066v5…