A filtered bucket-clustering method for projection onto the simplex and the $$\ell _1$$ ball
| Autor: | Guillaume Perez, Michel Barlaud, Jean-Charles Régin, Lionel Fillatre |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
021103 operations research
Simplex Efficient algorithm On the fly General Mathematics Numerical analysis 0211 other engineering and technologies Probabilistic logic 010103 numerical & computational mathematics 02 engineering and technology Vector size 01 natural sciences Ball (mathematics) 0101 mathematics Cluster analysis Algorithm Software Mathematics |
| Zdroj: | Mathematical Programming. 182:445-464 |
| ISSN: | 1436-4646 0025-5610 |
| DOI: | 10.1007/s10107-019-01401-3 |
| Popis: | We propose in this paper a new method processing the projection of an arbitrary size vector onto the probabilistic simplex or the $$\ell _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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink