Fast Projection onto the Simplex and the l1 Ball - Université Grenoble Alpes Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Fast Projection onto the Simplex and the l1 Ball

Résumé

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.
Fichier principal
Vignette du fichier
simplexproj.pdf (129.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01056171 , version 1 (17-08-2014)
hal-01056171 , version 2 (01-09-2015)

Identifiants

  • HAL Id : hal-01056171 , version 1

Citer

Laurent Condat. Fast Projection onto the Simplex and the l1 Ball. 2014. ⟨hal-01056171v1⟩
1709 Consultations
4588 Téléchargements

Partager

Gmail Facebook X LinkedIn More