Projection Onto L1 Ball

Problem

The Euclidean projection onto the L1 ball of radius r keeps points with ||x||_1 <= r and otherwise soft-thresholds with the threshold tau chosen so the sum of the positive parts equals r: sort |x| descending, find the largest count with u_j - (cumulative - r) / j > 0, and shrink by tau = (cumulative - r) / j preserving signs.

Given x and r > 0, return the projection.

Hint

Find the threshold from the sorted magnitudes, then shrink while keeping signs.

Test cases

case 1

in: [[3,0],1]

expected: [1,0]

case 2

in: [[1,1],1]

expected: [0.5,0.5]

case 3

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

expected: [1,-1,0]

Starter codePython

def projection_onto_l1_ball(x, radius):
    # Your code here
    pass

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