Duchi et. al. (2008) (Reference 1) has a simple and efficient algorithm for projecting a point onto the simplex. Formally, the optimization problem is
where represents the Euclidean norm and is some constant. Their algorithm runs in time, with the most expensive step being sorting the elements of in descending order. Here is the algorithm:
- Sort the elements of in descending order: .
- Find .
- Define .
- Output with .
Note: In some cases, we know that the projection is very likely to be a vertex of the simplex (for example, if the point is very far away from the simplex). For these cases, Ramanath et. al. (2021) (Reference 2, Algorithm 2) have a modified version of the algorithm above (based on Wolfe’s algorithm) that almost always runs in time. For large , dropping the logarithmic factor can make a significant difference.
- Duchi, J., et. al. (2008). Efficient projections onto the l1-ball for learning in high dimensions.
- Ramanath, R., et. al. (2021). Efficient Vertex-Oriented Polytopic Projection for Web-scale Applications.