Sparse Recovery of Streaming Signals Using $\ell_1$-Homotopy
Authors:
- 9 June 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 62 (16) , 4209-4223
Abstract
Most of the existing sparse-recovery methods assume a static system: the signal is a finite-length vector for which a fixed set of measurements and sparse representation are available and an l1 problem is solved for the reconstruction. However, the same representation and reconstruction framework is not readily applicable in a streaming system: the signal changes over time, and it is measured and reconstructed sequentially over small intervals. This is particularly desired when dividing signals into disjoint blocks and processing each block separately is infeasible or inefficient. In this paper, we discuss two streaming systems and a new homotopy algorithm for quickly solving the associated l1 problems: 1) recovery of smooth, time-varying signals for which, instead of using block transforms, we use lapped orthogonal transforms for sparse representation and 2) recovery of sparse, time-varying signals that follows a linear dynamic model. For both systems, we iteratively process measurements over a sliding interval and solve a weighted l1-norm minimization problem for estimating sparse coefficients. Since we estimate overlapping portions of the signal while adding and removing measurements, instead of solving a new l1 program as the system changes, we use available signal estimates as starting point in a homotopy formulation and update the solution in a few simple steps. We demonstrate with numerical experiments that our proposed streaming recovery framework provides better reconstruction compared to the methods that represent and reconstruct signals as independent, disjoint blocks, and that our proposed homotopy algorithm updates the solution faster than the current state-of-the-art solvers.Keywords
All Related Versions
This publication has 41 references indexed in Scilit:
- Fast and Accurate Algorithms for Re-Weighted $\ell _{1}$-Norm MinimizationIEEE Transactions on Signal Processing, 2013
- A Tutorial on Encoding and Wireless Transmission of Compressively Sampled VideosIEEE Communications Surveys & Tutorials, 2013
- WarmL1: A warm-start homotopy-based reconstruction algorithm for sparse signals2012
- Sparse signal recovery and dynamic update of the underdetermined system2010
- Dynamic Updating for $\ell_{1}$ MinimizationIEEE Journal of Selected Topics in Signal Processing, 2010
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Dynamic updating for sparse time varying signals2009
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Least-squares estimation: from Gauss to KalmanIEEE Spectrum, 1970
- A New Approach to Linear Filtering and Prediction ProblemsJournal of Basic Engineering, 1960