(ss:tv_denoising)=
# 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:
```{math}
:label: eq:CP-TV_problem

\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
{eq}`eq:CP-TV_problem` we have to further investigate the two prox
operators in {eq}`eq:CP-update_y_prox` and {eq}`eq:CP-update_x_prox`.

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
```{math}
\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
{eq}`eq:CP-update_y_prox` becomes:
```{math}
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.,
```{math}
\partial G(x) \ = \ \frac{x - x_0}{\lambda} \ .
```
As we recall from Section {ref}`ss:general_convex` we need to fulfill:
```{math}
\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:
```{math}
y^{k+1} \ = \ \frac{y^k + \sigma \nabla \overline{x}^k}{\max(1, ||y^k + \sigma \nabla \overline{x}^k||)}
```

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

```{math}
\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$.