Source-linked AI summary
Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
Weiran Wang, Miguel Á. Carreira-Perpiñán
TL;DR
The paper addresses efficient Euclidean projection onto the probability simplex, presents a simple sorting-based algorithm, and proves its correctness using KKT conditions. It also applies the projection to Laplacian K-modes clustering, where row-wise simplex projections arise in gradient projection.
Problem
Computing Euclidean projection onto the probability simplex is the paper’s central optimization problem, which also arises in Laplacian K-modes clustering.
Method
The paper analyzes a sorting-based shift-and-threshold algorithm, gives an elementary KKT proof, and uses the projection within gradient projection for Laplacian K-modes clustering.
Results
The algorithm identifies the active set exactly after at most D steps after sorting and supplies the simplex projection used in the clustering optimization.
Takeaways & Limitations
The projection provides a simple, non-iterative operation for simplex-constrained optimization and for row-wise soft assignments in Laplacian K-modes clustering.
Abstract
from arXiv · showhide
We provide an elementary proof of a simple, efficient algorithm for computing the Euclidean projection of a point onto the probability simplex. We also show an application in Laplacian K-modes clustering.
1 Projection onto the probability simplex
The section formulates Euclidean projection of a point onto the probability simplex as a strictly convex quadratic program with a unique solution.
- 1 Projection onto the probability simplex: The projection problem computes the Euclidean projection of y onto the probability simplex.The simplex-constrained optimization is introduced for y∈R^D.
- 1 Projection onto the probability simplex: Strict convexity of the quadratic objective guarantees a unique solution x.
2 Algorithm
The proposed algorithm sorts the input, identifies the active positive components, and shifts and thresholds the entries to obtain the simplex projection efficiently.
- 2 Algorithm: O(D log D) complexity is dominated by sorting, while the active set is identified exactly after at most D steps.The method is non-iterative and can be implemented directly.
- 2 Algorithm: The algorithm sorts y in descending order and finds the largest index ρ satisfying the cumulative-sum test.
- 2 Algorithm: It outputs x_i = max{y_i + λ, 0}, with λ chosen so the components sum to 1.The shift-and-threshold form gives the projected vector.
- 2 Algorithm: The geometric interpretation is a rigid shift of the values followed by retaining points whose shifted values are positive and sum to 1.
- 2 Algorithm: The pseudocode also appears in Duchi et al. (2008), while earlier work solved more general versions of the problem.
- 2 Algorithm: Algorithm 1 is simple and non-iterative compared with alternative quadratic-programming and projection approaches.Other approaches include active-set, gradient-projection, interior-point, alternating-projection, and dual methods.
3 A simple proof
The paper proves correctness using KKT conditions: positive solution components share a common shift, while the remaining components are zero, and the algorithm detects their count.
- 3 A simple proof: The paper offers an elementary KKT-based proof of Algorithm 1’s correctness.Earlier proofs are cited, but this proof is presented as simpler.
- 3 A simple proof: KKT stationarity and complementarity imply x_i = y_i + λ for positive components and y_i + λ ≤ 0 for zero components.
- 3 A simple proof: The solution has ρ positive components followed by zero components, with x_1 ≥ ··· ≥ x_ρ > 0 and x_ρ+1 = ··· = x_D = 0.Because y is sorted, the zero components correspond to the smaller entries of y.
- 3 A simple proof: Once ρ is known, λ and the optimal solution follow by shifting every component of y and thresholding at zero.The resulting vector satisfies the KKT conditions.
- 3 A simple proof: The test remains positive through j = ρ and becomes non-positive afterward, so it identifies the exact number of positive solution components.
- 3 A simple proof: At the stopping index, the tentative vector has positive first j components summing to 1, and the next component is zero, satisfying all KKT conditions.
- 3 A simple proof: For a simplex scaled to x⊤1 = a with a > 0, the algorithm replaces the unit-sum terms by a.
4 Matlab code
The section provides vectorized Matlab code that applies the projection algorithm independently to every row of an N × D matrix.
- 4 Matlab code: The Matlab implementation projects each row vector of Y onto the probability simplex in D dimensions.
- 4 Matlab code: The code sorts rows, computes cumulative sums and candidate thresholds, then applies the resulting shift and nonnegative thresholding.
5 An application: Laplacian K-modes clustering
Laplacian K-modes uses simplex-constrained soft assignments and applies simplex projection in both training and out-of-sample mapping. The proposed projection solves each assignment row efficiently while preserving the clustering constraints.
- Training: Training alternates minimization over the assignment matrix Z and cluster modes C.With C fixed, optimizing Z is a quadratic program with NK variables.
- Training: For fixed C, accelerated gradient projection updates Z and projects each row independently onto a K-dimensional probability simplex.The convexity of the subproblem follows from the positive semidefiniteness of the graph Laplacian.
- Out-of-sample mapping: For a new point, the method fixes the trained Z and C and optimizes only its K-dimensional assignment vector.This avoids resolving assignments for all training points.
- Out-of-sample mapping: The new-point assignment is obtained by projecting an average combining training assignments and point-to-centroid affinities onto the probability simplex.The projected vector is z̄ + γg, where γ depends on the new point's affinities to the training data.
- Laplacian K-modes clustering: The model learns soft assignments z_nk for N items across K categories using an item-item graph Laplacian and item-category similarities.The assignment constraints require each z_nk to be nonnegative and each item's assignments to sum to one.