Sparse Recovery of Streaming Signals Using l1-Homotopy

被引:106
作者
Asif, M. Salman [1 ]
Romberg, Justin [2 ]
机构
[1] Rice Univ, Dept Elect & Comp Engn, Houston, TX 77005 USA
[2] Georgia Inst Technol, Sch Elect & Comp Engn, Atlanta, GA 30332 USA
关键词
Basis pursuit denoising; compressed sensing; Kalman filter; lapped transform; Lasso; weighted l(1) norm; TIME-VARYING SIGNALS; ALGORITHMS; SHRINKAGE; SELECTION;
D O I
10.1109/TSP.2014.2328981
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
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 l(1) 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 l(1) 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 l(1)-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 l(1) 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.
引用
收藏
页码:4209 / 4223
页数:15
相关论文
共 53 条
[1]  
Angelosante Daniele, 2009, 2009 43rd Asilomar Conference on Signals, Systems and Computers, P181, DOI 10.1109/ACSSC.2009.5470133
[2]  
[Anonymous], 1996, PRINCETON MATH SER
[3]  
Asif M. S., 2013, THESIS GEORGIA I TEC
[4]   Fast and Accurate Algorithms for Re-Weighted l1-Norm Minimization [J].
Asif, M. Salman ;
Romberg, Justin .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2013, 61 (23) :5905-5916
[5]   Motion-adaptive spatio-temporal regularization for accelerated dynamic MRI [J].
Asif, M. Salman ;
Hamilton, Lei ;
Brummer, Marijn ;
Romberg, Justin .
MAGNETIC RESONANCE IN MEDICINE, 2013, 70 (03) :800-812
[6]  
Asif MS, 2011, INT CONF ACOUST SPEE, P3908
[7]  
Asif MS, 2010, CONF REC ASILOMAR C, P798, DOI 10.1109/ACSSC.2010.5757675
[8]   STREAMING COMPRESSIVE SENSING FOR HIGH-SPEED PERIODIC VIDEOS [J].
Asif, M. Salman ;
Reddy, Dikpal ;
Boufounos, Petros T. ;
Veeraraghavan, Ashok .
2010 IEEE INTERNATIONAL CONFERENCE ON IMAGE PROCESSING, 2010, :3373-3376
[9]   Dynamic Updating for l1 Minimization [J].
Asif, M. Salman ;
Romberg, Justin .
IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, 2010, 4 (02) :421-434
[10]   Streaming Measurements in Compressive Sensing: l1 Filtering [J].
Asif, M. Salman ;
Romberg, Justin .
2008 42ND ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, VOLS 1-4, 2008, :1051-1058