Chambolle-Pock Algorithm

The Chambolle–Pock (primal–dual hybrid gradient) algorithm solves saddle-point problems

$$\underset{x}{\min }\underset{p}{\max }⟨Kx,p⟩+G(x)-F^{\ast }(p),$$

which is the primal–dual form of ${\min }_{x}F(Kx)+G(x)$. It needs only products with $K$ and $K^{\top }$ and the proximal operators of $G$ and $F^{\ast }$.

Iteration (step sizes $\tau ,s>0$ with $\tau s\Vert K{\Vert }^2<1$, $\theta =1$):

$$\begin{array}{rl}{p}^{k+1}& ={\mathrm{prox}}_{s{F}^{\ast }}(p^k+sK{\bar{x}}^k),\\ x^{k+1}& ={\mathrm{prox}}_{\tau G}(x^k-\tau K^{\top }{p}^{k+1}),\\ {\bar{x}}^{k+1}& =x^{k+1}+\theta (x^{k+1}-x^k).\end{array}$$

TV denoising (ROF prox). For ${\min }_z\beta \mathrm{TV}(z)+\frac{\rho }{2}\Vert z-y{\Vert }^2$ take $K=\nabla$ (discrete gradient), $F=\beta \Vert \cdot {\Vert }_{2,1}$ and $G=\frac{\rho }{2}\Vert \cdot -y{\Vert }^2$. Then:

• ${\mathrm{prox}}_{s{F}^{\ast }}$ is the pointwise projection of $p$ onto the ball $|p|\le \beta$;
• $K^{\top }=-\mathrm{div}$;
• ${\mathrm{prox}}_{\tau G}(v)=\frac{v+\tau \rho y}{1+\tau \rho }$.

For the standard forward-difference gradient on a unit grid, $\Vert \nabla {\Vert }^2\le 8$ in 2D.

This computes the Total Variation prox exactly, without smoothing. It can be used as the regulariser step in ADMM.

In ModularEIT.jl: prox!, TotalVariationRegularizer.

References

1. A. Chambolle, T. Pock (2011). A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. J. Math. Imaging Vis. 40, 120–145. doi:10.1007/s10851-010-0251-1
2. A. Chambolle, V. Caselles, D. Cremers, M. Novaga, T. Pock (2010). An Introduction to Total Variation for Image Analysis. In: Theoretical Foundations and Numerical Methods for Sparse Recovery, de Gruyter, 263–340. doi:10.1515/9783110226157.263