$\DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator{\Exp}{Exp} \newcommand{\geo}{\gamma_{\overset{\frown}{#1,#2}}} \newcommand{\geoS}{\gamma} \newcommand{\geoD}{\gamma_} \newcommand{\geoL}{\gamma(#2; #1)} \newcommand{\gradM}{\nabla_{\M}} \newcommand{\gradMComp}{\nabla_{\M,#1}} \newcommand{\Grid}{\mathcal G} \DeclareMathOperator{\Log}{Log} \newcommand{\M}{\mathcal M} \newcommand{\N}{\mathcal N} \newcommand{\mat}{\mathbf{#1}} \DeclareMathOperator{\prox}{prox} \newcommand{\PT}{\mathrm{PT}_{#1\to#2}#3} \newcommand{\R}{\mathbb R} \newcommand{\SPD}{\mathcal{P}(#1)} \DeclareMathOperator{\Tr}{Tr} \newcommand{\tT}{\mathrm{T}} \newcommand{\vect}{\mathbf{#1}}$

# The proximal map of an absolute second order difference

Proximal map $\prox_{\lambda f}$ for the function $f\colon\M^3\to\R,\quad f(x,y,z) = d_2(x,y,z) = d_{\M}(\geo{x}{z}(\tfrac{1}{2}),y)$, where the geodesic is the one closest to $y$. Following  we can compute the gradient of $f$. Let $c=\geo{x}{z}(\tfrac{1}{2})$ denote the mid point of a geodesic, such that the distance $d_\M(y,c)$ is minimal among all geodesics connecting $x$ and $z$. Then, using the adjoint Differential of the start point of a geodesic denoted by $J_{x,y}^*(t,\eta)$ the gradint is given by

An illustration is given by the following figure. Illustration of the gradient $\gradM f$ (light blue) at $x,y,z$ and the result of a gradient step (violet).

The proximal map is computed approximately using a subgradient descent, where both the step size as well as the stopping criterion are optional parameters of this function.

If one of the three values is NaN it can be set to the minimizer of $f$ using the geodesic of the remaining ones, e.g. $x=\geo{z}{y}(2)$ or $y=\geo{x}{z}(\tfrac{1}{2})$.

### Matlab Documentation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
% proxAbsoluteSecondOrderDifference(M,f1,f2,f3,lambda) prox d2(f1,f2,f3)
% Compute the proximal map of a second order difference (mid point model)
% by a subgradient descent. This formula was derived in
%
% R. Bergmann, M. Bacak, G. Steidl, A. Weinmann,
%     A second order non-smooth variational model for restoring
%     manifold-valued images,
%     SIAM Journal on Scientific Computing, 38, (1), A567?A597, 2016.
%
% INPUT
%   M        : a manifold
%   f1,f2,f3 : three point(sets)
%   lambda   : prox paramater
%
% OPTIONAL
%    stepSize : (@(x,eta,iter,old_step) 1/iter) a functional determining
%               the step size of the subgradient algorithm.
%    stopCrit : (stopCritMaxIterEpsilonCreator(M,3,10^(-9))) a stopping
%               criterion functional ( @(x,xold,lambda,iter) )
% ---
% Manifold-valued Image Restoration Toolbox 1.0
% R. Bergmann ~ 2015-04-22 | 2018-03-08