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 an l1-norm ball. It can be viewed as a Gauss-Seidel-like variant of Michelot’s variable fixing algorithm; that is, the threshold used to fix the variables is updated after each element is read, instead of waiting for a full reading pass over the list of non-fixed elements. This algorithm is empirically demonstrated to be faster than existing methods.

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. Mathematical Programming, Series A, 2016, 158 (1), pp.575-585. ⟨10.1007/s10107-015-0946-6⟩. ⟨hal-01056171v2⟩