Tampere University of Technology

TUTCRIS Research Portal

Adaptive Randomized Coordinate Descent for Sparse Systems: Lasso and Greedy Algorithms

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)4091-4101
Number of pages11
JournalIEEE Transactions on Signal Processing
Volume63
Issue number15
DOIs
Publication statusPublished - 1 Aug 2015
Publication typeA1 Journal article-refereed

Abstract

Coordinate descent (CD) is a simple optimization technique suited to low complexity requirements and also for solving large problems. In randomized version, CD was recently shown as very effective for solving least-squares (LS) and other optimization problems. We propose here an adaptive version of randomized coordinate descent (RCD) for finding sparse LS solutions, from which we derive two algorithms, one based on the lasso criterion, the other using a greedy technique. Both algorithms employ a novel way of adapting the probabilities for choosing the coordinates, based on a matching pursuit criterion. Another new feature is that, in the lasso algorithm, the penalty term values are built without knowing the noise level or using other prior information. The proposed algorithms use efficient computations and have a tunable trade-off between complexity and performance through the number of CD steps per time instant. Besides a general theoretical convergence analysis, we present simulations that show good practical behavior, comparable to or better than that of state of the art methods.

Keywords

  • Adaptive algorithms, coordinate descent, randomization, sparse filters

Publication forum classification

Field of science, Statistics Finland