# Convergence of Proximal Splitting Algorithms in CAT($\kappa$) Spaces and
Beyond

Florian Lauster Institute for Numerical and Applied Mathematics, University of
Göttingen. FL was supported by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) – Project-ID LU 1702/1-1<EMAIL_ADDRESS>goettingen.de D. Russell Luke Institute for Numerical and Applied Mathematics,
University of Goettingen, 37083 Goettingen, Germany. DRL was supported in part
by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) –
Project-ID 432680300 – SFB 1456<EMAIL_ADDRESS>
###### Abstract

In the setting of CAT($\kappa$) spaces, common fixed point iterations built
from prox mappings (e.g. prox-prox, Krasnoselsky-Mann relaxations, nonlinear
projected-gradients) converge locally linearly under the assumption of linear
metric subregularity. Linear metric subregularity is in any case necessary for
linearly convergent fixed point sequences, so the result is tight. To show
this, we develop a theory of fixed point mappings that violate the usual
assumptions of nonexpansiveness and firm nonexpansiveness in $p$-uniformly
convex spaces.

2010 Mathematics Subject Classification: Primary 47H09, 47H10, 53C22, 53C21

Secondary 53C23, 53C20, 49M27

Keywords: Averaged mappings, p-uniformly convex, CAT(k) space, nonexpansive
mappings, firmly nonexpansive, fixed point iteration, proximal point algorithm

##  1 Fundamentals of Nonlinear Spaces

Following [1] we focus on $p$-uniformly convex spaces with parameter $c$ [12]:
for $p\in(1,\infty)$, a metric space $(G,d)$ is $p$-uniformly convex with
constant $c>0$ whenever it is a geodesic space, and

$(\forall t\in[0,1])(\forall x,y,z\in G)\quad d(z,(1-t)x\oplus
ty)^{p}\leq(1-t)d(z,x)^{p}+td(z,y)^{p}-\tfrac{c}{2}t(1-t)d(x,y)^{p}.$ (1)

Examples of $p$-uniformly convex spaces are $L^{p}$ spaces, CAT(0) spaces
($p=c=2$), Hadamard spaces (complete CAT$(0)$ spaces), Hilbert spaces (linear
Hadamard spaces). Of particular interest are CAT($\kappa$) spaces since these
serve as the model space for applications on manifolds with curvature bounded
above.

######  Lemma 1 ([13], Proposition 3.1).

A CAT$(\kappa)$ space is locally $2$-uniformly convex with parameter
$c\nearrow 2$ as the diameter of the local neighborhood vanishes. In
particular, for any CAT$(\kappa)$ space $(G,d)$ and any point $\overline{x}\in
G$, for all $\delta\in(0,\pi/(4\sqrt{\kappa}))$ the subspace
$(\mathbb{B}_{\delta}(\overline{x}),\left.d\right|_{\mathbb{B}_{\delta}(\overline{x})})$
is a $2$-uniformly convex space with constant
$c_{\delta}=4\delta\sqrt{\kappa}\tan\left(\pi/2-2\delta\sqrt{\kappa}\right)$.

Note the asymptotic behavior of the constants: as $\delta\searrow 0$, the
constant $c\nearrow 2$.

######  Definition 2.

Let $(G,d)$ be a geodesic space and $\gamma$ and $\eta$ be two geodesics
through $p$. Then $\gamma$ is said to be perpendicular to $\eta$ at point $p$
denoted by $\gamma\perp_{p}\eta$ if

$\displaystyle d(x,p)\leq d(x,y)\quad\forall x\in\gamma,y\in\eta$

A space is said to be symmetric perpendicular if for all geodesics $\gamma$
and $\eta$ with common point $p$ we have

$\displaystyle\gamma\perp_{p}\eta\Leftrightarrow\eta\perp_{p}\gamma.$

######  Remark 3.

Any $CAT(\kappa)$ space $(G,d)$ with $diam(G)<\frac{\pi}{2\sqrt{\kappa}}$ is
symmetric perpendicular [9, Theorem 2.11].

In a complete $p$-uniformly convex space the $p$-proximal mapping of a proper
and lower semicontinuous function $f$ is defined by

$\displaystyle\operatorname{prox}^{p}_{f,\lambda}(x)\coloneqq\operatorname{argmin\,}_{y\in
G}f(y)+\frac{1}{p\lambda^{p-1}}d(y,x)^{p}\quad(\lambda>0).$ (2)

The main dividend of this work is the following.

######  Theorem 4 (convergence of proximal algorithms in CAT($\kappa$)
spaces).

Let $(G,d)$ be a $CAT(\kappa)$ space with $\kappa>0$ and for $j=1,2,\dots,N$,
let $f_{j}$ and $g\colon G\rightarrow\mathbb{R}\cap\\{+\infty\\}$ be proper,
convex and lower semicontinuous. Let $T:\,D\to D\,$ where $D\subset G$ denote
one of the following:

  1. (i)

$T:=\operatorname{prox}_{f_{N},\lambda_{N}}\circ\operatorname{prox}_{f_{N-1},\lambda_{N-1}}\circ\dots\circ\operatorname{prox}_{f_{1},\lambda_{1}}$;

  2. (ii)

$T:=\beta\operatorname{prox}_{g,\lambda}\oplus(1-\beta)\operatorname{Id}$;

  3. (iii)

$T:=\operatorname{prox}_{f_{1},\lambda_{1}}\circ\left(\beta\operatorname{prox}_{g,\lambda_{2}}\oplus(1-\beta)\operatorname{Id}\right)$;

  4. (iv)

$T:=P_{C}\circ\left(\beta\operatorname{prox}_{g,\lambda_{1}}\oplus(1-\beta)\operatorname{Id}\right)$,

where in the last case $P_{C}$ is the metric projector onto the closed convex
set $C$. If $T$ satisfies $\operatorname{Fix}T\neq\emptyset$ and

$d(x,\operatorname{Fix}T\cap D)\leq\mu d(x,Tx),\hskip 5.69046pt\forall x\in
D\subset G,$

with constant $\mu$, then the fixed point sequence initialized from any
starting point close enough to $\operatorname{Fix}T$ is at least linearly
convergent to a point in $\operatorname{Fix}T$.

A more precise statement of this theorem, with proof, is Theorem 25. The
intervening sections prove the fundamental building blocks.

##  2 Almost $\alpha$-firmly Nonexpansive Mappings

The regularity of a mapping $T:\,G\to G\,$ is characterized by the behavior of
the images of pairs of points under $T$. A key tool is what has been called
the transport discrepancy in [4]:

$\quad\psi^{(p,c)}_{T}(x,y)\coloneqq\tfrac{c}{2}\left(d(Tx,x)^{p}+d(Ty,y)^{p}+d(Tx,Ty)^{p}+d(x,y)^{p}-d(Tx,y)^{p}-d(x,Ty)^{p}\right).$
(3)

######  Definition 5.

Let $(G,d)$ be a $p$-uniformly convex metric space with constant $c$.

  1. (i)

The mapping $T:G\to G$ is pointwise almost nonexpansive at $y\in D\subset G$
on $D$ with violation $\epsilon>0$ whenever

$\exists\alpha\in(0,1),\epsilon\geq 0:\quad
d(Tx,Ty)^{p}\leq(1+\epsilon)d(x,y)^{p}\quad\forall x\in D.$ (4)

The smallest $\epsilon$ for which (7) holds is called the violation. If (4)
holds with $\epsilon=0$, then $T$ is pointwise nonexpansive at $y\in D\subset
G$ on $D$. If (4) holds at all $y\in D$ then $T$ is said to be (almost)
nonexpansive on $D$. If $D=G$ the mapping $T$ is simply said to be (almost)
nonexpansive. If $D\supset\operatorname{Fix}T\neq\emptyset$ and (4) holds at
all $y\in\operatorname{Fix}T$ with the same violation, then $T$ is said to be
almost quasi nonexpansive.

  2. (ii)

The mapping $T$ is said to be pointwise asymptotically nonexpansive at $y$
whenever

$\forall\epsilon>0,\exists D_{\epsilon}(y)\subset G:\quad
d(Tx,Ty)^{p}\leq(1+\epsilon)d(x,y)^{p}\quad\forall x\in D_{\epsilon}(y),$ (5)

where $D_{\epsilon}(y)$ is a neighborhood of $y$ in $D$.

  3. (iii)

$T:\,G\to G\,$ is said to be quasi strictly nonexpansive whenever

$d(Tx,\overline{x})<d(x,\bar{x})\quad\forall x\in
G,\forall\overline{x}\in\operatorname{Fix}T.$ (6)

  4. (iv)

The operator $T:G\to G$ is pointwise almost $\alpha$-firmly nonexpansive at
$y\in D\subset G$ on $D$ with violation $\epsilon>0$ whenever

$\exists\alpha\in(0,1),\epsilon\geq 0:\quad
d(Tx,Ty)^{p}\leq(1+\epsilon)d(x,y)^{p}-\tfrac{1-\alpha}{\alpha}\psi^{(p,c)}_{T}(x,y)\quad$
(7)

If (7) holds with $\epsilon=0$, then $T$ is pointwise $\alpha$-firmly
nonexpansive at $y\in D\subset G$ on $D$. If (7) holds at all $y\in D$ with
the same constant $\alpha$, then $T$ is said to be (almost) $\alpha$-firmly
nonexpansive on $D$. If $D=G$ the mapping $T$ is simply said to be (almost)
$\alpha$-firmly nonexpansive. If $D\supset\operatorname{Fix}T\neq\emptyset$
and (7) holds at all $y\in\operatorname{Fix}T$ with the same constant $\alpha$
then $T$ is said to be almost quasi $\alpha$-firmly nonexpansive.

  5. (v)

The mapping $T$ is said to be pointwise asymptotically $\alpha$-firmly
nonexpansive at $y$ with constant $\alpha<1$ whenever

$\forall\epsilon>0,~{}\exists D_{\epsilon}(y)\subset G:\quad
d(Tx,Ty)^{p}\leq(1+\epsilon)d(x,y)^{p}-\tfrac{1-\alpha}{\alpha}\psi^{(p,c)}_{T}(x,y)\quad\forall
x\in D_{\epsilon}(y).$ (8)

where $D_{\epsilon}(y)$ is a neighborhood of $y$ in $D$.

######  Proposition 6 (characterizations).

Let $(G,d)$ be a p-uniformly convex space with constant $c>0$ and let $T:D\to
G$ for $D\subset G$.

  1. (i)

$\psi_{T}^{(p,c)}(x,y)=\tfrac{c}{2}d(Tx,x)^{p}\quad\mbox{whenever
}y\in\operatorname{Fix}T.$ (9)

For fixed $y\in\operatorname{Fix}T$ the function $\psi_{T}^{(p,c)}(x,y)\geq 0$
for all $x\in D$ and $\psi_{T}^{(p,c)}(x,y)=0$ only when
$x\in\operatorname{Fix}T$.

  2. (ii)

Let $y\in\operatorname{Fix}T$. $T$ is pointwise almost $\alpha$-firmly
nonexpansive at $y$ on $D$ with violation $\epsilon>0$ if and only if

$\exists\alpha\in[0,1):\quad
d(Tx,y)^{p}\leq(1+\epsilon)d(x,y)^{p}-\tfrac{1-\alpha}{\alpha}\tfrac{c}{2}d(Tx,x)^{p}\quad\forall
x\in D.$ (10)

In particular, $T$ is almost quasi $\alpha$-firmly nonexpansive on $D$
whenever $T$ possesses fixed points and (10) holds at all
$y\in\operatorname{Fix}T$ with the same constant $\alpha\in[0,1)$ and
violation $\epsilon$.

  3. (iii)

If $T$ is pointwise almost $\alpha$-firmly nonexpansive at
$y\in\operatorname{Fix}T$ on $D$ with constant $\underline{\alpha}\in[0,1)$
and violation $\epsilon$, then it is pointwise almost $\alpha$-firmly
nonexpansive at $y$ with the same violation on $D$ for all
$\alpha\in[\underline{\alpha},1]$. In particular, if $T$ is pointwise almost
$\alpha$-firmly nonexpansive at $y\in\operatorname{Fix}T$ on D, then it is
pointwise almost nonexpansive at $y$ with violation $\epsilon$ on D.

###### Proof.

This is a slight extension of [4, Proposition 4], which was for pointwise
$\alpha$-firmly nonexpansive mappings. The proof for pointwise almost
$\alpha$-firmly nonexpansive mappings is the same. ∎

###  2.1 Composition of Operators

Before continuing with pointwise almost $\alpha$-firmly nonexpansive mappings,
we make a brief but important observation about fixed points of compositions
of quasi strictly nonexpansive mappings (6).

######  Lemma 7.

Let $T_{1}$ and $T_{2}$ be quasi strictly nonexpansive on $(G,d)$ with
$\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}\neq\emptyset$. Then
$\operatorname{Fix}T_{1}\circ
T_{2}=\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}$.

###### Proof.

The inclusion
$\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}\subset\operatorname{Fix}\left(T_{1}\circ
T_{2}\right)$ is clear. Assume there exists a
$y\in\operatorname{Fix}(T_{1}\circ
T_{2})\setminus(\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2})$ and
choose $x\in\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}$. Then

$d(y,x)\leq d(T_{1}\circ T_{2}y,x)\leq d(T_{2}y,x)\leq d(y,x)$

with either $d(T_{2}y,x)<d(y,x)$ or $d(T_{1}\circ T_{2}y,x)<d(T_{2}y,x)$ as
$y\notin\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}$. This is a
contradiction, so $\operatorname{Fix}T_{1}\circ
T_{2}=\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}$. ∎

######  Remark 8.

The sufficiency of strict quasi-nonexpansivity for the analogous identity for
convex combinations of mappings in a Hadamard space was recognized in [3,
Remark 7.11].

######  Lemma 9.

Let $(G,d)$ be a $p$-uniformly convex space with constant $c>0$ and let
$D\subset G$. Let ${T_{0}}:D\to G$ be pointwise almost $\alpha$-firmly
nonexpansive at $y$ on $D$ with constant $\alpha_{0}$ and violation
$\epsilon_{0}$ and let ${T_{1}}:{T_{0}}(D)\to G$ be pointwise almost
$\alpha$-firmly nonexpansive at ${T_{0}}y$ on ${T_{0}}(D)$ with constant
$\alpha_{1}$ and violation $\epsilon_{1}$. Then the composition
$\overline{T}:={T_{1}}\circ{T_{0}}$ is pointwise almost $\alpha$-firmly
nonexpansive at $y$ with constant $\overline{\alpha}\in(0,1)$ and violation
${\overline{\epsilon}}=\epsilon_{0}+\epsilon_{1}+\epsilon_{0}\epsilon_{1}$ on
$D$ whenever

$\frac{1-\overline{\alpha}}{\overline{\alpha}}\psi^{(p,c)}_{\overline{T}}(x,y)\leq(1+\epsilon_{1})\frac{1-\alpha_{0}}{\alpha_{0}}\psi^{(p,c)}_{{T_{0}}}(x,y)+\frac{1-\alpha_{1}}{\alpha_{1}}\psi^{(p,c)}_{{T_{1}}}({T_{0}}x,{T_{0}}y)\quad\forall
x\in D.$ (11)

###### Proof.

The proof is a slight extension of the same result for compositions of
$\alpha$-firmly nonexpansive mappings in [4, Lemma 10]. Since ${T_{1}}$ is
pointwise $\alpha$-firmly nonexpansive at ${T_{0}}y$ with violation
$\epsilon_{1}$ and constant $\alpha_{1}$ on ${T_{0}}(D)$ we have

$d(\overline{T}x,\overline{T}y)^{p}\leq(1+\epsilon_{1})d({T_{0}}x,{T_{0}}y)^{p}-\frac{1-\alpha_{1}}{\alpha_{1}}\psi^{(p,c)}_{{T_{1}}}({T_{0}}x,{T_{0}}y)\quad\forall
x\in D$

where $\psi^{(p,c)}_{{T_{1}}}$ is defined by (3). Since ${T_{0}}$ is
$\alpha$-firmly nonexpansive at $y$ with constant $\alpha_{0}$ with violation
$\epsilon_{0}$ on $D$ we have

$\displaystyle
d(\overline{T}x,\overline{T}y)^{p}\leq(1+\epsilon_{0})(1+\epsilon_{1})d(x,y)^{p}$
$\displaystyle-(1+\epsilon_{1})\frac{1-\alpha_{0}}{\alpha_{0}}\psi^{(p,c)}_{{T_{0}}}(x,y)-\frac{1-\alpha_{1}}{\alpha_{1}}\psi^{(p,c)}_{{T_{1}}}({T_{0}}x,{T_{0}}y),$

for all $x\in D$. Whenever (11) holds, we conclude that

$\displaystyle\exists~{}\overline{\alpha}\in(0,1):\quad
d(\overline{T}x,\overline{T}y)^{p}\leq(1+{\overline{\epsilon}})d(x,y)^{p}-\frac{1-\overline{\alpha}}{\overline{\alpha}}\psi^{(p,c)}_{\overline{T}}(x,y)\quad\forall
x\in D,$

where
${\overline{\epsilon}}=\epsilon_{0}+\epsilon_{1}+\epsilon_{0}\epsilon_{1}$. ∎

######  Proposition 10 (compositions of pointwise almost $\alpha$-firmly
nonexpansive mappings).

Let $(G,d)$ be a $p$-uniformly convex space with constant $c>0$ and let
$D\subset G$. Let $T_{0}:D\to G$ be pointwise almost $\alpha$-firmly
nonexpansive at $y$ on $D$ with constant $\alpha_{0}$ and violation
$\epsilon_{0}$ and let $T_{1}:T_{0}(D)\to G$ be pointwise almost
$\alpha$-firmly nonexpansive at $y$ on $T_{0}(D)$ with constant $\alpha_{1}$
and violation $\epsilon_{1}$. Let
$y\in\operatorname{Fix}T_{0}\cap\operatorname{Fix}{T_{1}}$. Then the composite
operator $\overline{T}={T_{1}}\circ T_{0}$ is pointwise almost $\alpha$-firmly
nonexpansive at $y$ on $D$ with violation
${\overline{\epsilon}}=\epsilon_{0}+\epsilon_{1}+\epsilon_{0}\epsilon_{1}$ and
constant

$\overline{\alpha}=\tfrac{\alpha_{0}+\alpha_{1}-2\alpha_{0}\alpha_{1}}{\frac{c}{2}\left(1-\alpha_{0}-\alpha_{1}+\alpha_{0}\alpha_{1}\right)+\alpha_{0}+\alpha_{1}-2\alpha_{0}\alpha_{1}}.$
(12)

###### Proof.

This is a minor extension of [4, Theorem 11]. By Lemma 9, it suffices to show
(11) at all points
$y\in\operatorname{Fix}{T_{1}}\cap\operatorname{Fix}{T_{0}}$. First, note that
$\operatorname{Fix}\overline{T}\supset\operatorname{Fix}{T_{1}}\cap\operatorname{Fix}{T_{0}}$,
so by (9) we have $\psi^{(p.c)}_{T_{0}}(x,y)=\tfrac{c}{2}d(x,{T_{0}}x)^{p}$,
$\psi^{(p.c)}_{T_{1}}({T_{0}}x,{T_{0}}y)=\tfrac{c}{2}d({T_{0}}x,\overline{T}x)^{p}$,
and $\psi^{(p.c)}_{\overline{T}}(x,y)=\tfrac{c}{2}d(x,\overline{T}x)^{p}$
whenever $y\in\operatorname{Fix}{T_{1}}\cap\operatorname{Fix}{T_{0}}$.
Inequality (11) in this case simplifies to

$\exists\overline{\kappa}>0:\quad\kappa_{0}(1+\epsilon_{1})d(x,{T_{0}}x)^{p}+\kappa_{1}d({T_{0}}x,\overline{T}x)^{p}\geq\overline{\kappa}d(x,\overline{T}x)^{p}\qquad\forall
x\in D,$ (13)

where $\kappa_{0}:=\frac{1-\alpha_{0}}{\alpha_{0}}$,
$\kappa_{T_{1}}:=\frac{1-\alpha_{1}}{\alpha_{1}}$ and
$\overline{\kappa}:=\frac{1-\overline{\alpha}}{\overline{\alpha}}$ with
$\overline{\alpha}\in(0,1)$. By (1), we have

$\displaystyle\tfrac{c}{2}t(1-t)d(x,\overline{T}x)^{p}$ $\displaystyle\leq$
$\displaystyle\tfrac{c}{2}t(1-t)d(x,\overline{T}x)^{p}+d({T_{0}}x,(1-t)x\oplus
t\overline{T}x)^{p}$ (14) $\displaystyle\leq$
$\displaystyle(1-t)d({T_{0}}x,x)^{p}+td({T_{0}}x,\overline{T}x)^{p}\quad\forall
x\in G,\forall t\in(0,1).$

Letting $t=\tfrac{\kappa_{1}}{\kappa_{0}+\kappa_{1}}$ yields
$(1-t)=\tfrac{\kappa_{0}}{\kappa_{0}+\kappa_{1}}$, so that (14) becomes

$\displaystyle\tfrac{c}{2}\tfrac{\kappa_{0}\kappa_{1}}{\kappa_{0}+\kappa_{1}}d(x,\overline{T}x)^{p}$
$\displaystyle\leq$
$\displaystyle(1+\epsilon_{1})\kappa_{0}d({T_{0}}x,x)^{p}+\kappa_{1}d({T_{0}}x,\overline{T}x)^{p}\quad\forall
x\in G.$ (15)

It follows that (13) holds for any
$\overline{\kappa}\in\left(0,\tfrac{c\kappa_{0}\kappa_{1}}{2(\kappa_{0}+\kappa_{1})}\right]$.
We conclude that the composition $\overline{T}$ is quasi $\alpha$-firmly
nonexpansive with constant

$\overline{\alpha}=\frac{\kappa_{0}+\kappa_{1}}{\frac{c}{2}\kappa_{0}\kappa_{1}+\kappa_{0}+\kappa_{1}}.$

A short calculation shows that this is the same as (12), which completes the
proof. ∎

###  2.2 Averages of Operators

Let $\mathcal{B}(G)$ be the borel algebra on $(G,d)$, $\mathcal{P}$ the family
of probability measures on $(G,\mathcal{B}(G))$ and $\mathcal{P}^{p}(G)$ the
family of probability measures on $G$ such that the $p$-th moment exists,
i.e.:

$\displaystyle\mathcal{P}^{p}(G)\coloneqq\\{\nu\in\mathcal{P}(G)\mid\int_{y}d(x,y)^{p}\nu(dx)<\infty\quad\forall
x\in G\\}.$

For $\mu\in\mathcal{P}^{p}(G)$ the minimizer of

$\displaystyle x\mapsto\int_{G}d(x,y)^{p}\nu(dy)$

is called $p$-barycenter of $\nu$ and denoted by $b_{p}(\nu)$ if it exists.
The $p$-barycenter of $\nu$ always exsists if $(G,d)$ is a proper geodesic
space and $\mu\in\mathcal{P}^{p}(G)$ [9, Proposition 3.3].

Let $T_{i}\colon G\rightarrow G,i\in I$ be a collection of mappings where $I$
is an index space. Assume that $(I,\mathcal{I})$ is a measurable space and
$(x,i)\mapsto T_{i}x$ is measurable. Let $\eta$ be a probability measure on
$I$ and define $b_{p}(T_{i},\eta)\colon G\rightarrow G$ by

$\displaystyle b_{p}(T_{i},\eta)(x)=\operatorname{argmin\,}_{y\in
G}y\mapsto\int_{I}d(T_{i}x,y)^{p}\eta(di).$

We use the notation $T_{i}x_{*}\eta$ for the push forward of $\eta$ with
respect to the mapping $i\mapsto T_{i}x$ for fixed $x$, i.e.

$\displaystyle T_{i}x_{*}\eta(A)=\eta(\\{i\mid T_{i}x\in A\\})$ (16)

for $A\in\mathcal{B}(G)$. Then by definition
$b_{p}(T_{i},\eta)(x)=b_{p}(T_{i}x_{*}\eta)$.

######  Theorem 11.

Let $G$ be a proper, symmetric perpendicular, $p$-uniformly convex space with
constant $c>0$ and let $T_{i}$, $i\in I$ be a family of almost quasi
$\alpha$-firmly nonexpansive operators with violation $\epsilon_{i}$ and
constant $\alpha_{i}$ respectively on $G$. Let $\eta$ be a probability measure
on $I$ such that $T_{i}x_{*}\eta\in\mathcal{P}^{p}(G)$ for all $x\in G$. Then
$\mathscr{T}=b_{p}(T_{i},\eta)$ is a pointwise almost $\alpha$-firm operator
at any $y\in\cap_{i\in I}\operatorname{Fix}T_{i}$ on $G$ with constant
$\overline{\alpha}=\sup_{i\in I}\alpha_{i}$ and violation
${\overline{\epsilon}}=\sup_{i\in I}\epsilon_{i}$.

###### Proof.

Let $x\in G$ be arbitrary, $y\in\cap_{i\in
I}\operatorname{Fix}T_{i}\subset\operatorname{Fix}\mathscr{T}$,
$\nu=T_{i}x_{*}\eta$ as defined in (16) and $(d(\cdot,y)^{p})_{*}\nu$ the push
forward of $\nu$ . Then

$\displaystyle
d(\mathscr{T}x,\mathscr{T}y)^{p}=d(b_{p}(T_{i}x_{*}\eta),y)^{p}=d(b_{p}(\nu),y)^{p}\leq
b_{p}((d(\cdot,y)^{p})_{*}\nu)$

by Jensens inequality [9, Theorem 4.1] since $d(\cdot,y)^{p}$ is a convex
function and the fact that $\mathbb{R}$ is a $p$-uniformly convex space with
constant $c$. Now

$\displaystyle b_{p}((d(\cdot,y)^{p})_{*}\nu)$
$\displaystyle=\operatorname{argmin\,}_{t\in\mathbb{R}}\int_{z}|t-d(z,y)^{p}|^{p}\nu(dz)$
$\displaystyle=\operatorname{argmin\,}_{t\in\mathbb{R}}\int_{i}|t-d(T_{i}x,y)^{p}|^{p}\eta(di)$
$\displaystyle\leq\operatorname{argmin\,}_{t\in\mathbb{R}}\int_{i}|t-[(1+\epsilon_{i})d(x,y)^{p}-\frac{1-\alpha_{i}}{\alpha_{i}}\frac{c}{2}d(T_{i}x,x)^{p}]|^{p}\eta(di)$
$\displaystyle\leq(1+{\overline{\epsilon}})d(x,y)^{p}-\operatorname{argmin\,}_{t\in\mathbb{R}}\int_{i}|t-\frac{1-\overline{\alpha}}{\overline{\alpha}}\frac{c}{2}d(T_{i}x,x)^{p}|^{p}\eta(di)$
$\displaystyle=(1+{\overline{\epsilon}})d(x,y)^{p}-\frac{1-\overline{\alpha}}{\overline{\alpha}}\frac{c}{2}\operatorname{argmin\,}_{t\in\mathbb{R}}\int_{z}|t-d(z,x)^{p}|^{p}\nu(dz)$
$\displaystyle=(1+{\overline{\epsilon}})d(x,y)^{p}-\frac{1-\overline{\alpha}}{\overline{\alpha}}\frac{c}{2}b_{p}((d(\cdot,y)^{p})_{*}\nu).$

And again Jensens inequality completes the proof

$\displaystyle(1+{\overline{\epsilon}})d(x,y)^{p}-b_{p}(\frac{1-\overline{\alpha}}{\overline{\alpha}}\frac{c}{2}d(x,T_{i}x)_{*}\eta)$
$\displaystyle\leq(1+{\overline{\epsilon}})d(x,y)^{p}-\frac{1-\overline{\alpha}}{\overline{\alpha}}\frac{c}{2}d(x,b_{p}(T_{i}x_{*}\eta))^{p}.$

∎

For a finite index set $I$, without loss of generality $I=\\{1,\ldots,n\\}$
and a probability measure $\eta$ on $I$ we can define
$\omega_{i}\coloneqq\eta(i)$ for all $i$. Then

$\displaystyle b_{p}(T_{i},\eta)(x)=\operatorname{argmin\,}_{z\in
G}\sum_{i=1}^{n}\omega_{i}d(z,T_{i}x)^{p}.$

In case of a Hilbert space $G$ and $p=c=2$ this reduces further to
$b_{p}(T_{i},\eta)(x)=\sum_{i=1}^{n}\omega_{i}T_{i}x$.

If the support of the measure $\nu$ consits of two disrecte points $x_{1}$ and
$x_{2}$, i.e. for $\omega\in[0,1]$
$\nu=\omega\delta_{x_{1}}+(1-\omega)\delta_{x_{2}}$, then $b_{p}(\nu)$ can be
calculated explicitly. It is obvious that $b_{p}(\nu)$ has to lie on the
geodesic connecting $x_{1}$ and $x_{2}$. Hence
$b_{p}(\nu)=\overline{t}x_{1}\oplus(1-\overline{t})x_{2}$ for some
$\overline{t}\in[0,1]$. Minimizing the function $t\mapsto\omega
d(tx_{1}\oplus(1-t)x_{2},x_{1})^{p}+(1-\omega)d(tx_{1}\oplus(1-t)x_{2},x_{1})^{p}$
leads to $\overline{t}=\frac{1}{\sqrt[p-1]{\frac{1-\omega}{\omega}}+1}$. If
$I=\\{1,2\\}$, $T_{1}=T$ and $T_{2}=Id$,
$\eta=\omega\delta_{1}(\cdot)+(1-\omega)\delta_{2}(\cdot)$ for
$\omega\in[0,1]$ then $T_{\beta}=b_{p}(T_{i},\eta)$ is Krasnoselsky-Mann
relaxation of $T$

$T_{\beta}=\beta T\oplus(1-\beta)Id\quad\text{with
}\beta=\frac{1}{\sqrt[p-1]{\frac{1-\omega}{\omega}}+1}.$

The next result shows that the convex combination of an almost nonexpansive
mapping with the identity mapping can be made arbitrarily close to
$\alpha$-firmly nonexpansive (no violation) by choosing the averaging constant
small enough – this can be interpreted as choosing an appropriately small step
size.

######  Proposition 12 (Krasnoselsky-Mann relaxations).

Let $(G,d)$ be a $p$-uniformly convex space and $T\colon G\rightarrow G$ be
pointwise almost nonexpansive at all $y\in\operatorname{Fix}T$ with violation
$\epsilon$. Then $T_{\beta}\coloneqq\beta T\oplus(1-\beta)Id$ is pointwise
almost $\alpha$-firmly nonexpansive at all $y\in\operatorname{Fix}T$ with
constant

$\alpha_{\beta}=\frac{\alpha\beta^{p-1}}{\alpha\beta^{p-1}-\alpha\beta+1}$

and violation $\epsilon_{\beta}:=\epsilon\beta$.

###### Proof.

Clearly $\operatorname{Fix}T=\operatorname{Fix}T_{\beta}$ and
$d(x,T_{\beta}x)^{p}=\beta^{p}d(x,Tx)^{p}$. Let $y\in FixT_{\beta}$ then

$\displaystyle d(y,T_{\beta}x)^{p}$ $\displaystyle=d(y,\beta
Tx\oplus(1-\beta)x)^{p}$ $\displaystyle\leq\beta
d(y,Tx)^{p}+(1-\beta)d(y,x)^{p}-\frac{c}{2}\beta(1-\beta)d(x,Tx)^{p}$
$\displaystyle\leq(1+\epsilon\beta)d(x,y)^{p}-\frac{c}{2}\beta^{1-p}\left(\tfrac{1-\alpha}{\alpha}+1-\beta\right)d(x,T_{\beta}x)^{p}.$

Setting

$\tfrac{1-\alpha_{\beta}}{\alpha_{\beta}}=\beta^{1-p}\left(\tfrac{1-\alpha}{\alpha}+1-\beta\right)$

and solving for $\alpha_{\beta}$ yields the result. ∎

###  2.3 Metric Subregularity

Recall that $\mu:[0,\infty)\to[0,\infty)$ is a gauge function if $\mu$ is
continuous, strictly increasing with $\mu(0)=0$, and
$\lim_{t\to\infty}\mu(t)=\infty$.

######  Definition 13 (metric regularity on a set).

Let $(G_{1},d_{1})$ and $(G_{2},d_{2})$ be metric spaces and let
$\Phi:\,G_{1}\rightrightarrows G_{2}\,$, $U\subset G_{1}$, $V\subset G_{2}$.
The mapping $\Phi$ is called _metrically regular with gauge $\mu$ on $U\times
V$ relative to $\Lambda\subset G_{1}$_ if

$\forall y\in V,\forall x\in
U\cap\Lambda,\quad\operatorname{dist}\left(x,\Phi^{-1}(y)\cap\Lambda\right)\leq\mu\left(\operatorname{dist}\left(y,\Phi(x)\right)\right).$
(17)

When the set $V$ consists of a single point, $V=\\{{\overline{y}}\\}$, then
$\Phi$ is said to be _metrically subregular for ${\overline{y}}$ on $U$ with
gauge $\mu$ relative to $\Lambda\subset G_{1}$_.

When $\mu$ is a linear function (that is, $\mu(t)=\kappa t,\,\forall
t\in[0,\infty)$), this special case is distinguished as linear metric
(sub)regularity with constant $\kappa$. When $\Lambda=G_{1}$, the quantifier
“relative to” is dropped. When $\mu$ is linear, the infimum of all constants
$\kappa$ for which (17) holds is called the modulus of metric regularity.

The next statement is obvious from the definition.

######  Proposition 14.

Let $(G_{1},d_{1})$ and $(G_{2},d_{2})$ be metric spaces and let
$\Phi:\,G_{1}\rightrightarrows G_{2}\,$, $U\subset G_{1}$, $V\subset G_{2}$.
If $\Phi$ is metrically subregular with gauge $\mu$ at $y$ on $U$ relative to
$\Lambda\subset G_{1}$, then $\Phi$ is metrically subregular with the same
gauge $\mu$ at $y$ on all subsets $U^{\prime}\subset U$ relative to
$\Lambda\subset G_{1}$.

##  3 Quantitative Convergence

To obtain convergence of fixed point iterations under the assumption of metric
subregularity, the gauge of metric subregularity $\mu$ is constructed
implicitly from another nonnegative function
$\theta:\,[0,\infty)\to[0,\infty)\,$ satisfying

$\displaystyle(i)~{}\theta(0)=0;\quad(ii)~{}0<\theta(t)<t~{}\forall
t>0;\quad(iii)~{}\sum_{j=1}^{\infty}\theta^{(j)}(t)<\infty~{}\forall t\geq 0.$
(18)

For a $p$-uniformly convex space the operative gauge satisfies

$\mu\left(\left(\frac{(1+\epsilon)t^{p}-\left(\theta(t)\right)^{p}}{\tau}\right)^{1/p}\right)=t\quad\iff\quad\theta(t)=\left((1+\epsilon)t^{p}-\tau\left(\mu^{-1}(t)\right)^{p}\right)^{1/p}$
(19)

for $\tau>0$ fixed and $\theta$ satisfying (18).

In the case of linear metric subregularity on a CAT($\kappa$) space this
becomes

$t\mapsto\mu
t\quad\iff\quad\theta(t)=\left((1+\epsilon)-\frac{\tau}{\mu^{2}}\right)^{1/2}t\quad(\mu\geq\sqrt{\tfrac{\tau}{(1+\epsilon)}}).$

If (17) is satisfied for some $\mu^{\prime}>0$, then the condition
$\mu\geq\sqrt{\tfrac{\tau}{(1+\epsilon)}}$ is satisfied for all
$\mu\geq\mu^{\prime}$ large enough. The conditions in (18) in this case
simplify to $\theta(t)=\gamma t$ where

$0<\gamma:=\sqrt{1+\epsilon-\frac{\tau}{\mu^{2}}}<1\quad\iff\quad\sqrt{\tfrac{\tau}{(1+\epsilon)}}\leq\mu\leq\sqrt{\tfrac{\tau}{\epsilon}}.$
(20)

The next definition characterizes the quantitative convergence of sequences in
terms of gauge functions.

######  Definition 15 (gauge monotonicity [10]).

Let $(G,d)$ be a metric space, let $(x_{k})_{k\in\mathbb{N}}$ be a sequence on
$G$, let $D\subset G$ be nonempty and let the continuous mapping
$\mu:\,\mathbb{R}_{+}\to\mathbb{R}_{+}\,$ satisfy $\mu(0)=0$ and

$\displaystyle\mu(t_{1})<\mu(t_{2})\leq t_{2}\;\mbox{ whenever }\;0\leq
t_{1}<t_{2}.$

  1. (i)

$(x_{k})_{k\in\mathbb{N}}$ is said to be _gauge monotone with respect to $D$
with rate $\mu$_ whenever

$d(x_{k+1},D)\leq\mu\left(d(x_{k},D)\right)\quad\forall k\in\mathbb{N}.$ (21)

  2. (ii)

$(x_{k})_{k\in\mathbb{N}}$ is said to be _linearly monotone with respect to
$D$_ with rate $c$ if (21) is satisfied for $\mu(t)=c\cdot t$ for all
$t\in\mathbb{R}_{+}$ and some constant $c\in[0,1]$.

A sequence $(x_{k})_{k\in\mathbb{N}}$ is said to converge gauge monotonically
to some element $x^{*}\in G$ with rate
$s_{k}(t):=\sum_{j=k}^{\infty}\mu^{(j)}(t)$ whenever it is gauge monotone with
gauge $\mu$ satisfying $\sum_{j=1}^{\infty}\mu^{(j)}(t)<\infty~{}\forall t\geq
0$, and there exists a constant $a>0$ such that $d(x_{k},x^{*})\leq as_{k}(t)$
for all $k\in\mathbb{N}$.

All Fejér monotone sequences are linearly monotone (with constant $c=1$) but
the converse does not hold (see Proposition 1 and Example 1 of [10]). Gauge-
monotonic convergence for a linear gauge in the definition above is just
$R$-linear convegence.

Metric subregularity and pointwise (almost) nonexpansiveness are fundamentally
connected through the surrogate mapping
$\mathcal{T}_{S}:\,G\to\mathbb{R}_{+}\,\cup\\{+\infty\\}$ defined by

$\mathcal{T}_{S}(x):=\left|\left(\inf_{y\in
S}\psi^{(p,c)}_{T}(x,y)\right)^{1/p}\right|$ (22)

where $\psi^{(p,c)}_{T}$ is defined by (3) and $S\subset G$. If $S=\emptyset$
then, by definition, $\mathcal{T}_{S}(x):=+\infty$ for all $x$. Hence,
$\mathcal{T}_{S}$ is proper when $S$ is nonempty. For our purposes,
$S\subseteq\operatorname{Fix}T$, in which case by Proposition 6(i) we have
$\psi^{(p,c)}_{T}(x,y)\geq 0$ for all $x\in D$ and all $y\in S$ and
$\psi^{(p,c)}_{T}(x,y)=0$ only when both $x,y\in\operatorname{Fix}T$. Hence
$\mathcal{T}_{S}$ is nonnegative, and takes the value $0$ only on
$\operatorname{Fix}T$ and has the simple representation

$\mathcal{T}_{S}(x)=\sqrt[p]{\tfrac{2}{c}}d(Tx,x)>0\quad(S\neq\emptyset).$
(23)

######  Theorem 16 (necessary and sufficient conditions for convergence
rates).

Let $(G,d)$ be a $p$-uniformly convex space with constant $c$; let $D\subset
G$, let $T:\,D\to D\,$, and let $S:=\operatorname{Fix}T\cap D$ be nonempty.
Assume further that $T$ is pointwise almost $\alpha$-firmly nonexpansive at
all points $y\in S$ with the same constant $\overline{\alpha}$ and violation
$\epsilon$ on $D$.

  1. (a)

(necessity) Suppose that all sequences $(x^{k})_{k\in\mathbb{N}}$ defined by
$x^{k+1}=Tx^{k}$ and initialized in $D$ are gauge monotone relative to $S$
with rate $\theta$ satisfying (18), and
$(\operatorname{Id}-\theta)^{-1}(\cdot)$ is continuous on $\mathbb{R}_{+}$,
strictly increasing, and $(\operatorname{Id}-\theta)^{-1}(0)=0$. Then all
sequences initialized on $D$ converge gauge monotonically to some
$\overline{x}\in S$ with rate $O(s_{k}(t_{0}))$ where
$s_{k}(t):=\sum_{j=k}^{\infty}\theta^{(j)}(t)$ and
$t_{0}:=d(x^{0},\operatorname{Fix}T\cap D)$. Moreover, $\mathcal{T}_{S}$
defined by (22) is metrically subregular for $0$ relative to $D$ on $D$ with
gauge $\mu(\cdot)=(\operatorname{Id}-\theta)^{-1}(\cdot)$.

  2. (b)

(sufficiency) If $T$ satisfies

$d(x,\operatorname{Fix}T\cap D)\leq\mu(d(x,Tx)),\hskip 5.69046pt\forall x\in
D,$ (24)

with gauge $\mu$ given by (19) for
$\tau=(1-\overline{\alpha})/\overline{\alpha}$ and $\epsilon>0$ the violation
of pointwise $\alpha$ firmness of $T$ on $D$, then for any $x^{0}\in D$, the
sequence $(x^{k})_{k\in\mathbb{N}}$ defined by $x^{k+1}=Tx^{k}$ satisfies

$d\left(x^{k+1},\operatorname{Fix}T\cap
D\right)\leq\theta\left(d\left(x^{k},\operatorname{Fix}T\cap
D\right)\right)\quad\forall k\in\mathbb{N},$ (25)

where $\theta$ given implicitly by (19) satisfies (18). Moreover, the sequence
$(x^{k})_{k\in\mathbb{N}}$ converges gauge monotonically to some
$x^{*}\in\operatorname{Fix}T\cap D$ with rate $O(s_{k}(t_{0}))$ where
$s_{k}(t):=\sum_{j=k}^{\infty}\theta^{(j)}(t)$ and
$t_{0}:=d(x^{0},\operatorname{Fix}T\cap D)$.

Before proving this theorem, we collect some intermediate results.

######  Lemma 17 (gauge monotonicity and almost quasi $\alpha$-firmness
implies convergence to fixed points).

Let $(G,d)$ be a $p$-uniformly convex space with constant $c$. Let $T:\,G\to
G\,$ with $T(D)\subseteq D\subseteq G$ for $D$ closed. Suppose that
$\operatorname{Fix}T\cap D$ is nonempty and that $T$ is pointwise almost
$\alpha$-firmly nonexpansive at all $y\in\operatorname{Fix}T\cap D$ with the
same constant $\overline{\alpha}$ and violation $\epsilon$ on $D$. If the
sequence $(x^{k})_{k\in\mathbb{N}}$ defined by $x^{k+1}=Tx^{k}$ and
initialized in $D$ is gauge monotone relative to $\operatorname{Fix}T\cap D$
with rate $\theta$ satisfying (18), then $(x^{k})_{k\in\mathbb{N}}$ converges
gauge monotonically to some $x^{*}\in\operatorname{Fix}T\cap D$ with rate
$O(s_{k}(t_{0}))$ where $s_{k}(t):=\sum_{j=k}^{\infty}\theta^{(j)}(t)$ and
$t_{0}:=d(x^{0},\operatorname{Fix}T\cap D)$.

###### Proof.

The assumption that $T$ is pointwise almost $\alpha$-firmly nonexpansive at
all $y\in\operatorname{Fix}T\cap D$ with constant $\overline{\alpha}$ and
violation $\epsilon$ on $D$ yields

$d(Tx,y)^{p}\leq(1+\epsilon)d(x,y)^{p}-\tfrac{c(1-\overline{\alpha})}{2\overline{\alpha}}d(Tx,x)^{p},\hskip
5.69046pt\forall x\in D.$

Let $x^{0}\in D$ and define the sequence $x^{k+1}=Tx^{k}$ for all
$k\in\mathbb{N}$. Since $T$ is pointwise almost $\alpha$-firmly nonexpansive
at all points in $\operatorname{Fix}T\cap D$ on $D$, $\operatorname{Fix}T\cap
D$ is closed and $P_{\operatorname{Fix}T\cap D}x^{k}$ is nonempty (though
possibly set-valued) for all $k$. Denote any selection by $\bar{x}^{k}\in
P_{\operatorname{Fix}T\cap D}x^{k}$ for each $k\in\mathbb{N}$. Then

$d(x^{k+1},\bar{x}^{k})^{p}\leq(1+\epsilon)d(x^{k},\bar{x}^{k})^{p}-\tfrac{c(1-\overline{\alpha})}{2\overline{\alpha}}d(x^{k},x^{k+1})^{p},\hskip
5.69046pt\forall k\in\mathbb{N},$

which implies that

$d(x^{k},x^{k+1})\leq\left(\tfrac{2\overline{\alpha}(1+\epsilon)}{c(1-\overline{\alpha})}\right)^{1/p}d(x^{k},\bar{x}^{k}),\hskip
5.69046pt\forall k\in\mathbb{N}.$

On the other hand $d(x^{k},\bar{x}^{k})=d(x^{k},\operatorname{Fix}T\cap
D)\leq\theta\left(d(x^{k-1},\operatorname{Fix}T\cap D)\right)$ since
$(x^{k})_{k\in\mathbb{N}}$ is gauge monotone relative to
$\operatorname{Fix}T\cap D$ with rate $\theta$. Therefore an iterative
application of gauge monotonicity yields

$d(x^{k},x^{k+1})\leq\left(\tfrac{2\overline{\alpha}(1+\epsilon)}{c(1-\overline{\alpha})}\right)^{1/p}\theta^{(k)}\left(d(x^{0},\operatorname{Fix}T\cap
D)\right),\hskip 5.69046pt\forall k\in\mathbb{N}.$

Let $t_{0}=d(x^{0},\operatorname{Fix}T\cap D)$. For any given natural numbers
$k,l$ with $k<l$ an iterative application of the triangle inequality yields
the upper estimate

$\displaystyle d(x^{k},x^{l})$ $\displaystyle\leq$ $\displaystyle
d(x^{k},x^{k+1})+d(x^{k+1},x^{k+2})+...+d(x^{l-1},x^{l})$ $\displaystyle\leq$
$\displaystyle\left(\tfrac{2\overline{\alpha}(1+\epsilon)}{c(1-\overline{\alpha})}\right)^{1/p}\left(\theta^{(k)}(t_{0})+\theta^{(k+1)}(t_{0})+\dots+\theta^{(l-1)}(t_{0})\right)$
$\displaystyle<$
$\displaystyle\left(\tfrac{2\overline{\alpha}(1+\epsilon)}{c(1-\overline{\alpha})}\right)^{1/p}s_{k}(t_{0}),$

where $s_{k}(t_{0}):=\sum_{j=k}^{\infty}\theta^{(j)}(t_{0})<\infty$ for
$\theta$ satisfying (18). Since $(\theta^{(k)}(t_{0}))_{k\in\mathbb{N}}$ is a
summable sequence of nonnegative numbers, the sequence of partial sums
$s_{k}(t_{0})$ converges to zero monotonically as $k\to\infty$ and hence
$(x^{k})_{k\in\mathbb{N}}$ is a Cauchy sequence and $x^{k}\to x^{*}$ for some
$x^{*}\in G$. Letting $l\to+\infty$ yields

$\lim_{l\to+\infty}d(x^{k},x^{l})=d(x^{k},x^{*})\leq as_{k}(t_{0}),\hskip
5.69046pta:=\left(\frac{2\overline{\alpha}(1+\epsilon)}{c(1-\overline{\alpha})}\right)^{1/p}.$

Therefore $(x^{k})_{k\in\mathbb{N}}$ converges gauge monotonically to $x^{*}$
with rate $O(s_{k}(t_{0}))$.

It remains to show that $x^{*}\in\operatorname{Fix}T\cap D$. Note that for
each $k\in\mathbb{N}$

$d(x^{k},\bar{x}^{k})=d(x^{k},\operatorname{Fix}T\cap
D)\leq\theta^{(k)}(t_{0}),$

which yields $\lim_{k}d(x^{k},\bar{x}^{k})=0$. But by the triangle inequality

$d(\bar{x}^{k},x^{*})\leq d(x^{k},\bar{x}^{k})+d(x^{k},x^{*}),$

so $\lim_{k}d(\bar{x}^{k},x^{*})=0$. By construction
$(\bar{x}^{k})_{k\in\mathbb{N}}\subseteq\operatorname{Fix}T\cap D$ and
$\operatorname{Fix}T\cap D$ is closed, hence $x^{*}\in\operatorname{Fix}T\cap
D$. ∎

######  Proposition 18 ([4], Theorem 32).

Let $(G,d)$ be a $p$-uniformly convex metric space with constant $c$. Let
$T:D\to D$ with $D\subseteq G$. Suppose that $S:=\operatorname{Fix}T\cap D$ is
nonempty. Suppose all sequences $(x^{k})_{k\in\mathbb{N}}$ defined by
$x^{k+1}=Tx^{k}$ and initialized in $D$ are gauge monotone relative to $S$
with rate $\theta$ satisfying (18). Suppose, in addition, that
$(\operatorname{Id}-\theta)^{-1}(\cdot)$ is continuous on $\mathbb{R}_{+}$,
strictly increasing, and $(\operatorname{Id}-\theta)^{-1}(0)=0$. Then
$\mathcal{T}_{S}$ defined by (22) is metrically subregular for $0$ relative to
$D$ on $D$ with gauge $\mu(\cdot)=(\operatorname{Id}-\theta)^{-1}(\cdot)$.

Proof of Theorem 16.  Part (a). This follows immediately from Lemma 17 and
Proposition 18.

Part (b). Our pattern of proof follows the same logic as the analogous result
for set-valued mappings in a Euclidean space setting [11, Theorem 2.2]. Since
$S=\operatorname{Fix}T\cap D$, Proposition 6(i) establishes that
$\psi(x,y)=\frac{c}{2}d(x,Tx)^{p}$ for all $y\in\operatorname{Fix}T$, so
$\mathcal{T}_{S}(x)=\frac{c}{2}d(x,Tx)$. Also by Proposition 6(i)
$\mathcal{T}_{S}$ takes the value $0$ only on $\operatorname{Fix}T$, that is,
$\mathcal{T}_{S}^{-1}(0)=\operatorname{Fix}{T}$. So by assumption that
$\mathcal{T}_{S}$ satisfies (24) with gauge $\mu$ given by (19) for
$\tau=(1-\overline{\alpha})/\overline{\alpha}$, together with the definition
of metric subregularity (Definition 13) this yields

$\displaystyle d(x,\operatorname{Fix}T\cap D)$ $\displaystyle=$ $\displaystyle
d(x,\mathcal{T}_{S}^{-1}(0)\cap D)$ $\displaystyle\leq$
$\displaystyle\mu\left(\mathcal{T}_{S}(x)\right)=\mu(d(x,Tx))\quad\forall x\in
D.$

In other words,

$\tfrac{1-\overline{\alpha}}{\overline{\alpha}}\left(\mu^{-1}\left(d(x,\operatorname{Fix}T\cap
D)\right)\right)^{p}\leq\tfrac{1-\overline{\alpha}}{\overline{\alpha}}d(x,Tx)^{p}\quad\forall
x\in D.$ (26)

On the other hand, by the assumption that $T$ is pointwise almost
$\alpha$-firmly nonexpansive at all points $y\in S$ with the same constant
$\overline{\alpha}$ and violation $\epsilon$ on $D$ we have

$\displaystyle 0$ $\displaystyle\leq$
$\displaystyle\tfrac{1-\overline{\alpha}}{\overline{\alpha}}d(x,Tx)^{p}$ (27)
$\displaystyle\leq$
$\displaystyle(1+\epsilon)d(x,y)^{p}-d(Tx,y)^{p}\quad\forall
y\in\operatorname{Fix}T\cap D,\forall x\in D.$

Incorporating (26) into (27) and rearranging the inequality yields

$\displaystyle d(Tx,y)^{p}\\!$ $\displaystyle\leq$
$\displaystyle\\!(1+\epsilon)d(x,y)^{p}-\tfrac{1-\overline{\alpha}}{\overline{\alpha}}\left(\mu^{-1}\left(d(x,\operatorname{Fix}T\cap
D)\right)\right)^{p}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\forall
y\in\operatorname{Fix}T\cap D,\forall x\in D.$

Since this holds at any $x\in D$, it certainly holds at the iterates $x^{k}$
with initial point $x^{0}\in D$ since $T$ is a self-mapping on $D$. Therefore
for all $k\in\mathbb{N}$

$d(x^{k+1},y)\leq\sqrt[p]{(1+\epsilon)d(x^{k},y)^{p}-\frac{1-\overline{\alpha}}{\overline{\alpha}}\left(\mu^{-1}\left(d\left(x^{k},\,\operatorname{Fix}T\cap
D\right)\right)\right)^{p}}\quad\forall y\in\operatorname{Fix}T\cap D.$ (28)

Equation (28) simplifies. Indeed $\operatorname{Fix}T\cap D$ is closed, so for
every $k\in\mathbb{N}$ the distance $d(x^{k},\operatorname{Fix}T\cap D)$ is
attained at some $y^{k}\in\operatorname{Fix}T\cap D$ yielding

$d(x^{k+1},y^{k+1})^{p}\leq
d(x^{k+1},y^{k})^{p}\leq(1+\epsilon)d(x^{k},y^{k})^{p}-\tfrac{1-\overline{\alpha}}{\overline{\alpha}}\left(\mu^{-1}\left(d(x^{k},y^{k})\right)\right)^{p}\quad\forall
k\in\mathbb{N}.$ (29)

Taking the $p$th root and recalling (19) yields (25).

This establishes also that the sequence $(x^{k})_{k\in\mathbb{N}}$ is gauge
monotone relative to $\operatorname{Fix}T\cap D$ with rate $\theta$ satisfying
Eq.(18). By Lemma 17 it follows that the sequence $(x^{k})_{k\in\mathbb{N}}$
converges gauge monotonically to $x^{*}\in\operatorname{Fix}T\cap D$ with the
rate $O(s_{k}(d(x^{0},\operatorname{Fix}T\cap D)))$ where
$s_{k}(t):=\sum_{j=k}^{\infty}\theta^{(j)}(t)$. $\Box$

######  Corollary 19 (linear convergence).

  1. (a)

(necessity) In the setting of Theorem 16(a), if all sequences
$(x^{k})_{k\in\mathbb{N}}$ defined by $x^{k+1}=Tx^{k}$ and initialized in $D$
are linearly monotone relative to $S$ with rate $\gamma<1$, then all sequences
initialized on $D$ converge R-linearly to some $\overline{x}\in S$ with rate
$O(\gamma^{k})$. Moreover, $\mathcal{T}_{S}$ defined by (22) is linearly
metrically subregular for $0$ relative to $D$ on $D$ with gauge
$\mu(t)=(1-\gamma)^{-1}t$.

  2. (b)

(sufficiency) In the setting of Theorem 16(b) suppose that $T$ satisfies

$d(x,\operatorname{Fix}T\cap D)\leq\mu d(x,Tx),\hskip 5.69046pt\forall x\in
D,$ (30)

with the scalar $\mu$ satisfying

$\sqrt[p]{\tfrac{1-\overline{\alpha}}{\overline{\alpha}(1+\epsilon)}}<\mu<\sqrt[p]{\tfrac{1-\overline{\alpha}}{\overline{\alpha}\epsilon}}.$

Then for any $x^{0}\in D$, the sequence $(x^{k})_{k\in\mathbb{N}}$ defined by
$x^{k+1}=Tx^{k}$ is $R$-linearly convergent to a point in
$\operatorname{Fix}T\cap D$ with rate
$\gamma=\sqrt[p]{1+\epsilon-\frac{1-\overline{\alpha}}{\overline{\alpha}\mu^{p}}}$.

In the statements above, the violation of $\alpha$-firm nonexpansiveness,
$\epsilon$, has to be compensated for by an equally strong gauge of metric
subregularity with this value of $\epsilon$ explicitly accounted for in the
gauge. The next result shows that these can be decoupled if $T$ is pointwise
asymptotically $\alpha$-firmly nonexpansive at fixed points. In particular, if
$T$ is pointwise almost $\alpha$-firmly nonexpansive at
$y\in\operatorname{Fix}T$ with arbitrarily small violation $\epsilon$, then
whenever $T$ is (gauge) metrically subregular at $y$, there is a neighborhood
of $y$ on which convergence of the fixed point iteration can be quantified by
said gauge. In this situation it suffices to qualitatively determine metric
subregularity - the exact value of the constants in relation to the violation
of $\alpha$-firmness is not needed in order to determine local convergence on
the order of the gauge.

######  Proposition 20.

Let $(G,d)$ be a $p$-uniformly convex space with constant $c$; let $D\subset
G$, let $T:\,D\to D\,$, and let $S:=\operatorname{Fix}T\cap D$ be nonempty.
Assume that $T$ is a self mapping on sufficiently small balls around points in
$S$ restricted to $D$, and that $T$ is pointwise asymptotically
$\alpha$-firmly nonexpansive at all points $y\in S$ with constant
$\overline{\alpha}\in(0,1)$. Suppose further that $T$ satisfies

$d(x,\operatorname{Fix}T\cap D)\leq\mu(d(x,Tx)),\hskip 5.69046pt\forall x\in
D,$ (31)

with gauge $\mu$ given by (19) and
$\tau=(1-\overline{\alpha})/\overline{\alpha}$. Then for any $x^{0}$ close
enough to $S$, the sequence $(x^{k})_{k\in\mathbb{N}}$ defined by
$x^{k+1}=Tx^{k}$ converges gauge monotonically to some
$x^{*}\in\operatorname{Fix}T\cap D$ with rate $O(s_{k}(t_{0}))$ where
$s_{k}(t):=\sum_{j=k}^{\infty}\theta^{(j)}(t)$ and
$t_{0}:=d(x^{0},\operatorname{Fix}T)$ for $\theta$ given implicitly by (19)
satisfying (18).

###### Proof.

Since $T$ is a self mapping on $\mathbb{B}_{\delta}(S)\cap D$ for $\delta$
small enough, and $T$ is pointwise asymptotically $\alpha$-firmly nonexpansive
with constant $\overline{\alpha}\in(0,1)$, the result follows immediately from
Proposition 14 and Theorem 16 when the domain $D$ is restricted to
$\mathbb{B}_{\delta}(S)$ for $\delta$ sufficiently small. ∎

##  4 Proximal Mappings

We return now to the prox mapping (2). It was shown in [8, Proposition 2.7]
that the $\operatorname{argmin\,}$ in (2) exists and is unique if $f$ is
proper, lsc and convex. In general the prox mapping of a convex function is
not $\alpha$-firmly nonexpansive. However it was shown in [4, Corollary 23]
that it is almost $\alpha$-firmly nonexpansive. This and other properties of
prox mappings are collected in the following result.

######  Theorem 21.

Let $(G,d)$ be a $p$-uniformly convex metric space with constant $c\in(0,2]$,
and let $f\colon G\rightarrow\mathbb{R}$ be proper, convex and lower
semicontinuous.

  1. (i)

If $(G,d)$ is symmetric perpendicular, then
$\operatorname{prox}^{p}_{f,\lambda}$ is quasi strictly nonexpansive, that is,

$d(\operatorname{prox}^{p}_{f,\lambda}(x),\overline{x})<d(x,\bar{x})\quad\forall
x\in
G,\forall\overline{x}\in\operatorname{argmin\,}f=\operatorname{Fix}\operatorname{prox}^{p}_{f,\lambda}.$

  2. (ii)

The prox mapping $\operatorname{prox}_{f,\lambda}^{p}$ is pointwise almost
$\alpha$-firmly nonexpansive at all $y\in\operatorname{argmin\,}f$ on $G$ with
constant

$\alpha_{c}=\tfrac{c(c-1)}{c(c-1)+2}\quad\mbox{and violation
}\quad\epsilon_{c}=\tfrac{2-c}{c-1}.$ (32)

  3. (iii)

If $(G,d)$ is a CAT$(\kappa)$ space, then
$\operatorname{prox}_{f,\lambda}^{p}$ is pointwise asymptotically
$\alpha$-firmly nonexpansive at all $y\in\operatorname{argmin\,}f$ with
constant $\overline{\alpha}=1/2$.

###### Proof.

(i). Let $x\in G$ be arbitrary and
$y\coloneqq\operatorname{prox}^{p}_{f,\lambda}(x)$. We prove by contradiction
that the projection of $x$ onto the geodesic $[\overline{x},y]$ connecting
$\overline{x}$ and $y$ is $y$, i.e. $P_{[\overline{x},y]}(x)=y$. Therefore
assume that $P_{[\overline{x},y]}(x)\neq y$, i.e.
$P_{[\overline{x},y]}(x)=(1-t)y\oplus t\overline{x}$ for some $t\in(0,1]$.
Then $f((1-t)y\oplus t\overline{x})\leq(1-t)f(y)+tf(\overline{x})\leq f(y)$
and $d((1-t)y\oplus t\overline{x},x)<d(y,x)$. Now

$f((1-t)y\oplus t\overline{x})+\frac{1}{p\lambda^{p-1}}d((1-t)y\oplus
t\overline{x},x)^{p}<f(y)+\frac{1}{p\lambda^{p-1}}d(y,x)$

contradicts $y=\operatorname{prox}^{p}_{f,\lambda}(x)$. Hence our assumption
must be discarded and $P_{[\overline{x},y]}(x)=y$. In particular
$[\overline{x},y]\perp_{y}[x,y]$ and hence by the symmetric perpendicular
property $[x,y]\perp_{y}[\overline{x},y]$. Now
$[x,y]\perp_{y}[\overline{x},y]$ in turn yields the claim
$d(y,\overline{x})\leq d(x,\overline{x})$.

If in addition $(G,d)$ is a $p$-uniformly convex space

$\displaystyle d(\overline{x},y)^{p}$
$\displaystyle=d(\overline{x},P_{[x,y]}(\overline{x}))^{d}\leq
d(\overline{x},\frac{1}{2}x\oplus\frac{1}{2}y)^{p}$
$\displaystyle\leq\frac{1}{2}d(\overline{x},x)^{p}+\frac{1}{2}d(\overline{x},y)^{p}-\frac{c}{2}\frac{1}{4}d(x,y)^{p}$
$\displaystyle\leq d(\overline{x},x)^{p}-\frac{c}{2}\frac{1}{4}d(x,y)^{p}.$

This is only possible if either $x=y$ or
$d(\overline{x},y)<d(\overline{x},x)$. In both cases
$\operatorname{prox}^{p}_{f,\lambda}$ is quasi strictly nonexpansive.

(ii). This is [4, Corollary 23].

(iii). Let $\epsilon>0$, $y\in\operatorname{argmin\,}f$ and
$c=\frac{2+\epsilon}{1+\epsilon}$. Then $c\in(1,2)$ and there is a unique
solution $t\in(0,\pi/2)$ to $\frac{c}{2}=t\tan(\pi/2-t)$. Set
$\delta=t/(2\sqrt{\kappa})$. Then $\delta\in(0,\pi/(4\sqrt{\kappa}))$ and
$(\mathbb{B}_{\delta}(y),\left.d\right|_{\mathbb{B}_{\delta}(y)})$ is a
$p$-uniformly convex space with constant $c$ by Lemma 1. Part (i) ensures that
$\operatorname{prox}^{p}_{f,\lambda}$ is a self mapping on
$\mathbb{B}_{\delta}(y)$ and hence

$\displaystyle\operatorname{argmin\,}_{z\in
G}f(z)+\frac{1}{p\lambda^{p-1}}d(z,x)^{p}=\operatorname{argmin\,}_{z\in\mathbb{B}_{\delta}(y)}f(y)+\frac{1}{p\lambda^{p-1}}d(y,x)^{p}$

and we will use the same notation $\operatorname{prox}^{p}_{f,\lambda}$ for
the operator restricted to the subspace
$(\mathbb{B}_{\delta}(y),\left.d\right|_{\mathbb{B}_{\delta}(y)})$. The
operator $\operatorname{prox}^{p}_{f,\lambda}$ is pointwise almost
$\alpha$-firmly nonexpansive with constant
$\alpha_{c}=\frac{c(c-1)}{c(c-1)+2}$ and violation
$\epsilon_{c}=\frac{2-c}{c-1}=\epsilon$ on
$(\mathbb{B}_{\delta}(y),\left.d\right|_{\mathbb{B}_{\delta}(y)})$ by part
(ii). Note that $\alpha_{c}\nearrow 1/2$ as $c\nearrow 2$ and by Propositon
6(iii) $\operatorname{prox}^{p}_{f,\lambda}$ is pointwise almost
$\alpha$-firmly nonexpansive with constant $\overline{\alpha}=1/2$ for all
$c\in(0,2)$. Since $\epsilon_{c}\searrow 0$ as $c\nearrow 2$, this implies
that $\operatorname{prox}^{p}_{f,\lambda}$ is pointwise asymptotically
$\alpha$-firmly nonexpansive at $y\in\operatorname{argmin\,}f$ with constant
$\overline{\alpha}=1/2$ and neighborhood $\mathbb{B}_{\delta}(y)$ of $y$. ∎

######  Remark 22.

In part (i) of Theorem 21, quasi nonexpansiveness comes from the symmetric
perpendicular property. Strict quasi nonexpansiveness comes from the property
of $p$-uniformly convex spaces.

The next result gathers properties of mappings built from prox mappings.

######  Proposition 23.

Let $(G,d)$ be a $p$-uniformly convex space with constant $c\in(1,2]$ and let
$f,g\colon G\rightarrow\mathbb{R}\cup\\{+\infty\\}$ be convex, proper and
lower semicontinuous. Assume that
$\operatorname{argmin\,}f\cap\operatorname{argmin\,}g\neq\emptyset$.

  1. (i)

The operator
$T\coloneqq\operatorname{prox}_{f,\lambda_{2}}^{p}\circ\operatorname{prox}_{g,\lambda_{1}}^{p}$
($\lambda_{1},\lambda_{2}>0$) is pointwise almost $\alpha$-firmly nonexpansive
at all points
$y\in\Omega:=\operatorname{argmin\,}f\cap\operatorname{argmin\,}g$ on $G$ with
constant $\alpha_{\circ}=\frac{2(c-1)}{2c-1}$ and violation
$\epsilon_{\circ}=\frac{1}{(c-1)^{2}}-1$. If $(G,d)$ is a CAT($\kappa$) space,
then $T$ is pointwise asymptotically $\alpha$-firmly nonexpansive at all
$y\in\Omega$ with constant $\overline{\alpha}_{\circ}=2/3$.

  2. (ii)

Let $T_{0}:\,G\to G\,$ be pointwise asymptotically $\alpha$-firmly
nonexpansive with constant $\overline{\alpha}_{0}$ at all
$y\in\Omega:=\operatorname{argmin\,}f\cap\operatorname{Fix}T_{0}$. The
operator $T\coloneqq\operatorname{prox}_{f,\lambda}^{p}\circ T_{0}$
($\lambda>0$) is pointwise almost $\alpha$-firmly nonexpansive at all points
$y\in\Omega$ on $G$ with constant and violation

$\alpha=\tfrac{\overline{\alpha}_{0}+\alpha_{c}-2\overline{\alpha}_{0}\alpha_{c}}{\frac{c}{2}\left(1-\overline{\alpha}_{0}-\alpha_{c}+\overline{\alpha}_{0}\alpha_{c}\right)+\overline{\alpha}_{0}+\alpha_{c}-2\overline{\alpha}_{0}\alpha_{c}}\quad\mbox{and
}\epsilon=\epsilon_{0}+\epsilon_{c}+\epsilon_{0}\epsilon_{c}$ (33)

where $\epsilon_{0}$ is the violation of $\alpha$-firm nonexpansiveness of
$T_{0}$ on some neighborhood small enough. If $(G,d)$ is a CAT($\kappa$)
space, then $T$ is pointwise asymptotically $\alpha$-firmly nonexpansive at
all $y\in\Omega$ with constant

$\overline{\alpha}:=\tfrac{1}{2-\overline{\alpha}_{0}}.$ (34)

  3. (iii)

The Krasnoselski-Mann relaxation
$T:=\beta\operatorname{prox}_{f,\lambda}^{p}\oplus(1-\beta)\operatorname{Id}$
is pointwise almost $\alpha$-firmly nonexpansive at all points
$y\in\Omega:=\operatorname{argmin\,}f$ on $G$ with constant

$\alpha_{\beta}=\frac{\alpha_{c}\beta^{p-1}}{\alpha_{c}\beta^{p-1}-\alpha_{c}\beta+1}$

and violation $\epsilon_{\beta}=\beta\epsilon_{c}$ where $\alpha_{c}$ and
$\epsilon_{c}$ are given by (32). If $(G,d)$ is a CAT($\kappa$) space, then
$T$ is pointwise asymptotically $\alpha$-firmly nonexpansive at all
$y\in\Omega$ with constant

$\overline{\alpha}_{\beta}:=\tfrac{\beta^{p-1}}{\beta^{p-1}-\beta+2}.$

  4. (iv)

The composition
$T:=\operatorname{prox}_{f,\lambda_{2}}^{p}\circ\left(\beta\operatorname{prox}_{g,\lambda_{1}}^{p}\oplus(1-\beta)\operatorname{Id}\right)$
is pointwise almost $\alpha$-firmly nonexpansive at all points
$y\in\Omega:=\operatorname{argmin\,}f\cap\operatorname{argmin\,}g$ on $G$ with
constant

$\widehat{\alpha}=\tfrac{\alpha_{\beta}+\alpha_{c}-2\alpha_{\beta}\alpha_{c}}{\frac{c}{2}\left(1-\alpha_{\beta}-\alpha_{c}+\alpha_{\beta}\alpha_{c}\right)+\alpha_{\beta}+\alpha_{c}-2\alpha_{\beta}\alpha_{c}}\quad\mbox{
and violation
}\widehat{\epsilon}=(1+\beta)\epsilon_{c}+\beta\epsilon_{c}^{2},$ (35)

where $\alpha_{\beta}$, $\alpha_{c}$, and $\epsilon_{c}$ are the constants in
part (iii) and Theorem 21(ii) respectively. If $(G,d)$ is a CAT($\kappa$)
space, then $T$ is pointwise asymptotically $\alpha$-firmly nonexpansive at
all $y\in\Omega$ with constant

$\widehat{\alpha}=\tfrac{1}{2-\overline{\alpha}_{\beta}}.$

where $\overline{\alpha}_{\beta}$ is the constant in part (iii),

  5. (v)

If $(G,d)$ is symmetric perpendicular, the projected gradient operator

$T:=P_{C}\circ\left(\beta\operatorname{prox}_{g,\lambda}^{p}\oplus(1-\beta)\operatorname{Id}\right)$

is pointwise almost $\alpha$-firmly nonexpansive at all points
$y\in\Omega:=C\cap\operatorname{argmin\,}g$ on $G$ with

$\alpha_{PG}=\tfrac{1}{\frac{c}{2}\left(1-\alpha_{\beta}\right)+1}\quad\mbox{
and violation }\epsilon_{PG}=\epsilon_{c}\beta.$ (36)

If $(G,d)$ is a CAT($\kappa$) space, then $T$ is pointwise asymptotically
$\alpha$-firmly nonexpansive at all $y\in\Omega$ with constant

$\alpha_{PG}=\tfrac{1}{2-\overline{\alpha}_{\beta}}.$

where $\overline{\alpha}_{\beta}$ is the constant in part (iii),

###### Proof.

(i). By Theorem 21(ii), the operators $\operatorname{prox}_{f,\lambda}^{p}$
and $\operatorname{prox}_{g,\lambda}^{p}$ are almost quasi $\alpha$-firmly
nonexpansive with constants $\alpha_{c}=\frac{c(c-1)}{c(c-1)+2}$ and violation
$\epsilon_{c}=\frac{2-c}{c-1}$. The operator $T$ is almost $\alpha$-firmly
nonexpansive at all points $y\in\Omega$ on $G$ with

$\displaystyle\alpha_{\circ}=\frac{2\alpha_{c}-2\alpha_{c}^{2}}{\frac{c}{2}(1-2\alpha_{c}+\alpha_{c}^{2})+2\alpha_{c}-2\alpha_{c}^{2}}$

and violations $1+\epsilon_{\circ}=(1+\epsilon_{c})^{2}$ by Proposition 10 . A
short calculation yields

$\displaystyle\alpha_{\circ}=\frac{2(c-1)}{2c-1}\quad\mbox{ and
}\quad\epsilon_{\circ}=\frac{1}{(c-1)^{2}}-1.$

Taking the limit as $c\to 2$ from below yields the constant
$\overline{\alpha}_{\circ}=2/3$ with limiting violation
${\overline{\epsilon}}_{\circ}=0$. The same argument as Propositon 21(iii)
then shows that, when $G,d)$ is a CAT$(\kappa)$ space, the composition of two
prox mappings is pointwise asymptotically $\alpha$-firmly nonexpansive at
points in $\Omega$ with constant $2/3$.

(ii). Theorem 21(ii) and Proposition 10 yield pointwise almost $\alpha$-firm
nonexpansiveness of $T$ at $y\in\Omega$ with constant and violation given by
(33). where $\alpha_{c}$ and $\epsilon_{c}$ are given by (32),
$\overline{\alpha}_{0}$ is the asymptotic constant of $\alpha$-firm
nonexpansiveness of $T_{0}$, and $\epsilon_{0}$ is the violation on some
neighborhood. (By Proposition 6(iii) if $T_{0}$ is pointwise almost
$\alpha$-firmly nonexpansive with constant $\alpha_{0}<\overline{\alpha}_{0}$,
then $T_{0}$ is also pointwise almost $\alpha$-firmly nonexpansive with
constant $\overline{\alpha}_{0}$.) By Theorem 21 (iii) and the assumption that
$T_{0}$ is pointwise asymptotically $\alpha$-firmly nonexpansive at
$\operatorname{Fix}T_{0}$ with constant $\overline{\alpha}_{0}$, the same
argument as Proposition 21(iii) establishes that, when $G,d)$ is a
CAT$(\kappa)$ space, $T$ is pointwise asymptotically $\alpha$-firmly
nonexpansive at points in $\Omega$ with constant $\overline{\alpha}$ given by
(34).

(iii). The first statement is an immediate application of Proposition 12 and
Theorem 21(ii). When $(G,d)$ is a CAT$(\kappa)$ space, the same argument as
Proposition 21(iii) establishes that Krasnoselsky-Mann relaxations of prox
mappings are pointwise asymptotically $\alpha$-firmly nonexpansive with
constant $\overline{\alpha}_{\beta}$ as claimed.

(iv). This is an application of part (ii) to part (iii).

(v). This is a specialization of part (iv) when $f$ is the indicator function
of a convex set $C$ and follows from the fact that, on symmetric perpendicular
$p$-uniformly convex spaces, the projector is pointwise $\alpha$-firmly
nonexpansive at all points in $C$ with constant $\alpha=1/2$ (no violation) as
shown in [4, Proposition 25].
∎

######  Remark 24.

Part (i) of Proposition 23 coincides with $\alpha=\frac{2}{3}$ and
$\epsilon=0$ in the classic setting with $c=2$. In particular the composition
$P_{A}\circ P_{B}$ of two projections $P_{A}$ and $P_{B}$ onto convex sets $A$
and $B$ with $A\cap B\neq\emptyset$ is $\alpha$-firmly nonexpansive at all
$y\in A\cap B$ on $G$ with $\alpha=\frac{2}{3}$ and violation $\epsilon=0$.
However this result does not apply if the problem is infeasible, i.e. $A\cap
B=\emptyset$.

These properties allow us to prove the following fundamental result.

######  Theorem 25 (convergence of proximal algorithms in CAT($\kappa$)
spaces).

Let $(G,d)$ be a $CAT(\kappa)$ space with $\kappa>0$ and $f,g\colon
G\rightarrow\mathbb{R}\cap\\{+\infty\\}$ be proper, convex and lower
semicontinuous with
$\operatorname{argmin\,}f\cap\operatorname{argmin\,}g\neq\emptyset$. Let $T$
denote any of the mappings in Proposition 23. If $T$ satisfies

$d(x,\operatorname{Fix}T\cap D)\leq\mu d(x,Tx),\hskip 5.69046pt\forall x\in
D,$ (37)

with constant $\mu$, then the fixed point sequence initialized from any
starting point close enough to $\operatorname{Fix}T\cap D$ is at least
linearly convergent to a point in $\operatorname{Fix}T\cap D$ with rate
$\gamma=\sqrt{1+\epsilon-\tfrac{1-\alpha}{\alpha\mu^{2}}}<1$, where $\alpha$
and $\epsilon$ are the respective constant and violation of pointwise
$\alpha$-firm nonexpansiveness of the fixed point mapping $T$ as given in
Proposition 23. The asymptotic rate of convergence is
$\overline{\gamma}=\sqrt{1-\tfrac{1-\overline{\alpha}}{\overline{\alpha}\mu^{2}}}<1$,
where $\overline{\alpha}$ is the respective constant of pointwise asymptotic
$\alpha$-firm nonexpansiveness of the fixed point mapping $T$.

###### Proof.

As established in Theorem 21 and Proposition 23, all of the mappings covered
in those results are pointwise asymptotically $\alpha$-firmly nonexpansive at
points in $\Omega$ with constants $\overline{\alpha}<1$ where $\Omega$ is one
of the following subsets corresponding to the respective mappings (i)-(v) in
23: (i) $\Omega=\operatorname{argmin\,}f\cap\operatorname{argmin\,}g$; (ii)
$\Omega\subset\operatorname{Fix}T_{0}\cap\operatorname{argmin\,}f$; (iii)
$\Omega=\operatorname{argmin\,}f$; (iv)
$\Omega=\operatorname{argmin\,}f\cap\operatorname{argmin\,}g$; (v)
$\Omega=C\cap\operatorname{argmin\,}g$.

As noted in Remark 3, any CAT($\kappa$) space is symmetric perpendicular
locally, so by Theorem 21(i) and Lemma 7, in every case
$\operatorname{Fix}T=\Omega$. Now, if $T$ satisfies (37) at all points in
$\operatorname{Fix}T$ on $G$ with constant $\mu$, it follows immediately from
Proposition 20 that the fixed point iteration converges linearly to a point in
$\operatorname{Fix}T\cap D$ with the given rate for all starting points close
enough to $\operatorname{Fix}T\cap D$, as claimed. ∎

##  5 Proximal Splitting Methods

The concrete examples provided here have been well studied for $p$-uniformly
convex spaces with $p=c=2$, i.e. CAT(0) spaces. The tools established in the
previous sections open the door to applying these methods in CAT$(\kappa)$
spaces, which is new. Since CAT$(\kappa)$ spaces are $p$-uniformly convex with
$p=2$, to avoid confusion, we revert to the usual notation for proximal
operators in the setting, namely $\operatorname{prox}_{f,\lambda}$, omitting
the exponent.

Let $(G,d)$ be a CAT$(\kappa$) space, $f_{i}:G\to G$ be proper lsc convex
functions for $i=1,2,\dots N$. Consider the problem

$\inf_{x\in G}\sum_{i=1}^{N}f_{i}(x).$ (38)

Applying backward-backward splitting to this problem yields Algorithm 1.

Parameters : Functions $f_{1}\ldots,f_{N}$ and $\lambda_{i}>0$
$(i=1,2,\dots,N)$.

Initialization : Choose $x_{0}\in G$.

for  _$k=0,1,2,\ldots$_ do

$\displaystyle
x_{k+1}=Tx_{k}:=\left(\operatorname{prox}_{f_{N},\lambda_{N}}\circ\cdots\circ\operatorname{prox}_{f_{2},\lambda_{2}}\circ\operatorname{prox}_{f_{1},\lambda_{1}}\right)(x_{k})$

Algorithm 1 Proximal splitting

Local linear convergence follows from Theorem 25 and the extension of
Proposition 23(i) via part (ii) of the same proposition and induction, under
the assumption that $\mathcal{T}_{\Omega}$ defined by (22) – which simplifies
to (23) – is linearly metrically subregular for $0$ on $G$ with constant $\mu$
and $\Omega:=\cap_{j}\operatorname{argmin\,}f_{j}\neq\emptyset$. By
Proposition 6(i), linear metric subregularity simplifies to

$d(x,\Omega)\leq\mu d(Tx,x)\quad\forall x\in D.$ (39)

Recall, in a $p$-uniformly convex space with $p=2$, the Moreau-Yosida envelope
of $f$ is defined by

$e_{f,\lambda}(x):=\inf_{y\in
G}\left(f(y)+\tfrac{1}{2\lambda}d(x,y)^{2}\right).$

The analogue to the direction of steepest descent for the Moreau-Yosida
envelope in $p$-uniformly convex settings is

$(1-\beta)x\oplus\beta\operatorname{prox}_{f,\lambda}(x).$ (40)

Specializing problem (38) to the case $N=2$ and $f_{2}=\iota_{C}$, the
indicator function of some closed convex set $C\subset G$ yields Algorithm 2,
the analog to projected gradients in CAT($\kappa$) space, which is the
projected resolvent/projected prox iteration.

Parameters : $f:\,G\to\mathbb{R}\,$, the closed set $C\subset G$, $\lambda>0$
and $\beta\in(0,1)$.

Initialization : Choose $x_{0}\in G$.

for  _$k=0,1,2,\ldots$_ do

$\displaystyle
x_{k+1}=T_{PG}(x_{k}):=P_{C}\left((1-\beta)\operatorname{Id}\oplus\beta\operatorname{prox}_{f,\lambda}\right)(x_{k})$

Algorithm 2 Metric Projected Gradients

Local linear convergence follows immediately from Theorem 25 under the
assumption that $T$ satisfies (30) and $\Omega:=\operatorname{argmin\,}f\cap
C\neq\emptyset$.

Compositions of projectors in CAT$(\kappa)$ spaces has been studied in [4] and
[1]. We consider Algorithm 1 when the functions $f_{i}:=\iota_{C_{i}}$, the
indicator functions of closed convex sets $C_{i}\subset G$, where $(G,d)$ is a
complete, symmetric perpendicular $p$-uniformly convex space with constant
$c$. The $p$-proximal mapping of the indicator function is the metric
projector and so by [4, Proposition 25] these are pointwise $\alpha$-firmly
nonexpansive at all points in $\cap_{i}C_{i}$ (assuming, of course, that this
is nonempty) and by [4, Lemma 10] the cyclic projections mapping

$T_{CP}:=P_{C_{N}}\cdot P_{C_{2}}P_{C_{1}}$ (41)

is pointwise $\alpha$-firmly nonexpansive at all points in
$\cap_{i}C_{i}=\operatorname{Fix}T_{CP}$, when the intersection is nonempty,
with constant $\overline{\alpha}_{N}=\frac{N-1}{N}$ on $G$. $\Delta$\- or weak
convergence (no rate) to a point in $\cap_{i}C_{i}$ follows from [4, Theorem
27], with strong convergence whenever one of the sets is compact. If in
addition $d(x,\cap_{i}C_{i})\leq\mu d(T_{CP}x,x)$ for all $x\in G$ where
$\mu>0$ is the rate of linear metric subregularity, then, by Theorem 25 below,
the sequence $(x_{k})$ initialized anywhere in $G$ converges linearly to some
$x^{*}\in\cap_{i}C_{i}$.

##  6 Open Problems

There are two obvious next steps for this work. First and foremost is to
determine the requirements for quantitative convergence of proximal splitting
methods for the case when the individual prox mappings do not have common
fixed points – the so-called inconsistent case – since it is too limiting to
require that the fixed points of the constituent elements of splitting methods
coincide. The second item to explore is qualitative settings in which metric
subregularity comes “for free”. In linear settings, polyhedrality and isolated
fixed points suffice to guarantee metric subregularity [7, Propositions 3I.1
and 3I.2] and this was successfully used to prove local linear convergence of
the ADMM/Douglas-Rachford algorithms in a convex setting [2, Theorem 2.7]. In
more general settings, the Kurdyka-Łojasiewicz (KL) property – which is
equivalent to metric subregularity [6, Corollary 4 and Remark 5] – is
satisfied by semi-algebraic functions [5]. Analogues to these properties for
$p$-uniformly convex spaces would be very useful.

##  7 Declarations

###  7.1 Availability of data and materials

Not applicable

###  7.2 Competing interests

The authors declare that they have no competing interests

###  7.3 Funding

FL was supported in part by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) – Project-ID LU 1702/1-1. DRL was supported in part by
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID
LU 1702/1-1 and in part by Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) – Project-ID 432680300 – SFB 1456.

###  7.4 Authors’ contributions

The authors contributed equally to all results. All authors read and approved
the final manuscript.

###  7.5 Acknowledgements

Not applicable.

## References

  * [1] D. Ariza-Ruiz, G. López-Acedo, and A. Nicolae.  The asymptotic behavior of the composition of firmly nonexpansive mappings.  J Optim Theory Appl, 167:409–429, 2015.
  * [2] T. Aspelmeier, C. Charitha, and D. R. Luke.  Local linear convergence of the ADMM/Douglas–Rachford algorithms without strong convexity and application to statistical imaging.  SIAM J. Imaging Sci., 9(2):842–868, 2016.
  * [3] A. Bërdëllima.  Investigations in Hadamard Spaces.  PhD thesis, Georg-August Universität Göttingen, Göttingen, 2020\.
  * [4] A. Bërdëllima, F. Lauster, and D. R. Luke.  $\alpha$-firmly nonexpansive operators on metric spaces.  Technical report, University of Göttingen, 2021.
  * [5] J. Bolte, A. Daniilidis, and A. Lewis.  The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.  SIAM J. Optim., 17:1205–1223, 2006.
  * [6] J. Bolte, A. Daniilidis, O. Ley, and L. Mazet.  Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity.  Trans. Am. Math. Soc., 362(6):3319–3363, 2010.
  * [7] A. L. Dontchev and R. T. Rockafellar.  Implicit Functions and Solution Mappings.  Springer-Verlag, Dordrecht, second edition, 2014.
  * [8] C. Izuchukwu, G. C. Ugwunnadi, O. T. Mewomo, A. R. Khan, and M. Abbas.  Proximal-type algorithms for split minimization problem in P-uniformly convex metric spaces.  Numer. Algorithms, 82(3):909–935, 2019.
  * [9] K. Kuwae.  Jensen’s inequality on convex spaces.  Calc. Var. Partial Differ. Equ., 49(3-4):1359–1378, 2014.
  * [10] D. R. Luke, M. Teboulle, and N. H. Thao.  Necessary conditions for linear convergence of iterated expansive, set-valued mappings.  Math. Program., 180:1–31, 2018.
  * [11] D. R. Luke, N. H. Thao, and M. K. Tam.  Quantitative convergence analysis of iterated expansive, set-valued mappings.  Math. Oper. Res., 43(4):1143–1176, 2018.
  * [12] A. Naor and L. Silberman.  Poincaré inequalities, embeddings, and wild groups.  Compos. Math., 147(5):1546–1572, 2011.
  * [13] S. Ohta.  Convexities of metric spaces.  Geom. Dedicata, 125:225–250, 2007.