Tampere University of Technology

TUTCRIS Research Portal

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

Research output: Contribution to journalArticleScientificpeer-review

Standard

Adaptive Randomized Coordinate Descent for Sparse Systems : Lasso and Greedy Algorithms. / Onose, Alexandru; Dumitrescu, Bogdan.

In: IEEE Transactions on Signal Processing, Vol. 63, No. 15, 01.08.2015, p. 4091-4101.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

Onose, A & Dumitrescu, B 2015, 'Adaptive Randomized Coordinate Descent for Sparse Systems: Lasso and Greedy Algorithms', IEEE Transactions on Signal Processing, vol. 63, no. 15, pp. 4091-4101. https://doi.org/10.1109/TSP.2015.2436369

APA

Onose, A., & Dumitrescu, B. (2015). Adaptive Randomized Coordinate Descent for Sparse Systems: Lasso and Greedy Algorithms. IEEE Transactions on Signal Processing, 63(15), 4091-4101. https://doi.org/10.1109/TSP.2015.2436369

Vancouver

Onose A, Dumitrescu B. Adaptive Randomized Coordinate Descent for Sparse Systems: Lasso and Greedy Algorithms. IEEE Transactions on Signal Processing. 2015 Aug 1;63(15):4091-4101. https://doi.org/10.1109/TSP.2015.2436369

Author

Onose, Alexandru ; Dumitrescu, Bogdan. / Adaptive Randomized Coordinate Descent for Sparse Systems : Lasso and Greedy Algorithms. In: IEEE Transactions on Signal Processing. 2015 ; Vol. 63, No. 15. pp. 4091-4101.

Bibtex - Download

@article{b3a1e23e25724d0f9db5bb1e83f62770,
title = "Adaptive Randomized Coordinate Descent for Sparse Systems: Lasso and Greedy Algorithms",
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",
author = "Alexandru Onose and Bogdan Dumitrescu",
year = "2015",
month = "8",
day = "1",
doi = "10.1109/TSP.2015.2436369",
language = "English",
volume = "63",
pages = "4091--4101",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC",
number = "15",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - Adaptive Randomized Coordinate Descent for Sparse Systems

T2 - Lasso and Greedy Algorithms

AU - Onose, Alexandru

AU - Dumitrescu, Bogdan

PY - 2015/8/1

Y1 - 2015/8/1

N2 - 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.

AB - 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.

KW - Adaptive algorithms

KW - coordinate descent

KW - randomization

KW - sparse filters

U2 - 10.1109/TSP.2015.2436369

DO - 10.1109/TSP.2015.2436369

M3 - Article

VL - 63

SP - 4091

EP - 4101

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 15

ER -