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
O(n log n) algorithm for Euclidean projection onto a simplex
Discover more from Marxist Philosophy of Science
Subscribe to get the latest posts sent to your email.
Leave a Comment/Deja un Comentario