Chambolle-Pock algorithm explained

In mathematics, the Chambolle-Pock algorithm is an algorithm used to solve convex optimization problems. It was introduced by Antonin Chambolle and Thomas Pock^[1] in 2011 and has since become a widely used method in various fields, including image processing, computer vision,^[2] and signal processing.^[3]

The Chambolle-Pock algorithm is specifically designed to efficiently solve convex optimization problems that involve the minimization of a non-smooth cost function composed of a data fidelity term and a regularization term. This is a typical configuration that commonly arises in ill-posed imaging inverse problems such as image reconstruction,^[4] denoising^[5] and inpainting.^[6]

The algorithm is based on a primal-dual formulation, which allows for simultaneous updates of primal and dual variables. By employing the proximal operator, the Chambolle-Pock algorithm efficiently handles non-smooth and non-convex regularization terms, such as the total variation, specific in imaging framework.

Problem statement

Let be

l{X}, l{Y} two real vector spaces equipped with an inner product \langle ⋅ , ⋅ \rangle and a norm \lVert ⋅ \rVert = \langle ⋅ , ⋅ \rangle ^{(1)/(2)} . From up to now, a function F is called simple if its proximal operator prox _{\tau} has a closed-form representation or can be accurately computed, for \tau > 0 , where prox _{\tau} is referred to

$$x\; =\; \backslash text\_(\backslash tilde)\; =\; \backslash text\; \backslash min\_\backslash left\backslash$$

Consider the following constrained primal problem:

$$\backslash min\_\; F(Kx)\; +\; G(x)$$

where

K: l{X} → l{Y} is a bounded linear operator, F: l{Y} → [ 0 , +inf ty), G: l{X} → [ 0 , +inf ty) are convex, lower semicontinuous and simple.

The minimization problem has its dual corresponding problem as

$$\backslash max\_\; -\backslash left(G^*(-K^*y)\; +\; F^*(y)\backslash right)$$

where

F ^{*,} G ^{*} and K ^{*} are the dual map of F, G and K , respectively.

Assume that the primal and the dual problems have at least a solution

(\hat{x}, \hat{y}) \in l{X} x l{Y} , that means they satisfies^[7]

where

\partial F ^{*} and \partial G are the subgradient of the convex functions F ^{*} and G , respectively.

The Chambolle-Pock algorithm solves the so-called saddle-point problem

$$\backslash min\_\; \backslash max\_\; \backslash langle\; Kx,\; y\; \backslash rangle\; +\; G(x)\; -\; F^*(y)$$

which is a primal-dual formulation of the nonlinear primal and dual problems stated before.

Algorithm

The Chambolle-Pock algorithm primarily involves iteratively alternating between ascending in the dual variable

y and descending in the primal variable x using a gradient-like approach, with step sizes \sigma and \tau respectively, in order to simultaneously solve the primal and the dual problem. Furthermore, an over-relaxation technique is employed for the primal variable with the parameter \theta . stopping criterion.

end doChambolle and Pock proved that the algorithm converges if

\theta = 1 and \tau \sigma \lVert K \rVert ^{2} \leq 1 , sequentially and with l{O}(1/N) as rate of convergence for the primal-dual gap. This has been extended by S. Banert et al.^[8] to hold whenever \theta> 1 / 2 and \tau \sigma \lVert K \rVert ^{2} < 4 / ( 1+2 \theta) .

The semi-implicit Arrow-Hurwicz method^[9] coincides with the particular choice of

\theta = 0 in the Chambolle-Pock algorithm.

Acceleration

There are special cases in which the rate of convergence has a theoretical speed up. In fact, if

G , respectively F ^{*} , is uniformly convex then G ^{*} , respectively F , has a Lipschitz continuous gradient. Then, the rate of convergence can be improved to l{O}(1/N ^{2)} , providing a slightly changes in the Chambolle-Pock algorithm. It leads to an accelerated version of the method and it consists in choosing iteratively \tau _{n,} \sigma _{n} , and also \theta _{n} , instead of fixing these values.

In case of

G uniformly convex, with \gamma> 0 the uniform-convexity constant, the modified algorithm becomes

stopping criterion.

end doMoreover, the convergence of the algorithm slows down when

L , the norm of the operator K , cannot be estimated easily or might be very large. Choosing proper preconditioners T and \Sigma , modifying the proximal operator with the introduction of the induced norm through the operators T and \Sigma , the convergence of the proposed preconditioned algorithm will be ensured.^[10]

Application

A typical application of this algorithm is in the image denoising framework, based on total variation. It operates on the concept that signals containing excessive and potentially erroneous details exhibit a high total variation, which represents the integral of the absolute value gradient of the image. By adhering to this principle, the process aims to decrease the total variation of the signal while maintaining its similarity to the original signal, effectively eliminating unwanted details while preserving crucial features like edges. In the classical bi-dimensional discrete setting,^[11] consider

l{X} = R ^{NM} , where an element u\in l{X} represents an image with the pixels values collocated in a Cartesian grid N x M .

Define the inner product on

l{X} as

$\backslash langle\; u,\; v\backslash rangle\_\; =\; \backslash sum\_\; u\_v\_,\backslash quad\; u,v\; \backslash in\; \backslash mathcal$that induces an

L ^{2} norm on l{X} , denoted as \lVert ⋅ \rVert _{2} .

Hence, the gradient of

u is computed with the standard finite differences,

$\backslash left(\backslash nabla\; u\; \backslash right)\_\; =\; \backslash left(\backslash begin\backslash left(\backslash nabla\; u\; \backslash right)^1\_\backslash \backslash \backslash left(\backslash nabla\; u\; \backslash right)^2\_\backslash end\backslash right)$

which is an element of the space

l{Y}= l{X} x l{X} , where

Notes and References

1. Chambolle . Antonin . Pock . Thomas . 2011-05-01 . A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging . Journal of Mathematical Imaging and Vision . en . 40 . 1 . 120–145 . 10.1007/s10851-010-0251-1 . 207175707 . 1573-7683.
2. Book: Pock . Thomas . Cremers . Daniel . Bischof . Horst . Chambolle . Antonin . 2009 IEEE 12th International Conference on Computer Vision . An algorithm for minimizing the Mumford-Shah functional . 2009 . https://ieeexplore.ieee.org/document/5459348 . 1133–1140 . 10.1109/ICCV.2009.5459348. 978-1-4244-4420-5 . 15991312 .
3. 2014 . A Generic Proximal Algorithm for Convex Optimization—Application to Total Variation Minimization . IEEE Signal Processing Letters . 21 . 8 . 985–989 . 10.1109/LSP.2014.2322123 . 2014ISPL...21..985. . 8976837 . 1070-9908.
4. Sidky . Emil Y . Jørgensen . Jakob H . Pan . Xiaochuan . 2012-05-21 . Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm . Physics in Medicine and Biology . 57 . 10 . 3065–3091 . 10.1088/0031-9155/57/10/3065 . 0031-9155 . 3370658 . 22538474. 1111.5632 . 2012PMB....57.3065S .
5. Fang . Faming . Li . Fang . Zeng . Tieyong . 2014-03-13 . Single Image Dehazing and Denoising: A Fast Variational Approach . SIAM Journal on Imaging Sciences . en . 7 . 2 . 969–996 . 10.1137/130919696 . 1936-4954.
6. Allag . A. . Benammar . A. . Drai . R. . Boutkedjirt . T. . 2019-07-01 . Tomographic Image Reconstruction in the Case of Limited Number of X-Ray Projections Using Sinogram Inpainting . Russian Journal of Nondestructive Testing . en . 55 . 7 . 542–548 . 10.1134/S1061830919070027 . 203437503 . 1608-3385.
7. Book: Ekeland . Ivar . Convex Analysis and Variational Problems . Témam . Roger . 1999 . Society for Industrial and Applied Mathematics . 978-0-89871-450-0 . 61 . en . 10.1137/1.9781611971088.
8. Banert . Sebastian. Upadhyaya . Manu. Giselsson . Pontus . 2023 . The Chambolle-Pock method converges weakly with \theta > 1 / 2 and \tau \sigma \lVert L \rVert ^{2} < 4 / ( 1 + 2 \theta ) . math.OC . 2309.03998 .
9. Book: Uzawa, H. . Iterative methods for concave programming . K. J. . Arrow . L. . Hurwicz . H. . Uzawa . Studies in linear and nonlinear programming . registration . Stanford University Press . 1958 .
10. Book: Pock . Thomas . Chambolle . Antonin . 2011 International Conference on Computer Vision . Diagonal preconditioning for first order primal-dual algorithms in convex optimization . https://ieeexplore.ieee.org/document/6126441 . 2011-11-06 . 1762–1769 . 10.1109/ICCV.2011.6126441. 978-1-4577-1102-2 . 17485166 .
11. Chambolle . Antonin . 2004-01-01 . An Algorithm for Total Variation Minimization and Applications . Journal of Mathematical Imaging and Vision . en . 20 . 1 . 89–97 . 10.1023/B:JMIV.0000011325.36760.1e . 1573-7683 . 207622122.