OPTEC - K.U.Leuven Center of Excellence: Optimization in Engineering

"A Lower Complexity Bound for l1-regularized Least-squares Problems using a Certain Class of Algorithms"

Tobias Lindstrøm Jensen
Deparment of Electronic Systems at Aalborg University 

The l1-regularized least-squares problem have received broad attention the last couple of years. The result is numerous approaches for reliable large-scale solvers which combines both well known methods and recently developed techniques for efficient computations. We define a class of algorithms which is not as restrictive as classic black-box algorithms and hence includes most of the recently proposed methods. We show how to obtain a worst-case convergence rate for all these methods.