Skip to content

Instantly share code, notes, and snippets.

Embed
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), dtype=np.int)
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)
print(p)
print(np.sum(p))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.