Sequential Compressed Sensing or Recursive
Reconstruction of Sparse Signal Sequences
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]
1. CS-Residual: Least Squares
CS-residual (LS-CS) and Kalman Filtered CS-residual (KF-CS) 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 least squares
(LS), or Kalman filtered (KF), observation residual computed using the
previous estimate of the support.
We obtain tight upper bounds on LS CS-residual error
and show that they are much smaller than the bound on CS error, if the
sparsity pattern changes slowly enough. We also obtain the conditions
under which the KF CSresidual 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-residual estimate stabilizes to within a small error of the
genie-aided KF estimate. An analogous result is also obtained for LS
CS-residual.
2. Modified-CS 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. This 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 of the support. The idea of our solution
(modified-CS) is to solve a convex relaxation of the following problem:
find the sparsest possible signal that satisfies the data constraint
and whose support contains the “known” part of the support. In other
words, we try to find a signal with the smallest number of new
additions to the known support that satisifies the data constraint.
We derive sufficient conditions for exact
reconstruction using modified-CS. These are much weaker than the
sufficient conditions needed for CS, particularly when the known part
of the support is large compared to the unknown part.
3. Ongoing work: (1) Obvious
and not-so-obvious combinations of the above ideas for noisy and for
compressible signal sequences. (2) Dealing with errors in the ``known"
part of the support. (3) Stability of LS and KF CS-residual under
weaker assumptions. (4) Applications in dynamic MRI and in video
compression.
4. Applications:
Already existing work for dynamic MR image reconstruction
(greatly reduced capture time by using CS already demonstrated by
others),
But in all existing work: reconstruction is done offline (wait
to get all the measurements first) and it takes
many hours. Our goal: reduce scan time (because of CS) and
reconstruction time (because of causal reconstruction)
Our goal: Reduce the number of measurements required (reduce
scan time) and provide real-time (causal and recursive
reconstruction) with same complexity as CS for one frame
Application: Provide ability to use MR in interventional
radiology
applications and in real-time fMRI imaging
Works because support of wavelet
transform of medical image sequences changes slowly over time
[see figure]
Single-pixel video camera:
Convert the single-pixel camera into a single-pixel video camera with
real-time display capability (ability to reconstruct the image in
real-time from projections)
Sensor networks:
Real-time estimation of time-varying temperature, pressure or other
random fields using a sensor network : extend Haupt-Nowak's work to
time sequences
Any CS problem where need to reconstruct a "sequence of signals",
most typically a time sequence, that satisfies "slow sparsity change"
assumption
MATLAB Code:
Modified-CS code:
Please cite paper number 1.
above (Vaswani and Lu, ISIT 2009) if you use this code
README.txt with
detailed comments and instructions
Two older versions of KF-CS code
Kalman filtered CS (KF-CS): KFCS_new.zip
(Main file:
runsims_final, see comments and see README.txt)
Please cite N. Vaswani, ICASSP'09 and ICIP'08 if you use this
code.
See README.txt for code structure. runsims_final.m is the
main
file. kfcs_full contains the kfcs code.
Least Squares CS (LS-CS):
Replace the KF in the above code by LS: to get the LS-CS implementation
(will be posted soon)
Older version of code based on the ICIP'08 paper: KFCS.zip
(To run it: runsims2, followed by plotting the errors)
Please cite the above ICIP paper when using this code
See README.txt or comments in runsims2.m
You may need to install netlab and add it to your MATLAB path:netlab.zip
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.
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).
Students:
Graduate Students
Wei Lu : modified-CS for dynamic MRI and for video compression
Chenlu Qiu: Kalman filtered CS and Least Squared CS for
dynamic MRI
Undergraduate students:
Senior Design
team (Aaron Logan, William Lim, Dylan Reid, Kyungchul Song)
