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

- September 2010: New Student Opening for Spring or Fall 2011
- September
2010: Allerton 2010 papers posted

- May 2010: Exciting new experimental results on fMRI
reconstruction and brain activation detection

- February 2010: Modified-CS paper accepted to TSP
- January 2010: LS-CS-residual (LS-CS) paper accepted to TSP
- October 2009: Invited talk on
Recursive
and Causal Sparse Reconstruction
at special session on CS at INFORMS Annual Meeting

- Overview talk on Recursive
and Causal Sparse Reconstruction (talk at UCSD, Oct 15 2009,
Princeton, May
5, 2010 )

- April 2009: Research got supported by NSF

- Summary - Recursive
reconstruction of sparse signal seqeunces

- Journal Papers

- Namrata Vaswani, LS-CS-residual (LS-CS): Compressive Sensing on Least Squares Residual, To Appear in IEEE Trans. Signal Processing. Shorter versions appeared in ICIP'08 and ICASSP 2009 (ICIP talk)
- Namrata Vaswani and Wei Lu, Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support, To Appear in IEEE Trans. Signal Processing. Shorter version appeared in ISIT'09 (ISIT talk)
- Preprints
- Namrata
Vaswani, Stability (over
time) of Modified-CS and LS-CS for Recursive Causal Sparse
Reconstruction, arXiv: 1006.4818

- Wei
Lu and Namrata Vaswani, Regularized
Modified-BPDN for compressive sensing with partially known support,
arXiv: 1002.0019

- Namrata Vaswani, KF-CS-residual (KF-CS): Compressive Sensing on Kalman filtered residual, arXiv:0912.1628.
- shorter
version in ICIP'08 and
ICASSP 2009
(ICIP talk)

- Chenlu
Qiu and Namrata Vaswani,
__Compressive Sensing on the Least Squares and Kalman Filtering Residual for Real-time Dynamic MRI and Video Reconstruction__, Submitted to IEEE Trans. Image Processing in December 2009. - shorter version in ICASSP'09 (ICASSP talk)
- KF-CS and LS-CS conference papers
- Namrata Vaswani, Kalman Filtered Compressed Sensing, IEEE Intl. Conf. Image Proc. (ICIP), 2008.
- Namrata Vaswani, Analyzing Least Squares and Kalman Filtered Compressed Sensing, IEEE Intl. Conf. Acous. Speech. Sig. Proc. (ICASSP), 2009.
- Chenlu Qiu, Wei Lu and Namrata Vaswani, Real-time Dynamic MR Image Reconstruction using Kalman Filtered Compressed Sensing, IEEE Intl. Conf. Acous. Speech. Sig. Proc. (ICASSP), 2009.
- Modified-CS conference papers

- (noiseless measuements) Namrata Vaswani and Wei Lu, Modified-CS: Modifying Compressive Sensing for Problems with Partially Known Support, IEEE Intl. Symp. Info. Theory (ISIT), 2009
**(noisy measurements) Wei Lu**and Namrata Vaswani, Modified Basis Pursuit Denoising (Modified-BPDN) For Noisy Compressive Sensing With Partially Known Support, IEEE Intl. Conf. Acous. Speech. Sig.Proc.(ICASSP), 2010.- (dynamic MRI application) Wei Lu and Namrata Vaswani, Modified Compressive Sensing for Real-time Dynamic MR Imaging, IEEE Intl. Conf. Image Proc (ICIP), 2009
- (noisy case: stability over time) Namrata Vaswani, Stability (over time) of Modified-CS for Recursive Causal Sparse Reconstruction, Allerton 2010 (invited)
- Real-time Robust PCA
- Chenlu Qiu and Namrata Vaswani, Real-time Robust Principal Components' Pursuit, Allerton, 2010

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:

- Real-time Dynamic
MRI (Magnetic Resonance Image) Reconstruction

- 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:

- Code using CVX (works for signals/images of size upto about 4096:
- Code for large-sized images
(optimization code rewritten using fast operators for 2D-DFT and
2D-DWT)

- A note about
ModifiedCS_sequential.m

- the following may appear as a small typo: for
seq=1:seqlen should be replaced by for
seq=2:seqlen

- but it does not affect results in any way for
sparse sequences, it actually improves results for compressible
sequences.

- KF-CS and
LS-CS new code:

- Contains LS-CSresidual-LS (LS-CS), KF-CSresidual-LS (KF-CS), KF-CSresidual-KF (KF-CS - 0), versions with and without deletion step
- Code: LSCS_KFCS_code.zip
- 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)