5.4. Special case: TV denoising

We can use the above derived general optimization scheme for the special case of total variation denoising of a given (discrete) noisy image \(x_0 \in \mathbb{R}^n\), i.e., solving the following minimization problem:

(5.15)\[\min_{x \in \mathbb{R}^n} \frac{1}{2}||x - x_0||^2 + \lambda ||\nabla x||_{l^1} \ , \quad \lambda > 0 \ .\]

In this case it gets clear that: \(G(\cdot) = \frac{1}{2\lambda}||\cdot - x_0||^2\), \(F(\cdot) = ||\cdot||_{1}\), and \(K = \nabla\) is the gradient operator in \(\mathbb{R}^n\). We also directly see that \(K^* = -\operatorname{div}\) is the divergence operator. To numerically compute an optimal solution to (5.15) we have to further investigate the two prox operators in (5.12) and (5.13).

We know that \(F^*(y) = \chi_B(y)\) is the indicator function of the convex ball \(B = \{z \in Y : ||z||_\infty \leq 1\}\). One can show that

\[\operatorname{prox}_{\sigma F^*}(y) \ = \ \operatorname{prox}_{\chi_B}(y) \ = \ \Pi_B(y)\]

is the projection onto the convex ball \(B\). Hence, the update step (5.12) becomes:

\[y^{k+1} \ = \ \frac{z}{\max(1, ||z||)} \quad \text{ with } \quad z \ = \ y^k + \sigma \nabla x^k\]

Then, we see that \(G\) is strictly convex and even differentiable and thus the subdifferential \(\partial G\) is always a singleton, i.e.,

\[\partial G(x) \ = \ \frac{x - x_0}{\lambda} \ .\]

As we recall from Section ss:general_convex we need to fulfill:

\[\begin{aligned} x^k - \tau K^*y^{k+1} \ &=& \ x^k + \tau \operatorname{div}y^{k+1} \ = \ x^{k+1} + \tau \frac{x^{k+1} - x_0}{\lambda} \\ \Leftrightarrow \ x^{k+1} \ &=& \ \frac{x^k + \tau (\operatorname{div}y^{k+1} + x_0/\lambda)}{1 + \tau / \lambda} \end{aligned}\]

Thus, the general alternating optimization scheme becomes:

\[y^{k+1} \ = \ \frac{y^k + \sigma \nabla \overline{x}^k}{\max(1, ||y^k + \sigma \nabla \overline{x}^k||)}\]

\[x^{k+1} \ = \ \frac{x^k + \tau (\operatorname{div}y^{k+1} + x_0/\lambda)}{1 + \tau / \lambda}\]

\[\overline{x}^{k+1} \ = \ x^{k+1} + \Theta(x^{k+1} - x^k)\]

A sufficient condition for the convergence of the iteration scheme in case of two-dimensional discrete images is \(\tau \sigma < \frac{1}{8}\), e.g., by choosing \(\tau = \sigma = 0.35\).