Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
By Weiran Wang, M. A. Carreira-Perpiñán. 2013
330 citations recorded by the source corpus.
We provide an elementary proof of a simple, efficient algorithmfor computing the Euclidean projection of a point onto the probability simplex. We also show an application in Laplacian K-modes clustering.
Subfields: Artificial Intelligence, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Ananda Theertha Suresh
- Mehryar Mohri
- Aleksandra Korolova
- Benjamin Livshits
- Gary Sivek
- David Zeber
- Brendan Avent
- Torgeir Hovden
In Signal Processing
- Ananda Theertha Suresh
- Hao Cui
- Benjamin Livshits
- Jun Sakuma
- Roni Khardon
- Takao Murakami
- Aleksandra Korolova
- Hideitsu Hino
Citations in the corpus
- Agnostic Federated Learning (2019, methodology): “If Λ is the full simplex, then there is a near-linear time algorithm for this projection Wang and Carreira-Perpin´an (2013).”
- BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, methodology): “However, since we use the method of [39] in BlendProbabilities, the probability estimates involving ? have a minor implicit effect on the L1 and NDCG scores.”
- Local Differential Private Data Aggregation for Discrete Distribution Estimation (2019, background): “the true distribution u is randomly generated (except for experiments on real-world datasets), and the estimated distribution û of the true distribution is postprocessed by projecting onto the probability simplex [45].”
- Mutual Information Optimally Local Private Discrete Distribution Estimation (2016, methodology): “During each simulation, the truly distribution θ is generated randomly, the estimated distribution ˆ θ is postprocessed by projecting onto probability simplex [25][5].”
- Toward Distribution Estimation under Local Differential Privacy with Small Samples (2018, methodology): “The second method is a projected decoder, which projects p̂ onto the probability simplex C so that the Euclidean distance between the two points is minimized (using the algorithm in [48]).”
- Online Symbolic Gradient-Based Optimization for Factored Action MDPs (2016, methodology): “To achieve this we use a known algorithm [Wang and Carreira-Perpiñán, 2013; Duchi et al., 2008] to project onto a scaled probability simplex P a”