Kalman filtered Compressed Sensing

Namrata Vaswani

TL;DR

This paper introduces a novel "Kalman Filtered Compressed Sensing" (KF-CS) algorithm that reconstructs dynamic, spatially sparse signals from limited measurements more efficiently than existing methods. By combining Kalman filtering with Compressed Sensing, KF-CS adapts to slowly changing sparsity patterns, significantly reducing computational complexity and improving accuracy for real-time applications like dynamic MRI.

What Problem Does This Paper Address?

Reconstructing dynamic signals that are sparse in some transform domain (e.g., wavelets) from a limited number of "incoherent" measurements is a challenging problem. This is crucial for applications like real-time medical imaging (e.g., dynamic MRI of a beating heart) where capturing and reconstructing data quickly is essential. Traditional Compressed Sensing (CS) methods, while effective for static signals, treat entire time sequences as a single batch, leading to high computational costs and delays. Applying CS independently at each time step is faster but requires significantly more measurements to achieve low error. This paper addresses the gap of efficiently reconstructing dynamic sparse signals in real-time, specifically when the signal's sparsity pattern changes slowly over time and a simple temporal model of its non-zero elements is available.

Methods

The core innovation is the Kalman Filtered Compressed Sensing (KF-CS) algorithm. It leverages the fact that for dynamic sparse signals, the sparsity pattern (the locations of non-zero coefficients) changes gradually.

Here's how it works:

  • Initial Support Estimation: CS is used to estimate the "support set" (locations of non-zero coefficients) of the initial signal.
  • Kalman Filtering with Known Support: Once a support set is estimated, a reduced-order Kalman filter is employed. This filter operates only on the estimated non-zero coefficients, drastically reducing computational complexity compared to a full Kalman filter on the entire signal dimension.
  • Detecting Support Changes: The Kalman filter's innovation (prediction error) is monitored. If this error increases significantly, it signals a change in the sparsity pattern.
  • Estimating New Support Elements: Instead of re-running CS on the entire observation, KF-CS runs CS on the Kalman innovation error. This is more efficient because the "change" in the signal is typically much sparser than the entire signal itself. CS is used to estimate these new additions to the support set.
  • Adaptive Updates: The Kalman filter is then updated with the new, expanded support set. The algorithm also includes a mechanism for deleting coefficients that become near-zero over time.

This approach is a departure from standard CS, which typically performs CS on the raw measurements to estimate the entire signal at each time step. KF-CS intelligently uses the temporal dynamics and the Kalman filter's predictive power to refine the CS process.

Datasets

Not discussed in the paper. The paper focuses on a simulated scenario with a synthetic matrix A and simulated sparse signals.

Key Insights and Ideas

  • Leveraging Temporal Sparsity: The key insight is that for dynamic signals with slowly changing sparsity, we can do better than treating each time step independently. The temporal correlation is a valuable piece of information.
  • CS on the Error, Not the Signal: Running CS on the Kalman filter's innovation error is significantly more efficient than running it on the raw measurements. This is because the innovation error is expected to be sparse when only a few sparsity elements change.
  • Adaptive Sparsity Estimation: The algorithm adaptively updates its estimate of the sparsity pattern by using the Kalman filter's prediction and then employing CS to correct for deviations, rather than re-estimating everything from scratch.
  • Reduced-Order Kalman Filtering: By knowing or estimating the sparsity pattern, the Kalman filter can operate on a much smaller subspace, leading to substantial computational savings.

Key Results

The paper presents simulation results demonstrating the effectiveness of KF-CS:

  • Improved MSE: KF-CS consistently achieves lower Mean Squared Error (MSE) compared to regular CS applied at each time step, especially as the signal's sparsity level increases.
  • Efficiency: While not explicitly quantified in terms of speedup, the method's reliance on reduced-order Kalman filtering and CS on sparse errors implies significant computational advantages for real-time applications.
  • Performance with Known vs. Unknown Initial Support: The KF-CS algorithm performs well whether the initial sparsity pattern (T₁) is known or unknown, though performance slightly degrades when T₁ is unknown for higher sparsity levels.
  • Comparison to Full KF: A full Kalman filter (operating on the entire signal dimension without sparsity assumptions) is shown to have its error "blow up" due to unobservability and unstable modes, highlighting the necessity of exploiting sparsity.

Limitations and Future Work

The authors acknowledge several areas for future research:

  • Theoretical Analysis: A rigorous mathematical analysis of the stability of the KF-CS error and a formal comparison of KF-CS error with regular CS are needed.
  • Deletion of Constant Coefficients: Developing robust methods for identifying and removing coefficients that become consistently near-zero over time is an open question.
  • Compressible Signals: Extending KF-CS to handle "compressible" signals (where coefficients decay rapidly but are not strictly zero) is a promising direction.
  • Large-Scale Particle Filtering: Exploring extensions of KF-CS to large-dimensional particle filtering is also suggested.
  • Colored Noise: The paper notes that the CS step for estimating additions is applied to a "colored" noise scenario (due to the Kalman filter's dynamics), and while they use a modified approach, a deeper analysis of CS in such colored noise is beneficial.

Summary updated

Abstract

We consider the problem of reconstructing time sequences of spatially sparse signals (with unknown and time-varying 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. For a single spatial signal, the solution is provided by Compressed Sensing (CS). The question that we address is, for a sequence of sparse signals, can we do better than CS, if (a) the sparsity pattern of the signal's transform coefficients' vector changes slowly over time, and (b) a simple prior model on the temporal dynamics of its current non-zero elements is available. The overall idea of our solution is to use CS to estimate the support set of the initial signal's transform vector. At future times, run a reduced order Kalman filter with the currently estimated support and estimate new additions to the support set by applying CS to the Kalman innovations or filtering error (whenever it is "large").
BibTeX
@inproceedings{vaswani2008kalman,
  author = {Namrata Vaswani},
  title = {{Kalman filtered Compressed Sensing}},
  booktitle = {ICIP},
  year = {2008},
  doi = {10.1109/icip.2008.4711899},
}
Figure