# The Riemannian Chambolle-Pock Algorithm

The Riemannian Chambolle–Pock is a generalization of the Chambolle–Pock algorithm Chambolle and Pock [CP11] It is also known as primal-dual hybrid gradient (PDHG) or primal-dual proximal splitting (PDPS) algorithm.

In order to minimize over p∈\mathcal M§ the cost function consisting of

$$$F(p) + G(Λ(p)),$$$

where $F:\mathcal M → \overline{ℝ}$, $G:\mathcal N → \overline{ℝ}$, and $Λ:\mathcal M →\mathcal N$. If the manifolds $\mathcal M$ or $\mathcal N$ are not Hadamard, it has to be considered locally, i.e. on geodesically convex sets $\mathcal C \subset \mathcal M$ and $\mathcal D \subset\mathcal N$ such that $Λ(\mathcal C) \subset \mathcal D$.

The algorithm is available in four variants: exact versus linearized (see variant) as well as with primal versus dual relaxation (see relax). For more details, see Bergmann, Herzog, Silva Louzeiro, Tenbrinck and Vidal-Núñez [BHS+21]. In the following we note the case of the exact, primal relaxed Riemannian Chambolle–Pock algorithm.

Given base points $m∈\mathcal C$, $n=Λ(m)∈\mathcal D$, initial primal and dual values $p^{(0)} ∈\mathcal C$, $ξ_n^{(0)} ∈T_n^*\mathcal N$, and primal and dual step sizes $\sigma_0$, $\tau_0$, relaxation $\theta_0$, as well as acceleration $\gamma$.

As an initialization, perform $\bar p^{(0)} \gets p^{(0)}$.

The algorithms performs the steps $k=1,…,$ (until a StoppingCriterion is fulfilled with)

1. $$$ξ^{(k+1)}_n = \operatorname{prox}_{\tau_k G_n^*}\Bigl(ξ_n^{(k)} + \tau_k \bigl(\log_n Λ (\bar p^{(k)})\bigr)^\flat\Bigr)$$$
2. $$$p^{(k+1)} = \operatorname{prox}_{\sigma_k F}\biggl(\exp_{p^{(k)}}\Bigl( \operatorname{PT}_{p^{(k)}\gets m}\bigl(-\sigma_k DΛ(m)^*[ξ_n^{(k+1)}]\bigr)^\sharp\Bigr)\biggr)$$$
3. Update
• $\theta_k = (1+2\gamma\sigma_k)^{-\frac{1}{2}}$
• $\sigma_{k+1} = \sigma_k\theta_k$
• $\tau_{k+1} = \frac{\tau_k}{\theta_k}$
4. $$$\bar p^{(k+1)} = \exp_{p^{(k+1)}}\bigl(-\theta_k \log_{p^{(k+1)}} p^{(k)}\bigr)$$$

Furthermore you can exchange the exponential map, the logarithmic map, and the parallel transport by a retraction, an inverse retraction, and a vector transport.

Finally you can also update the base points $m$ and $n$ during the iterations. This introduces a few additional vector transports. The same holds for the case $Λ(m^{(k)})\neq n^{(k)}$ at some point. All these cases are covered in the algorithm.

Manopt.ChambollePockFunction
ChambollePock(
M, N, cost, x0, ξ0, m, n, prox_F, prox_G_dual, adjoint_linear_operator;
forward_operator=missing,
linearized_forward_operator=missing,
evaluation=AllocatingEvaluation()
)

Perform the Riemannian Chambolle–Pock algorithm.

Given a cost function $\mathcal E:\mathcal M → ℝ$ of the form

$$$\mathcal E(p) = F(p) + G( Λ(p) ),$$$

where $F:\mathcal M → ℝ$, $G:\mathcal N → ℝ$, and $Λ:\mathcal M → \mathcal N$. The remaining input parameters are

• p, X primal and dual start points $x∈\mathcal M$ and $ξ∈T_n\mathcal N$
• m,n base points on $\mathcal M$ and $\mathcal N$, respectively.
• adjoint_linearized_operator the adjoint $DΛ^*$ of the linearized operator $DΛ(m): T_{m}\mathcal M → T_{Λ(m)}\mathcal N$
• prox_F, prox_G_Dual the proximal maps of $F$ and $G^\ast_n$

note that depending on the AbstractEvaluationType evaluation the last three parameters as well as the forwardoperator Λ and the linearizedforward_operatorcan be given as allocating functions(Manifolds, parameters) -> resultor as mutating functions(Manifold, result, parameters)-> result to spare allocations.

By default, this performs the exact Riemannian Chambolle Pock algorithm, see the optional parameter DΛ for their linearized variant.

For more details on the algorithm, see Bergmann et al., Found. Comput. Math., 2021.

Optional Parameters

• acceleration – (0.05)
• dual_stepsize – (1/sqrt(8)) proximal parameter of the primal prox
• evaluation (AllocatingEvaluation()) specify whether the proximal maps and operators are allocating functions(Manifolds, parameters) -> resultor given as mutating functions(Manifold, result, parameters)-> result to spare allocations.
• Λ (missing) the (forward) operator $Λ(⋅)$ (required for the :exact variant)
• linearized_forward_operator (missing) its linearization $DΛ(⋅)[⋅]$ (required for the :linearized variant)
• primal_stepsize – (1/sqrt(8)) proximal parameter of the dual prox
• relaxation – (1.)
• relax – (:primal) whether to relax the primal or dual
• variant - (:exact if Λ is missing, otherwise :linearized) variant to use. Note that this changes the arguments the forward_operator will be called.
• stopping_criterion – (stopAtIteration(100)) a StoppingCriterion
• update_primal_base – (missing) function to update m (identity by default/missing)
• update_dual_base – (missing) function to update n (identity by default/missing)
• retraction_method – (default_retraction_method(M, typeof(p))) the rectraction to use
• inverse_retraction_method - (default_inverse_retraction_method(M, typeof(p))) an inverse retraction to use.
• vector_transport_method - (default_vector_transport_method(M, typeof(p))) a vector transport to use

Output

the obtained (approximate) minimizer $p^*$, see get_solver_return for details.

source
Manopt.ChambollePock!Function
ChambollePock(M, N, cost, x0, ξ0, m, n, prox_F, prox_G_dual, adjoint_linear_operator)

Perform the Riemannian Chambolle–Pock algorithm in place of x, ξ, and potentially m, n if they are not fixed. See ChambollePock for details and optional parameters.

source

## State

Manopt.ChambollePockStateType
ChambollePockState <: AbstractPrimalDualSolverState

stores all options and variables within a linearized or exact Chambolle Pock. The following list provides the order for the constructor, where the previous iterates are initialized automatically and values with a default may be left out.

• m - base point on $\mathcal M$
• n - base point on $\mathcal N$
• p - an initial point on $x^{(0)} ∈\mathcal M$ (and its previous iterate)
• X - an initial tangent vector $X^{(0)}∈T^*\mathcal N$ (and its previous iterate)
• pbar - the relaxed iterate used in the next dual update step (when using :primal relaxation)
• Xbar - the relaxed iterate used in the next primal update step (when using :dual relaxation)
• primal_stepsize – (1/sqrt(8)) proximal parameter of the primal prox
• dual_stepsize – (1/sqrt(8)) proximal parameter of the dual prox
• acceleration – (0.) acceleration factor due to Chambolle & Pock
• relaxation – (1.) relaxation in the primal relaxation step (to compute pbar)
• relax – (:primal) which variable to relax (:primal or :dual)
• stop - a StoppingCriterion
• variant – (exact) whether to perform an :exact or :linearized Chambolle-Pock
• update_primal_base ((p,o,i) -> o.m) function to update the primal base
• update_dual_base ((p,o,i) -> o.n) function to update the dual base
• retraction_method – (default_retraction_method(M, typeof(p))) the retraction to use
• inverse_retraction_method - (default_inverse_retraction_method(M, typeof(p))) an inverse retraction to use on the manifold $\mathcal M$.
• inverse_retraction_method_dual - (default_inverse_retraction_method(N, typeof(n))) an inverse retraction to use on manifold $\mathcal N$.
• vector_transport_method - (default_vector_transport_method(M, typeof(p))) a vector transport to use on the manifold $\mathcal M$.
• vector_transport_method_dual - (default_vector_transport_method(N, typeof(n))) a vector transport to use on manifold $\mathcal N$.

where for the last two the functions a AbstractManoptProblemp, AbstractManoptSolverStateo and the current iterate i are the arguments. If you activate these to be different from the default identity, you have to provide p.Λ for the algorithm to work (which might be missing in the linearized case).

Constructor

ChambollePockState(M::AbstractManifold, N::AbstractManifold,
m::P, n::Q, p::P, X::T, primal_stepsize::Float64, dual_stepsize::Float64;
kwargs...
)

where all other fields from above are keyword arguments with their default values given in brackets.

if Manifolds.jl is loaded, N is also a keyword argument and set to TangentBundle(M) by default.

source

## Useful Terms

Manopt.primal_residualFunction
primal_residual(p, o, x_old, X_old, n_old)

Compute the primal residual at current iterate $k$ given the necessary values $x_{k-1}, X_{k-1}$, and $n_{k-1}$ from the previous iterate.

$$$\Bigl\lVert \frac{1}{σ}\operatorname{retr}^{-1}_{x_{k}}x_{k-1} - V_{x_k\gets m_k}\bigl(DΛ^*(m_k)\bigl[V_{n_k\gets n_{k-1}}X_{k-1} - X_k \bigr] \Bigr\rVert$$$

where $V_{⋅\gets⋅}$ is the vector transport used in the ChambollePockState

source
Manopt.dual_residualFunction
dual_residual(p, o, x_old, X_old, n_old)

Compute the dual residual at current iterate $k$ given the necessary values $x_{k-1}, X_{k-1}$, and $n_{k-1}$ from the previous iterate. The formula is slightly different depending on the o.variant used:

For the :lineaized it reads

$$$\Bigl\lVert \frac{1}{τ}\bigl( V_{n_{k}\gets n_{k-1}}(X_{k-1}) - X_k \bigr) - DΛ(m_k)\bigl[ V_{m_k\gets x_k}\operatorname{retr}^{-1}_{x_{k}}x_{k-1} \bigr] \Bigr\rVert$$$

and for the :exact variant

$$$\Bigl\lVert \frac{1}{τ} V_{n_{k}\gets n_{k-1}}(X_{k-1}) - \operatorname{retr}^{-1}_{n_{k}}\bigl( Λ(\operatorname{retr}_{m_{k}}(V_{m_k\gets x_k}\operatorname{retr}^{-1}_{x_{k}}x_{k-1})) \bigr) \Bigr\rVert$$$

where in both cases $V_{⋅\gets⋅}$ is the vector transport used in the ChambollePockState.

source

## Debug

Manopt.DebugDualResidualType
DebugDualResidual <: DebugAction

A Debug action to print the dual residual. The constructor accepts a printing function and some (shared) storage, which should at least record :Iterate, :X and :n.

Constructor

DebugDualResidual()

with the keywords

• io (stdout) - stream to perform the debug to
• format ("$prefix%s") format to print the dual residual, using the • prefix ("Dual Residual: ") short form to just set the prefix • storage (a new StoreStateAction) to store values for the debug. source Manopt.DebugPrimalResidualType DebugPrimalResidual <: DebugAction A Debug action to print the primal residual. The constructor accepts a printing function and some (shared) storage, which should at least record :Iterate, :X and :n. Constructor DebugPrimalResidual() with the keywords • io (stdout) - stream to perform the debug to • format ("$prefix%s") format to print the dual residual, using the
• prefix ("Primal Residual: ") short form to just set the prefix
• storage (a new StoreStateAction) to store values for the debug.
source
Manopt.DebugPrimalDualResidualType
DebugPrimalDualResidual <: DebugAction

A Debug action to print the primaldual residual. The constructor accepts a printing function and some (shared) storage, which should at least record :Iterate, :X and :n.

Constructor

DebugPrimalDualResidual()

with the keywords

• io (stdout) - stream to perform the debug to
source

## Literature

[BHS+21]
R. Bergmann, R. Herzog, M. Silva Louzeiro, D. Tenbrinck and J. Vidal-Núñez. Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds. Foundations of Computational Mathematics 21, 1465–1504 (2021), arXiv: [1908.02022](http://arxiv.org/abs/1908.02022).
[CP11]
A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40, 120–145 (2011).