A filtered bucket-clustering method for projection onto the simplex and the l1 ball
成果类型：
Article
署名作者：
Perez, Guillaume; Barlaud, Michel; Fillatre, Lionel; Regin, Jean-Charles
署名单位：
Cornell University; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01401-3
发表日期：
2020
页码：
445-464
关键词：
摘要：
We propose in this paper a new method processing the projection of an arbitrary size vector onto the probabilistic simplex or the l(1) ball. Our method merges two principles. The first one is an original search of the projection using a bucket algorithm. The second one is a filtering, on the fly, of the values that cannot be part of the projection. The combination of these two principles offers a simple and efficient algorithm whose worst-case complexity is linear with respect to the vector size. Furthermore, the proposed algorithm exploits the representation of numeric values in digital computers to define the number of buckets and to accelerate the filtering.