Recursive Reconstruction of Sparse Signal Sequences  (or Sequential Compressed Sensing)
Faculty: Namrata Vaswani
Students: Wei Lu  and  Chenlu Qiu
Supported by: NSF (CCF)

Goal: Reconstruct time sequences of spatially sparse/compressible signals (with unknown and time-varying sparsity patterns) from a limited number of linear “incoherent” measurements, in real-time (i.e. causally and recurisvely). Use the fact that the sparsity pattern evolves slowly over time [see this figure for empirical verification]
Summary of Work
 Papers
 Main Idea and Applications
MATLAB Code
 Simulation Results
 Results on dynamic MRI reconstruction
 Students
 Research Summary
 Compressive Sensing class (EE 520)


News
 Papers

Main Ideas and Applications
1.  LS-CS-residual (LS-CS): Compressive Sensing on Least Squares Residual
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, LSCS- 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 the CSresidual 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 every-so-often, 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 from the support estimate and the number of extras in it 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. Extensive simulation results backing our claims are shown.
Contributions
(i)   The LS-CS-residual idea and extensive simulations
(ii)  Bound for CS-residual error and comparison with simple CS error bound
(iii) Proof of stability (over time) of support errors and hence of reconstruction errors, under mild assumptions

2. Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support
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 whose support contains the smallest number of new additions to T, although it may or may not contain all elements 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. Simulation comparisons for both sparse and compressible signals are shown.
Contributions
(i)  The modified-CS idea, extensive simulations and proof-of-concept applications in MRI/video
(ii)  Proof of exact reconstruction under much weaker assumptions on the measurement matix than those needed for simple CS (means: need much fewer measurements)
(iii) Regularized modified-CS idea (use the prior knowledge of signal values along with support knowledge)

2b. Stability (over time) of Modified-CS and LS-CS for Recursive Causal Sparse Reconstruction, ArXiv: 1006.4818
(i) stability (over time) of modified-CS and of LS-CS for the case when support additions/removals are allowed to occur at every time t.


3. KF-CS-residual (KF-CS): Compressive Sensing on Kalman filtering Residual
We consider the problem of reconstructing time sequences of spatially sparse signals (with unknown and timevarying sparsity patterns) from a limited number of linear “incoherent” measurements, in real-time. The signals are sparse in some transform domain referred to as the sparsity basis and the sparsity pattern is assumed to change slowly with time. The main idea of our proposed solution is to replace compressed sensing (CS) on the observation by CS on the Kalman filtered (KF), observation residual computed using the previous estimate of the support. We also obtain the conditions under which KF-CS-residual (KF-CS) estimate eventually converges to that of the genie-aided KF (the KF that knows the support at each time). A useful corollary is that if the sparsity pattern changes slowly enough, the KF-CS estimate stabilizes to within a small error of the genie-aided KF estimate. An analogous result is also obtained for LS CS-residual.
Contributions
(i) The KF-CS idea and extensive simulations.
(ii) Proof of KF-CSerror stability over time, but under strong assumptions. Ongoing work includes trying to do this under assumptions similar to those for LS-CS

3. Ongoing work:
(a) Bounding regularized-modified-BPDN error and comparison with modified-BPDN, LS-CS and simple CS (submitted)
(b) Stability (over time) of modified-CS-noisy and LS-CS-residual when support additions/removals at every time  (submitted)
(c) Applications in dynamic MRI and video: Chenlu Qiu's page   Wei Lu's page
(d) Stability of KF-CS and regularized-modified-CS over time, under assumptions similar to those for LS-CS:  still working

4. Applications:
MATLAB Code:
Simulation Results:
KF CS-residual (KF-CS): We used signal dimension, m = 256, and observation dimension, n = 72 and simulated i.i.d. random-Gaussian measurements.  We started with sparsity size, S_1 = 8 and for 10 ≤ t ≤ 50, we added 2 new elements to the support every 5 time units. Thus S_t = S_max = 26, for all t ≥ 50 (note 26 > n/3 = 24. KF-CS with the deletion (cofficient removal) step was implemented. Notice that the KF-CS error converges to that of the Genie KF roughly by t = 65. On the other hand, regular CS error is very large (particularly when S_t > n/3). Maximum CS error was 425.   

Compare KF-CS with CS and Genie-KF
                  
Modified-CS: We took a cardiac image sequence, sparsified it in the wavelet domain by retaining the largest wavelet coefficients corresponding to 99% of the image energy. The support of the wavelet coefficients of the resulting image sequence was about 10% of the image size. For noise-free measurements, modified-CS achieved exact reconstruction with only  n=16% Fourier measurements (simulate dynamic MRI application). With so few observations, clearly CS failed. See Fig (a) below. Fig (b) below considers a real cardiac sequence (not sparsified), but uses n=19% random Gaussian measurements (simulate video compression application).
Compare Modified-CS                                                                 


Students: