Dynamic Filtering of Time-Varying Sparse Signals via l1 Minimization
This work addresses the problem of processing streaming sparse signals for applications like video analysis, offering incremental improvements with robust performance guarantees.
The paper tackles dynamic filtering of time-varying sparse signals in high-dimensional streaming data by analyzing two algorithms based on l1 optimization, with the novel RWL1-DF algorithm showing better performance, especially under inaccurate system dynamics, and providing the first strong performance analysis in this area.
Despite the importance of sparsity signal models and the increasing prevalence of high-dimensional streaming data, there are relatively few algorithms for dynamic filtering of time-varying sparse signals. Of the existing algorithms, fewer still provide strong performance guarantees. This paper examines two algorithms for dynamic filtering of sparse signals that are based on efficient l1 optimization methods. We first present an analysis for one simple algorithm (BPDN-DF) that works well when the system dynamics are known exactly. We then introduce a novel second algorithm (RWL1-DF) that is more computationally complex than BPDN-DF but performs better in practice, especially in the case where the system dynamics model is inaccurate. Robustness to model inaccuracy is achieved by using a hierarchical probabilistic data model and propagating higher-order statistics from the previous estimate (akin to Kalman filtering) in the sparse inference process. We demonstrate the properties of these algorithms on both simulated data as well as natural video sequences. Taken together, the algorithms presented in this paper represent the first strong performance analysis of dynamic filtering algorithms for time-varying sparse signals as well as state-of-the-art performance in this emerging application.