Total Variation Denoise One Step

Problem

Take one explicit gradient step on the 1D total variation penalty lam * sum(abs(x_{i+1} - x_i)).

The penalty gradient at x_i is lam * (sign(x_i - x_{i-1}) - sign(x_{i+1} - x_i)), where missing neighbours contribute 0. Return x minus lr times the gradient as a list.

Hint

The TV gradient is a difference of neighbouring signs.

Test cases

case 1

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

expected: [0.05,1,2.95]

case 2

in: [[2,1,2],0.2,1]

expected: [1.8,1.4,1.8]

case 3

in: [[1],0.5,2]

expected: [1]

case 4

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

expected: [0,0,0]

Starter codePython

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

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