Online adaptive estimation of sparse signals: Where RLS meets the ℓ1-Norm

Daniele Angelosante, Juan Andrés Bazerque, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

215 Scopus citations

Abstract

Using the l1-norm to regularize the least-squares criterion, the batch least-absolute shrinkage and selection operator (Lasso) has well-documented merits for estimating sparse signals of interest emerging in various applications where observations adhere to parsimonious linear regression models. To cope with high complexity, increasing memory requirements, and lack of tracking capability that batch Lasso estimators face when processing observations sequentially, the present paper develops a novel time-weighted Lasso (TWL) approach. Performance analysis reveals that TWL cannot estimate consistently the desired signal support without compromising rate of convergence. This motivates the development of a time- and norm-weighted Lasso (TNWL) scheme with l1-norm weights obtained from the recursive least-squares (RLS) algorithm. The resultant algorithm consistently estimates the support of sparse signals without reducing the convergence rate. To cope with sparsity-aware recursive real-time processing, novel adaptive algorithms are also developed to enable online coordinate descent solvers of TWL and TNWL that provably converge to the true sparse signal in the time-invariant case. Simulated tests compare competing alternatives and corroborate the performance of the novel algorithms in estimating time-invariant signals, and tracking time-varying signals under sparsity constraints.

Original languageEnglish (US)
Article number5439789
Pages (from-to)3436-3447
Number of pages12
JournalIEEE Transactions on Signal Processing
Volume58
Issue number7
DOIs
StatePublished - Jul 2010

Bibliographical note

Funding Information:
Manuscript received September 02, 2009; accepted March 09, 2010. Date of publication March 29, 2010; date of current version June 16, 2010. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Hideaki Sakai. The work in this paper was supported by the NSF Grants CCF 0830480 and CON 0824007, and also through collaborative participation in the Communications and Networks Consortium sponsored by the U. S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. Parts of this paper were presented at the IEEE International Conference on Acoustics, Speech and Signal Processing, Taipei, Taiwan, April 2009, and at the IEEE Workshop on Statistical Signal Processing, Cardiff, Wales, U.K., August 2009.

Keywords

  • Adaptive algorithms
  • Compressive sampling
  • Coordinate descent
  • RLS
  • Sparse linear regression

Fingerprint Dive into the research topics of 'Online adaptive estimation of sparse signals: Where RLS meets the ℓ<sub>1</sub>-Norm'. Together they form a unique fingerprint.

Cite this