Fast projection onto the simplex and the ball

• 成果类型: Article
• 署名作者: Condat, Laurent
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0946-6
• 发表日期: 2016
• 页码: 575-585
• 关键词: algorithms; SPARSE

摘要

A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or an -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.