l1 projection

l1_proj.py

def l1_simplex_proj(x, radius=1.0):
    z = np.abs(x)
    mu = np.sort(z)[::-1] 
    cmu = np.cumsum(mu)
    f = mu * np.arange(1, 1 + len(x)) - (cmu - radius)
    rho = np.where(f > 0)[0][-1]
    theta = (cmu[rho] - radius) / (1.0 + rho)
    y = np.sign(x) * np.maximum(z - theta, 0)
    return y