1
$\begingroup$

I am trying to work through the "Mathematical exposition for 1D digital signals" in the wikipedia entry for Total Variation Denoising (TVD). I am familiar with Lagrange multipliers. However, I cant understand how to differentiate $V(y)$ and $E(x,y)$ with respect to $y_n$. Could someone walk me through this? A perfect answer would provide math and code I can use to step through in a numerical example.

Thanks!

$\endgroup$
1
  • $\begingroup$ Could you explain what you need? How to solve it? $\endgroup$
    – Royi
    Aug 26, 2017 at 11:28

1 Answer 1

1
$\begingroup$

Total variation is not differentiable when $y_{n+1} - y_n = 0$, because of the $\ell_1$ norm.

You will have to resort to either a subgradient method, or do a change of variables and use the soft-thresholding operator to solve the proximal problem. You can also replace the problem with a smooth approximation.

$\endgroup$
2
  • $\begingroup$ 1) Can you enlarge upon your first point? Is this because of the 'v' in the graph y = |x|? 2) Lets say the situation yn+1 - yn = 0 never occurs - i'm just trying to get a sense of how to do this $\endgroup$ Feb 19, 2015 at 10:02
  • $\begingroup$ Yes, your function, $V(y)=\sum_n |y_{n+1}-y_n|$ is not differentiable, because the $\ell_1$ norm is not differentiable at zero. Its subdifferential at zero is $[-1,1]$, so you can minimise $E+\lambda V$ by a subgradient algorithm. They are generally very slow, thought, so I recommend you use the other approaches I mentioned. Don't assume a possible situation will never occur; you will be taunting Murphy ;-) $\endgroup$
    – Tommy L
    Feb 19, 2015 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.