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 In order to minimize a cost function consisting of

\[F(p) + G(Λ(p)),\]

over $p∈\mathcal M$

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 only, that is 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 description is 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 AbstractEvaluationTypeevaluation the last three parameters as well as the forward operator Λ and the linearized_forward_operator can be given as allocating functions (Manifolds, parameters) -> result or as mutating functions (Manifold, result, parameters) -> result` to spare allocations.

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

For more details on the algorithm, see [BHS+21].

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
  • Λ: (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.) the relaxation parameter $γ$
  • 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 is called with.
  • stopping_criterion: ([StopAfterIteration](@ref)(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 retraction 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 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 :linearized 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.DebugDualChangeType
DebugDualChange(opts...)

Print the change of the dual variable, similar to DebugChange, see their constructors for detail, but with a different calculation of the change, since the dual variable lives in (possibly different) tangent spaces.

source
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 primal dual 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
  • 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

Record

Manopt.RecordDualChangeFunction
RecordDualChange()

Create the action either with a given (shared) Storage, which can be set to the values Tuple, if that is provided).

source

Internals

Manopt.update_prox_parameters!Function
update_prox_parameters!(o)

update the prox parameters as described in Algorithm 2 of [CP11],

  1. $θ_{n} = \frac{1}{\sqrt{1+2γτ_n}}$
  2. $τ_{n+1} = θ_nτ_n$
  3. $σ_{n+1} = \frac{σ_n}{θ_n}$
source

Technical details

The ChambollePock solver requires the following functions of a manifold to be available for both the manifold $\mathcal M$and $\mathcal N$

  • A retract!(M, q, p, X); it is recommended to set the default_retraction_method to a favourite retraction. If this default is set, a retraction_method= or retraction_method_dual= (for $\mathcal N$) does not have to be specified.
  • An inverse_retract!(M, X, p, q); it is recommended to set the default_inverse_retraction_method to a favourite retraction. If this default is set, a inverse_retraction_method= or inverse_retraction_method_dual= (for $\mathcal N$) does not have to be specified.
  • A vector_transport_to!M, Y, p, X, q); it is recommended to set the default_vector_transport_method to a favourite retraction. If this default is set, a vector_transport_method= or vector_transport_method_dual= (for $\mathcal N$) does not have to be specified.
  • A `copyto!(M, q, p) and copy(M,p) for points.

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.
[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).