ChambollePock

Chambolle–Pock, named after Antonin Chambolle and Thomas Pock, refers to a first-order primal-dual algorithm for convex optimization. Introduced to solve problems of the form min_x F(Kx) + G(x), where F and G are proper convex lower semicontinuous functions and K is a linear operator, the method is widely used in image processing and related fields for its efficiency on large-scale, non-smooth problems.

The algorithm is a saddle-point method that alternates updates to primal and dual variables using proximal operators. A common, canonical form of the iterations is:

p^{k+1} = prox_{sigma F^*}(p^k + sigma K x^k)

x^{k+1} = prox_{tau G}(x^k - tau K^T p^{k+1})

with optional over-relaxation bar{x}^{k+1} = x^{k+1} + theta (x^{k+1} - x^k). Convergence is guaranteed for step sizes sigma and tau that satisfy tau sigma ||K||^2 < 1, where F^* denotes the convex conjugate of F.

The Chambolle–Pock framework is known for its simplicity and versatility, requiring only first-order information and proximal computations. It can handle a broad class of convex, possibly non-smooth objectives, including total variation regularization, l1-norm penalties, and indicator functions of convex sets. In practice, the method is favored for tasks such as denoising, deconvolution, and reconstructive imaging, as well as other large-scale inverse problems.

Variants and extensions include adaptive step sizes, preconditioning, and accelerated schemes, all aimed at improving convergence speed on specific problem structures. The algorithm is closely related to and often referenced as the primal-dual hybrid gradient (PDHG) method.