Projection onto the probability simplex

ProofAdvanced⏱ 1 hourAdvanced Optimizationprojectionsimplexkktalgorithm

Theory: Projected, Proximal and Constrained First-Order Methods →

Problem

Derive an algorithm computing $\Pi_\Delta(v) = \arg\min\{\|z-v\|_2 : z\ge0,\ \sum_iz_i=1\}$ and show it runs in $O(d\log d)$ time. State the closed form of the solution in terms of a threshold.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Least squares as orthogonal projection	Classical ML	Proof	Foundation	15 min
The proximal operator of the l1 norm	Advanced Optimization	Proof	Beginner	15 min
Characterising orthogonal projectors	Foundations	Proof	Intermediate	30 min
Complementary slackness and active constraints	Advanced Optimization	Proof	Intermediate	30 min
Conditional expectation minimises mean squared error	Probability	Proof	Intermediate	30 min