An Accelerated Newton’s Method for Projections onto the l1-BallPP

We present two computationally efficient algorithms to solve the projection onto the $\ell_1$-ball (P$\ell_1$) problem. Considering an interpretation of the Michelot’s algorithm as Newton's method, our first algorithm can be understood as an accelerated Newton's method, while for the second we leverage P$\ell_1$'s dual, the $\ell_\infty$ proximity operator. Both algorithms need significantly less major iterations to converge to the solution and are empirically demonstrated to be faster than the state-of-the-art methods for P$\ell_1$.

This is poster number 23 in Poster Session

Paul Rodriguez (Pontificia Universidad Catolica del Peru)
accelerated newton, inverse problems, l1-norm ball, simplex