The Riemannian Chambolle-Pock Algorithm

The Riemannian Chambolle–Pock is a generalization of the Chambolle–Pock algorithm^{[ChambollePock2011]}. 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 ^{[BergmannHerzogSilvaLouzeiroTenbrinckVidalNunez2020]}. 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)

\[ξ^{(k+1)}_n = \operatorname{prox}_{\tau_k G_n^*}\Bigl(ξ_n^{(k)} + \tau_k \bigl(\log_n Λ (\bar p^{(k)})\bigr)^\flat\Bigr)\]
\[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)\]
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}$
\[\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.ChambollePock — Function

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(x) = F(x) + G( Λ(x) ),\]

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

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^{[BergmannHerzogSilvaLouzeiroTenbrinckVidalNunez2020]}.

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)) the rectraction to use
inverse_retraction_method - (default_inverse_retraction_method(M)) an inverse retraction to use.
vector_transport_method - (default_vector_transport_method(M)) a vector transport to use

Output

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

The Riemannian Chambolle-Pock Algorithm

Problem & Options

Useful Terms

Debug

Record

Internals