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

We provide an elementary proof of a simple, efficient algorithmfor computing the Euclidean projection of a point onto the probability simplex. We also show an application in Laplacian K-modes clustering.

• Publication year

  2013

• Venue

  arXiv.org

• Publication date

  2013-09-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1309.1541
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• LASS: A Simple Assignment Model with Laplacian Smoothing

  2014cited by this paper
• The K-modes algorithm for clustering

  2013cited by this paper
• Projection Onto A Simplex

  2011cited by this paper
• A Finite Algorithm for Finding the Projection of a Point onto the Canonical Simplex of R "

  2009cited by this paper
• Efficient projections onto the l1-ball for learning in high dimensions

  2008cited by this paper
• Efficient Learning of Label Ranking by Soft Projections onto Polyhedra

  2006cited by this paper
• Numerical optimization

  2004cited by this paper
• Numerical Optimization (Springer Series in Operations Research and Financial Engineering)

  2000cited by this paper
• An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds

  1990cited by this paper
• A finite algorithm for finding the projection of a point onto the canonical simplex of ∝n

  1986cited by this paper
• Review of recent development: An O( n) algorithm for quadratic knapsack problems

  1984cited by this paper

• Multi-view subspace clustering with consensus anchors and sparse constraint

  2026cites this paper
• Mitigating Steady-State Bias in Off-Policy TD Learning via Distributional Correction

  2026cites this paper
• ABM-UDE: Developing Surrogates for Epidemic Agent-Based Models via Scientific Machine Learning

  2026cites this paper
• Policy Gradient Algorithms in Average-Reward Multichain MDPs

  2026cites this paper
• RUNs: Fast and Robust Network Slicing for UAV-Assisted Wireless Networks Under Imperfect CSI and Node Mobility

  2026cites this paper
• A General Framework for Group Sparsity in Hyperspectral Unmixing Using Endmember Bundles

  2025cites this paper
• URDM: Hyperspectral Unmixing Regularized by Diffusion Models

  2025cites this paper
• Foundations of Top-k Decoding For Language Models

  2025cites this paper
• Maximum Risk Minimization with Random Forests

  2025influential citation
• On the Consistency and Performance of the Iterative Bayesian Update

  2025cites this paper
• Approximate Message Passing for Quantum State Tomography

  2025cites this paper
• On Group-Level Precoding for Multi-Subcarrier MU-MIMO Systems

  2025influential citation
• Balanced Rate-Distortion Optimization in Learned Image Compression

  2025cites this paper
• Implicit Generative Modeling by Kernel Similarity Matching

  2025cites this paper
• Towards Better IncomLDL: We Are Unaware of Hidden Labels in Advance

  2025cites this paper
• Hadamard-Riemannian Optimization for Margin-Variance Ensemble

  2025cites this paper
• Finding Equilibrium in Some Economics and Game Models

  2025cites this paper
• Penalized jackknife model averaging

  2025cites this paper
• Supervised Integrative Biclustering with applications to Alzheimer's Disease

  2025cites this paper
• FR-LUX: Friction-Aware, Regime-Conditioned Policy Optimization for Implementable Portfolio Management

  2025cites this paper
• Label Shift Meets Online Learning: Ensuring Consistent Adaptation with Universal Dynamic Regret

  2025cites this paper
• Geometry Denoising with Preferred Normal Vectors

  2025cites this paper
• ShortListing Model: A Streamlined SimplexDiffusion for Discrete Variable Generation

  2025cites this paper
• Towards Optimal Offline Reinforcement Learning

  2025cites this paper
• SoK: Descriptive Statistics Under Local Differential Privacy

  2025cites this paper
• Many-to-Many Matching via Sparsity Controlled Optimal Transport

  2025cites this paper
• Every Benchmark All at Once

  2025cites this paper
• Modified Bregman Golden Ratio Algorithm for Mixed Variational Inequality Problems

  2025cites this paper
• Structured multi-view k-means clustering

  2024cites this paper
• A Structured Bipartite Graph Learning method for ensemble clustering

  2024cites this paper
• Structured Bipartite Graph Ensemble Clustering

  2024cites this paper
• Two Models for Surface Segmentation using the Total Variation of the Normal Vector

  2024cites this paper
• Locally Private Set-Valued Data Analyses: Distribution and Heavy Hitters Estimation

  2024cites this paper
• Exploiting Storage for Computing: Computation Reuse in Collaborative Edge Computing

  2024cites this paper
• Primal Methods for Variational Inequality Problems with Functional Constraints

  2024cites this paper
• Unsupervised Feature Selection Algorithm Based on Graph Filtering and Self-representation

  2024cites this paper
• Distributed Joint Beamforming for RIS-assisted Cell-Free MIMO with Discrete Phase Shifts

  2024influential citation
• Splitting Algorithms for Distributionally Robust Optimization

  2024cites this paper
• Rapid Optimization of Superposition Codes for Multi-Hop NOMA MANETs via Deep Unfolding

  2024cites this paper
• Symmetric Splendor: Unraveling Universally Closest Refinements and Fisher Market Equilibrium through Density-Friendly Decomposition

  2024cites this paper
• Qutrit and qubit circuits for three-flavor collective neutrino oscillations

  2024cites this paper
• Stationary and Sparse Denoising Approach for Corticomuscular Causality Estimation

  2024cites this paper
• The Max-Min Formulation of Multi-Objective Reinforcement Learning: From Theory to a Model-Free Algorithm

  2024cites this paper
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient

  2024cites this paper
• No Regularization Is Needed: Efficient and Effective Incomplete Label Distribution Learning

  2024cites this paper
• LabelDP-Pro: Learning with Label Differential Privacy via Projections

  2024cites this paper
• Hotspot-Driven Peptide Design via Multi-Fragment Autoregressive Extension

  2024cites this paper
• Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods

  2024cites this paper
• Over the Air Based Distributed Beamforming Design for RIS Aided Cell-Free MIMO Systems

  2024cites this paper
• Social Optimum of a Linear Quadratic Collective Choice Model under Congestion

  2024cites this paper
• Dirichlet Flow Matching with Applications to DNA Sequence Design

  2024cites this paper
• Label Shift Correction via Bidirectional Marginal Distribution Matching

  2024cites this paper
• Full-Atom Peptide Design based on Multi-modal Flow Matching

  2024cites this paper
• Parallelly Sliced Optimal Transport on Spheres and on the Rotation Group

  2024cites this paper
• An initially robust minimum simplex volume-based method for linear hyperspectral unmixing

  2024cites this paper
• Deep Unfolded Superposition Coding Optimization for Two-Hop NOMA MANETs

  2023cites this paper
• Generating Adversarial Examples with Task Oriented Multi-Objective Optimization

  2023cites this paper
• Game-Theoretic Deception Methods for Perfectly and Bounded Rational Stealthy Attackers

  2023cites this paper
• Alternating direction method of multipliers for linear hyperspectral unmixing

  2023cites this paper
• Projected Policy Gradient Converges in a Finite Number of Iterations

  2023cites this paper
• Graph-Based Active Learning for Nearly Blind Hyperspectral Unmixing

  2023cites this paper
• Direction-oriented Multi-objective Learning: Simple and Provable Stochastic Algorithms

  2023cites this paper
• An Online Multiple Kernel Parallelizable Learning Scheme

  2023cites this paper
• MKL-$L_{0/1}$-SVM

  2023cites this paper
• Unveiling the Role of Message Passing in Dual-Privacy Preservation on GNNs

  2023cites this paper
• Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets

  2023cites this paper
• A proof of convergence of inverse reinforcement learning for multi-objective optimization

  2023cites this paper
• Convex optimization over a probability simplex

  2023cites this paper
• SS-ADMM: Stationary and Sparse Granger Causal Discovery for Cortico-Muscular Coupling

  2023cites this paper
• BanditQ: Fair Bandits with Guaranteed Rewards

  2023cites this paper
• Audio source separation by estimating the mixing matrix in underdetermined condition using successive projection and volume minimization

  2023cites this paper
• Inaccurate Label Distribution Learning

  2023cites this paper
• A Bregman–Kaczmarz method for nonlinear systems of equations

  2023cites this paper
• Label-Affinity Self-Adaptive Central Similarity Hashing for Image Retrieval

  2023influential citation
• Optimization in the space domain for density compensation with the nonuniform FFT.

  2023cites this paper
• Scalable Randomized Kernel Methods for Multiview Data Integration and Prediction (preprint)

  2023cites this paper
• SHAPER: can you hear the shape of a jet?

  2023cites this paper
• A Novel Framework for Policy Mirror Descent with General Parametrization and Linear Convergence

  2023influential citation
• Community Detection via Multihop Nonnegative Matrix Factorization

  2023influential citation
• On the Robustness of Randomized Ensembles to Adversarial Perturbations

  2023cites this paper
• A hash centroid construction method with Swin transformer for multi-label image retrieval

  2023influential citation
• Bridging the Usability Gap: Theoretical and Methodological Advances for Spectral Learning of Hidden Markov Models

  2023influential citation
• On the Convergence of Projected Policy Gradient for Any Constant Step Sizes

  2023cites this paper
• No Regularization is Needed: An Efficient and Effective Model for Incomplete Label Distribution Learning

  2023cites this paper
• Fast Bellman Updates for Wasserstein Distributionally Robust MDPs

  2023cites this paper
• Data Structures for Deviation Payoffs

  2023cites this paper
• A Tensor Optimization Algorithm for Computing Lagrangians of Hypergraphs

  2023cites this paper
• MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities

  2022cites this paper
• Cross-view graph matching for incomplete multi-view clustering

  2022cites this paper
• Learning Globally Smooth Functions on Manifolds

  2022cites this paper
• Sparse and risk diversification portfolio selection

  2022cites this paper
• Bregman-Golden Ratio Algorithms for Variational Inequalities

  2022cites this paper
• Adaptive KNN and graph-based auto-weighted multi-view consensus spectral learning

  2022cites this paper
• Reconstruction of the distribution of sensitive data under free-will privacy

  2022cites this paper
• Optimal and Robust Category-Level Perception: Object Pose and Shape Estimation From 2-D and 3-D Semantic Keypoints

  2022cites this paper
• A single cut proximal bundle method for stochastic convex composite optimization

  2022cites this paper
• Joint Active and Passive Beamforming for RIS-Aided MIMO Communications With Low-Resolution Phase Shifts

  2022cites this paper
• Faster and Scalable Algorithms for Densest Subgraph and Decomposition

  2022cites this paper
• Waserstein model reduction approach for parametrized flow problems in porous media

  2022cites this paper
• Statistica Sinica

  2022cites this paper