Source-linked AI summary
Kalman Filtered Compressed Sensing
Namrata Vaswani
TL;DR
The paper addresses real-time reconstruction of sparse signal sequences from limited incoherent measurements when support changes slowly and coefficient dynamics have a simple prior. It combines CS-based initial support estimation with reduced-order Kalman filtering and CS detection of support changes from large innovations or filtering errors. The discussion reports that missed coefficients can later be recovered with high probability when their magnitude increases, while rigorous stability and comparison analyses remain future work.
Problem
The problem is whether dynamic sparse sequences can be reconstructed better than applying CS independently when support changes slowly and nonzero coefficients follow a temporal prior.
Method
The method estimates the initial support with CS, runs a reduced-order Kalman filter, and applies CS to large innovations or filtering errors to detect support additions.
Results
Missed nonzero coefficients can later be estimated with high probability when their magnitude increases and produces high innovation and filtering-error signals.
Takeaways & Limitations
The approach uses the greater sparsity of support changes to perform causal tracking with fewer reconstruction burdens than repeatedly estimating the full signal support.
Takeaways & Limitations
Rigorous KF-CS error-stability analysis and comparison with regular CS are left for future work.
Abstract
from arXiv · showhide
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").
1. INTRODUCTION
The paper targets real-time reconstruction of temporally evolving sparse signals from limited incoherent measurements, where support changes slowly and coefficient dynamics follow a prior model. It proposes combining initial CS support estimation with reduced-order Kalman filtering and CS-based support updates.
- Problem: The task is real-time reconstruction of spatially sparse signal sequences from limited incoherent measurements.The signals are sparse in a transform-domain sparsity basis.
- Problem: Dynamic CS methods that process the full sequence are batch and computationally expensive, while separate CS at each time is online but measurement-intensive.The paper frames these as competing alternatives for dynamic reconstruction.
- Assumptions: The proposed setting assumes that the transform support changes slowly and that current nonzero coefficients follow a simple temporal prior.Only a few support elements change at each time.
- Approach: Initial support is estimated with CS, after which a reduced-order Kalman filter tracks the signal using the current support.The filter operates on the currently estimated nonzero coordinates.
- Approach: When innovations or filtering errors become large, CS estimates additions to the support and the Kalman update uses the expanded support.Coefficients that become nearly zero or constant can later be removed.
- Rationale: A full Kalman filter is unsuitable because fewer observations than signal dimensions leave many transform coefficients unobservable.The proposed reduced-order filter exploits sparsity instead.
2. THE MODEL AND PROBLEM FORMULATION
The model represents each spatial signal in an orthonormal sparsity basis and observes it through fewer incoherent linear measurements with temporally independent noise. The formulation seeks causal support estimates and MMSE state estimates under slowly changing sparsity and a Gaussian temporal prior.
- Signal and observations: The spatial signal z_t has m dimensions, while its observation vector y_t has n dimensions with n < m.The transform coefficients x_t = Φ′z_t are sparse.
- Signal and observations: The observation model is y_t = HΦx_t + w_t, where incoherence requires small correlations among columns of A = HΦ.This supports approximately orthonormal submatrices at the relevant sparsity level.
- Objective: The measurement noise w_t is temporally independent, and the goal is a best causal estimate of x_t or z_t from observations through time t.The formulation treats x_t as the state.
- Support notation: The support T_t contains the nonzero coordinates of x_t, with S_t = size(T_t).Subvector and submatrix notation selects entries or columns indexed by a support set.
- Assumptions: The support-change assumption requires S_diff,max < min_t S_t, so estimating additions can be easier than re-estimating the entire support.The paper states that this yields smaller CS error with high probability under Gaussian noise.
- Assumptions: The sensing matrix A must satisfy the UUP at S_max = max_t S_t to preserve observability of active coefficients.If rank(A_Tt) < S_t, unstable coefficient dynamics can cause the Kalman-filter error to grow without bound.
- Temporal model: The system model uses a spatially i.i.d. Gaussian random walk for currently nonzero coefficients, with newly active coefficients initialized by a zero-mean Gaussian prior.These assumptions provide the temporal dynamics used by the reduced-order MMSE filter.
- Estimation objectives: The formulation seeks support estimates minimizing false additions and omissions, together with MMSE state estimates assuming prior support estimates are perfect.Both objectives use observations y_1 through y_t.
3. KALMAN FILTERED COMPRESSED SENSING (KF-CS)
KF-CS combines a reduced-order Kalman filter with compressed sensing to track slowly changing support sets in real time. It detects model mismatch through innovations or filtering error, then estimates support additions and removes near-zero coefficients.
- Detecting If Addition to Support Set Occurred: A generalized likelihood ratio test detects support additions by checking whether the weighted innovation or filtering-error norm exceeds a threshold.The filtering-error norm can make detection more sensitive than the innovation norm.
- Iterating CS and KF-update: The algorithm can iterate compressed sensing and Kalman updates until the filtering-error norm falls below threshold, the estimated additions are empty, or a fixed iteration limit is reached.This addresses cases where one compressed-sensing pass misses some newly active coefficients.
- Estimating the Additions (using CS): When detection is high, KF-CS applies a colored-noise Dantzig selector to the filtering error, thresholds the estimate, and unions detected additions with the current support.The filtering error is used because its noise is smaller, while suppression of new components is small under the UUP assumption.
- Deleting Near-Zero Coefficients: KF-CS deletes coefficients that remain near zero and zeros the corresponding prediction-covariance row and column after removal.The same deletion mechanism addresses coefficients that became zero and coefficients added erroneously by compressed sensing.
- Running the KF: KF-CS initializes the support with compressed sensing, then runs a reduced-order Kalman filter using the current support set.When support changes, the old model creates innovation error that signals model mismatch.
- Discussion: The method assumes slowly changing support patterns and an appropriate temporal prior; rigorous KF-CS error-stability and comparison analyses remain future work.Missed or falsely added coefficients, and incorrect deletions, are identified as sources of error.
4. SIMULATION RESULTS
Simulations evaluated KF-CS on sparse 256-dimensional signals using 72 observations and three maximum sparsity levels. KF-CS had much lower MSE than regular CS, while performance degraded for unknown initialization beyond the matrix’s UUP level.
- Simulation setup: A support increase occurred at t=5 by adding two elements, after which the support remained at size Smax; only additions were simulated.The initial support contained Smax−2 uniformly sampled indices.
- Evaluation: KF-CS was evaluated with known T1 but unknown T5 and with both supports unknown, using MSE averaged over 100 Monte Carlo simulations.The benchmark was a genie-aided Smax-order Kalman filter with known T1 and T5.
- Results: KF-CS had much higher MSE than regular CS was observed for the regular-CS baseline, while unknown-T1 performance degraded more as Smax exceeded the UUP level.The known- and unknown-T1 variants performed almost equally for Smax=8.
- Results: The full 256-dimensional Kalman filter was unobservable with 72 observations, and its error diverged because all nonzero modes were unstable.This filter did not exploit signal sparsity.
5. CONCLUSIONS AND FUTURE DIRECTIONS
The paper introduces a causal extension of Compressed Sensing for time sequences of spatially sparse signals and identifies several directions for future study.
- 5. CONCLUSIONS AND FUTURE DIRECTIONS: KF-CS estimates the initial signal support with CS, then runs a reduced-order Kalman filter until innovation or filtering error increases.When the error increases, CS estimates support changes from the filtering error, which is sparser than the full signal.
- 5. CONCLUSIONS AND FUTURE DIRECTIONS: The authors identify stability analysis of KF-CS and comparison with regular CS as open research questions.
- 5. CONCLUSIONS AND FUTURE DIRECTIONS: Future directions include deleting constant coefficients, extending KF-CS to compressible signal sequences, and applying it to large-dimensional particle filtering.