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

摘要

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.