Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application

Abstract

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.

5 pages

Cited by in corpus (57)

• Agnostic Federated Learning
• Discrete Distribution Estimation under Local Privacy
• Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]
• Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors
• Online Nonnegative Matrix Factorization with Outliers
• Penalty Dual Decomposition Method For Nonsmooth Nonconvex Optimization
• Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations
• Projection onto the capped simplex
• Diversified Hidden Markov Models for Sequential Labeling
• Task-Robust Model-Agnostic Meta-Learning
• Learning to Continuously Optimize Wireless Resource In Episodically Dynamic Environment
• Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints
• CoinDICE: Off-Policy Confidence Interval Estimation
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• First-Order Methods for Large-Scale Market Equilibrium Computation
• Low-rank Characteristic Tensor Density Estimation Part I: Foundations
• Cautious Reinforcement Learning via Distributional Risk in the Dual Domain
• Sublinear Time Spectral Density Estimation
• Effective Scheduling Function Design in SDN through Deep Reinforcement Learning
• Information Leakage Games: Exploring Information as a Utility Function
• Exploiting Storage for Computing: Computation Reuse in Collaborative Edge Computing
• Antipodes of Label Differential Privacy: PATE and ALIBI
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• Minimal Radius Enclosing Polyellipsoids
• Non-smooth Variable Projection
• A distribution-dependent Mumford-Shah model for unsupervised hyperspectral image segmentation
• The Laplacian K-modes algorithm for clustering
• Efficient Online Hyperparameter Optimization for Kernel Ridge Regression with Applications to Traffic Time Series Prediction
• Clustering, factor discovery and optimal transport
• Gradient play in stochastic games: stationary points, convergence, and sample complexity
• Deep Neural Network Training with Frank-Wolfe
• Operator Splitting for Learning to Predict Equilibria in Convex Games
• Neuro-Optimization: Learning Objective Functions Using Neural Networks
• Spectral State Compression of Markov Processes
• Optimality of the Subgradient Algorithm in the Stochastic Setting
• Cyclic Label Propagation for Graph Semi-supervised Learning
• LASS: a simple assignment model with Laplacian smoothing
• Completing a joint PMF from projections: a low-rank coupled tensor factorization approach
• Solving graph compression via optimal transport
• Instance-weighted Central Similarity for Multi-label Image Retrieval
• Adapting The Gibbs Sampler
• Equitable and Optimal Transport with Multiple Agents
• Birds of a Feather Flock Together: A Close Look at Cooperation Emergence via Multi-Agent RL
• MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities
• Gradient Projection for Solving Quadratic Programs with Standard Simplex Constraints
• Blind Hyperspectral-Multispectral Image Fusion via Graph Laplacian Regularization
• Computing the proximal operator of the ${\ell }_1$ induced matrix norm
• Two-component Mixture Model in the Presence of Covariates
• Weighed l1 on the simplex: Compressive sensing meets locality
• Optimal Signal Processing for Common Randomness Generation over MIMO Gaussian Channels with Applications in Identification
• A Boosting Framework on Grounds of Online Learning
• Least Squares Optimal Density Compensation for the Gridding Non-uniform Discrete Fourier Transform
• Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization
• Time-optimality by distance-optimality for parabolic control systems
• Insense: Incoherent Sensor Selection for Sparse Signals