Scientific Lectures //
An Accelerated Newton’s Method for Projections onto the l1-Ball: Derivation and Applications to inverse Problems
Paul Rodriguez, Ph.D., Professor, Department of Electrical Engineering, Pontificia Universidad Católica del Perú (PUCP)
Presented: November 10, 2017
ABSTRACT: We present a simple and computationally efficient algorithm,based on the accelerated Newton’s method, to solve the root finding problem associated with the projection onto the l1-ball problem. Considering an interpretation of the Michelot’s algorithm as Newton method, our algorithm can be understood as an accelerated version of the Michelot’s algorithm, that needs significantly less major iterations to converge to the solution. Although the worst-case performance of the propose algorithm is O(n^2), it exhibits in practice an O(n) performance and it is empirically demonstrated that it is competitive or faster than existing methods.
Furthermore, when compared to l1-regularized problems, the l1-constraint counterpart usually exhibits an advantage in practical parameter selection that improve their practical performance. This will be empirically shown for the Basis Pursuit, Convolutional Sparse Coding and Robust PCA (a.k.a. Principal Component Pursuit) problems.
To view presentation please click here.