Skip to content

Instantly share code, notes, and snippets.

Created November 2, 2019 22:13
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Projection onto the probability simplex using isotonic regression.
# Author: Mathieu Blondel
# License: BSD 3 clause
import numpy as np
from sklearn.isotonic import isotonic_regression
def projection_simplex(x, z=1):
Compute argmin_{p : p >= 0 and \sum_i p_i = z} ||p - x||
perm = np.argsort(x)[::-1]
x = x[perm]
inv_perm = np.zeros(len(x),
inv_perm[perm] = np.arange(len(x))
x[0] -= z
dual_sol = isotonic_regression(x, increasing=False)
x[0] += z
primal_sol = x - dual_sol
return primal_sol[inv_perm]
if __name__ == '__main__':
rng = np.random.RandomState(None)
x = rng.rand(10)
p = projection_simplex(x)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment