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.
Citation
Preprint Hal-01056171, v1, Aug. 2014