Fused Lasso One Step

Problem

Take one proximal step for the fused lasso in 1D.

First do a gradient step z_i = x_i - lr * (x_i - y_i), then process i = 1 .. n-1 and replace z_i by z_{i-1} + soft(z_i - z_{i-1}, lr * lam). Return the resulting list.

Hint

Soft threshold each successive difference against lam * lr.

Test cases

case 1

in: [[0,1,0],[0,1,0],0.5,0.2]

expected: [0,0.9,0.1]

case 2

in: [[1,2],[0,0],0.1,0.5]

expected: [0.9,1.75]

case 3

in: [[3],[3],0.5,1]

expected: [3]

Starter codePython

def fused_lasso_step(x, y, lr, lam):
    # Your code here
    pass

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