Analyzing Least Squares and Kalman Filtered Compressed Sensing

Namrata Vaswani

TL;DR

This paper introduces and analyzes two novel algorithms, Kalman Filtered Compressed Sensing (KF-CS) and Least Squares Compressed Sensing (LS-CS), designed for efficiently reconstructing sparse signals that change over time. The key innovation lies in adapting compressed sensing techniques to work with dynamic signals by focusing computational effort on tracking changes in sparsity, leading to significant improvements over traditional methods.

What Problem Does This Paper Address?

Reconstructing signals from limited measurements is a core challenge in many fields, from medical imaging to sensor networks. Compressed Sensing (CS) offers a powerful framework for this, but it typically assumes the signal is static. However, many real-world signals, like video frames or dynamic medical scans, change over time. Traditional CS applied independently at each time step is computationally expensive and can be inaccurate for dynamic signals. Furthermore, when the signal's sparsity pattern (which elements are non-zero) also changes, it poses an even greater challenge. This paper addresses the need for efficient, causal methods to reconstruct these dynamic sparse signals, particularly when the sparsity pattern itself is unknown and evolves slowly.

Methods

The paper builds upon a previously proposed Kalman Filtered Compressed Sensing (KF-CS) approach and introduces a non-Bayesian variant, Least Squares Compressed Sensing (LS-CS).

  • KF-CS: This method combines a Kalman Filter (KF) with Compressed Sensing. Instead of running a full KF on the entire signal, it runs a reduced-order KF focused only on the currently estimated non-zero coefficients. The Kalman filtering error is then used with CS to detect and estimate newly appearing non-zero coefficients. This allows the algorithm to adapt to changes in the signal's sparsity.
  • LS-CS: This is a simplification of KF-CS where the Kalman Filter is replaced by a Least Squares (LS) estimation. This is beneficial when prior models for the signal's dynamics are unavailable or difficult to define.
  • Error Analysis: A significant contribution is the theoretical analysis of the error introduced when applying CS to the least squares error (LS error) of the Kalman filter. The authors derive bounds on this error and compare it to the error of applying CS directly to the raw observations (simple CS).
  • Convergence Analysis: The paper also investigates the conditions under which KF-CS and LS-CS estimates converge to those of a "genie-aided" version. A genie-aided estimator is one that has perfect knowledge of the true sparsity pattern at each time step, serving as an ideal benchmark.

Datasets

Not discussed in the paper. The authors use simulated data for their experiments.

Key Insights and Ideas

  • Focusing on Change: The core idea of tracking only the changes in the sparsity pattern, rather than re-estimating the entire signal from scratch, is crucial for efficiency and accuracy in dynamic scenarios.
  • CS on Errors is Better: Applying CS to the error of a preliminary estimation (like the LS error from a Kalman filter) can yield better results than applying CS directly to the raw measurements, especially when the signal's sparsity changes slowly. This is because the error signal is often "sparser" or more "compressible" in a useful way.
  • Convergence Guarantees: The paper provides theoretical conditions under which these dynamic CS methods can reliably converge to the performance of an ideal estimator that knows the true signal structure. This is important for building confidence in the algorithms.
  • Trade-offs in Thresholding: The choice of threshold for detecting new non-zero coefficients is critical. A high threshold reduces false positives but might miss genuine changes initially. A low threshold might lead to more false additions, complicating the estimation. The paper discusses strategies for managing this trade-off, including a "deletion" step to remove coefficients that are likely zero.

Key Results

  • Error Bounds: The paper derives theoretical bounds on the error of using CS on the LS error, showing it can be significantly smaller than the error of simple CS when sparsity changes slowly.
  • Convergence Proofs: Under specific assumptions (e.g., additions occurring before a finite time, bounded noise, and sufficient incoherence of the measurement matrix), the paper proves that KF-CS and LS-CS estimates converge in probability to their genie-aided counterparts.
  • Simulation Performance: Experimental results (Figure 1) demonstrate that KF-CS significantly outperforms simple CS, especially after new sparsity patterns emerge. While KF-CS shows a temporary increase in error immediately after a change, it quickly recovers and achieves much lower Mean Squared Error (MSE) than simple CS, which struggles with dynamic sparsity.

Limitations and Future Work

  • Assumptions for Convergence: The theoretical convergence guarantees rely on several assumptions, including:
  • The number of false additions being bounded.
  • The measurement matrix being sufficiently "incoherent" with the sparsity basis.
  • All sparsity changes (additions) occurring before a finite time, or changes happening slowly enough for the filter to stabilize.
  • Future Work: The authors are actively working on relaxing these assumptions to broaden the applicability of their methods. They are also exploring the application of KF-CS for real-time dynamic MRI reconstruction, a promising practical use case.

Summary updated

Abstract

In recent work, we studied the problem of causally reconstructing time sequences of spatially sparse signals, with unknown and slow time-varying sparsity patterns, from a limited number of linear "incoherent" measurements. We proposed a solution called Kalman Filtered Compressed Sensing (KF-CS). The key idea is to run a reduced order KF only for the current signal's estimated nonzero coefficients' set, while performing CS on the Kalman filtering error to estimate new additions, if any, to the set. KF may be replaced by Least Squares (LS) estimation and we call the resulting algorithm LS-CS. In this work, (a) we bound the error in performing CS on the LS error and (b) we obtain the conditions under which the KF-CS (or LS-CS) estimate converges to that of a genie-aided KF (or LS), i.e. the KF (or LS) which knows the true nonzero sets.
BibTeX
@inproceedings{vaswani2009analyzing,
  author = {Namrata Vaswani},
  title = {{Analyzing Least Squares and Kalman Filtered Compressed Sensing}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2009},
  doi = {10.1109/icassp.2009.4960258},
}
Figure