O(n log n) algorithm for Euclidean projection onto a simplex

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: […]

O(n log n) algorithm for Euclidean projection onto a simplex

Leave a comment