The Total Variation Denoising Problem is given by:

$$ \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) $$

Where $ $ is the Total Variation Norm.

How could one solve this using MATLAB?


migrated from math.stackexchange.com Apr 25 '17 at 11:30

This question came from our site for people studying math at any level and professionals in related fields.

  • $\begingroup$ Could you formulate the Primal Optimization Problem? $\endgroup$ – Royi May 12 '18 at 9:13

I will solve this for 1D but it could easily generalize into 2D.

The nice thing about the TV Norm that it can be re formulated by the $ {L}_{1} $ of the Derivative Operator:

$$ \operatorname{TV} \left( x \right) = \sum_{i = 1}^{N - 1} \left| {x}_{i + 1} - {x}_{i} \right| = {\left\| D x \right\|}_{1} $$

Where $ D $ is the matrix form of the Derivative Operator.
So the whole problem can be formulated as:

$$ \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) = \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \lambda {\left\| D x \right\|}_{1} $$

For the above there are many solvers based on ADMM or Proximal Gradient Descent.
You could even use the Sub Gradient Method to solve the above as the Sub Gradient is given by:

$$ {A}^{T} \left( A x - y \right) + {D}^{T} \operatorname{sign} \left( D x \right) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy