TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

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

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut4091-4101
Sivumäärä11
JulkaisuIEEE Transactions on Signal Processing
Vuosikerta63
Numero15
DOI - pysyväislinkit
TilaJulkaistu - 1 elokuuta 2015
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.

Tutkimusalat

Julkaisufoorumi-taso