Fast Projection onto the Simplex and the l1 Ball

Laurent Condat (1)

1 GIPSA-AGPIG - GIPSA - Architecture, Géométrie, Perception, Images, Gestes

A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or a l1-norm ball. The algorithm is demonstrated to be faster than existing methods. In addition, a wrong statement in a paper by Duchi et al. is corrected and an adversary sequence for Michelot's algorithm is exhibited, showing that it has quadratic complexity in the worst case.

Mots clés: Simplex; l1-norm ball; large-scale optimization

Domaines: Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Laurent Condat. Fast Projection onto the Simplex and the l1 Ball. 2014. ⟨hal-01056171v1⟩