Simplex Projection

Problem

The Euclidean projection of a vector onto the probability simplex {x : x_i >= 0, sum(x) = 1} is computed by sorting the values in descending order, finding the largest rho with u_rho - (sum of top rho - 1) / rho > 0, setting theta to that value, and returning max(v_i - theta, 0).

Given the values, return the projected vector.

Hint

A single scalar shift makes all coordinates nonnegative and forces the sum to 1.

Test cases

case 1

in: [[0.5,0.5]]

expected: [0.5,0.5]

case 2

in: [[1,0,0]]

expected: [1,0,0]

case 3

in: [[0.2,0.2,0.2]]

expected: [0.3333333333333333,0.3333333333333333,0.3333333333333333]

case 4

in: [[2,0.5,0.5]]

expected: [1,0,0]

case 5

in: [[-1,2,0.5]]

expected: [0,1,0]

Starter codePython

def simplex_projection(values):
    # Your code here
    pass

5 test cases · run your code against them in the editor