Accelerated Gradient Descent Method for Projections onto the ℓ1-Ball

Abstract

We present a computationally efficient algorithm to solve the projection onto the ℓ 1 -ball problem, which is cast as an equivalent univariate optimization problem by means of its dual formulation, the ℓ ∞ proximity operator. Our algorithm, which is a customization of the Nesterov's accelerated gradient descent method, is empirically demonstrated to be faster than the state-of-the-art methods for the projection onto the ℓ 1 -ball problem.