#  $\alpha$-Firmly Nonexpansive Operators on Metric Spaces

Arian Bërdëllima Institute for Numerical and Applied Mathematics, University
of Göttingen. AB was supported by the Deutscher Akademischer Austauschdienst
(DAAD<EMAIL_ADDRESS>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>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

We extend to $p$-uniformly convex spaces tools from the analysis of fixed
point iterations in linear spaces. This study is restricted to an appropriate
generalization of single-valued, pointwise $\alpha$-averaged mappings. Our
main contribution is establishing a calculus for these mappings in p-uniformly
convex spaces, showing in particular how the property is preserved under
compositions and convex combinations. This is of central importance to
splitting algorithms that are built by such convex combinations and
compositions, and reduces the convergence analysis to simply verifying
$\alpha$-firm nonexpansiveness of the individual components at fixed points of
the splitting algorithms. Our convergence analysis differs from what can be
found in the previous literature in that only $\alpha$-firm nonexpansiveness
with respect to fixed points is required. Indeed we show that, if the fixed
point mapping is pointwise nonexpansive at all cluster points, then these
cluster points are in fact fixed points, and convergence of the sequence
follows. Additionally, we provide a quantitative convergence analysis built on
the notion of gauge metric subregularity, which we show is necessary for
quantifiable convergence estimates. This allows one for the first time to
prove convergence of a tremendous variety of splitting algorithms in spaces
with curvature bounded from above.

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

Secondary 53C23, 53C20, 49M27

Keywords: Averaged mappings, firmly nonexpansive mappings, Hadamard space,
p-uniformly convex, CAT(k) space, nonexpansive mappings, firmly nonexpansive,
asymptotic regularity, fixed point iteration

##  1 Introduction

Our focus is on the extension to $p$-uniformly convex spaces of tools from the
analysis of fixed point iterations in linear spaces. We are indebted to the
works of Kuwae [24] and Ariza-Ruiz, Leuştean, López-Acedo, and Nicolae [2, 3]
who studied firm nonexpansiveness in nonlinear spaces, though the asymptotic
behavior of averaged mappings in uniformly convex Banach spaces was already
studied by Baillon, Bruck and Reich in [5]. Reich and Shafrir established an
approach to the study of convex combinations of nonexpansive mappings in
hyperbolic spaces [36], the foundations for which were developed in [14].
Building on this, we follow the framework for nonconvex optimization
established in [32] which is predicated on only two fundamental elements in a
Euclidean setting: pointwise almost $\alpha$-averaging [32, Definition 2.2]
and metric subregularity [17, Definition 2.1b]. Almost averaged mappings are,
in general, set-valued. In nonlinear metric spaces, there are several
difficulties that arise: first, there is no straight-forward generalization of
the averaging property since addition is not defined on general metric spaces;
and second, multivaluedness, which comes with allowing mappings to be
expansive. The issue of multivaluedness introduces technical overhead, but
does not, at this early stage, seem to present any conceptual difficulties.
The issue of violations of averagedness and nonexpansiveness is more
fundamental. We show that such violations are unavoidable if one wants to work
with resolvents. The foundations for working with these difficulties are
established here, but we postpone until later a direct study of resolvents on
spaces with curvature bounded from above.

We therefore restrict our attention to an appropriate generalization of
single-valued, pointwise $\alpha$-averaged mappings. This generalization leads
to a definition of firm nonexpansiveness that is less retrictive than notions
with the same name studied in [14, 35, 36, 8, 3], though, we show that our
notion is implied by the previously studied objects. Our main contribution is
establishing a calculus for these mappings in $p$-uniformly convex spaces,
showing in particular how the property is preserved under compositions and
convex combinations. This is of central importance to splitting algorithms
that are built by such convex combinations and compositions, and reduces the
convergence analysis to simply verifying quasi $\alpha$-firm nonexpansiveness
of the individual components of the splitting algorithms. Our convergence
analysis also differs from what can be found in the previous literature in
that only quasi $\alpha$-firm nonexpansiveness is required. Indeed we show
(Theorem 27) that, if the fixed point mapping is pointwise nonexpansive at the
asymptotic centers of all subsequences, then all asymptotic centers are fixed
points and weak (precisely, $\Delta$-) convergence of the fixed point sequence
is guaranteed. Additionally, we provide a quantitative convergence analysis
built on the notion of gauge metric subregularity, which we show is in fact
necessary for quantifiable convergence estimates. This allows one to prove
convergence of a tremendous variety of splitting algorithms for the first time
in spaces with curvature bounded from above.

After introducing notation, we begin in Section 2.1 with the central object of
this study given in Definition 1. Section 3 is devoted to developing
elementary properties and the calculus of $\alpha$-firmly nonexpansive
mappings. Proposition 4 and Theorem 7 in Section 3.1 establish asymptotic
regularity. The calculus of nonexpansive mappings in various settings is
established in Theorem 8 of Section 3.2. The calculus of quasi $\alpha$-firmly
nonexpansive mappings is established in Theorem 11 (compositions) of Section
3.3 and Theorem 21 (convex combinations) of Section 3.4. Convergence of fixed
point iterations of $\alpha$-firmly nonexpansive mappings is studied in
Section 4 where convergence without rates is established under the assumption
only of pointwise nonexpansiveness at the asymptotic centers of all
subsequences (Theorem 27) and quantitative convergence in Theorem 30 under the
additional assumption of (gauge) metric subregularity (Definition 29). We show
in Theorem 32 that metric subregularity with some gauge is in fact necessary
to guarantee quantitative convergence estimates. Some basic applications and
examples are presented in Section 5.

##  2 Notation and Foundations

Throughout, $(G,d)$ denotes a metric space. A geodesic path emanating from a
point $x\in G$ and extending to the point $y\in G$ is a mapping
$\gamma:\,[0,l]\to G\,$ with $\gamma(0)=x$, $\gamma(l)=y$ and
$d(\gamma(t_{1}),\gamma(t_{2}))=|t_{1}-t_{2}|$ whenever $t_{1},t_{2}\in[0,l]$.
When there is only one geodesic path joining any two points $x$ and $y$, we
use the notation $z=(1-t)x\oplus ty$ where $t=d(z,x)/d(x,y)$ to denote the
point on the geodesic connecting $x$ and $y$ such that $d(z,x)=td(x,y)$. A
geodesic space is a metric space $(G,d)$ for which every pair of points in $G$
is joined by a geodesic. If each pair of points is joined by one and only one
geodesic, the metric space is uniquely geodesic. A convex set $C\subset G$ is
a set containing all geodesics joining any two points in $C$. Following [3] we
focus on $p$-uniformly convex spaces with parameter $c$ [33]: 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 include $L_{p}$ spaces, and CAT spaces
(see Alexandrov [1] and Gromov [15]). CAT(0) spaces can be defined by (1) with
$p=2$ and $c=2$. CAT($\kappa$) spaces for $\kappa>0$ are relevant for the
study of phase retrieval and source localization [30]. When the diameter of
the space, $\operatorname{diam}{G}$ is bounded above by
$\pi/(2\sqrt{\kappa})$, then the corresponding CAT($\kappa$) space is
$2$-uniformly convex with constant
$c=\left(\pi-2\sqrt{\kappa}\epsilon\right)\tan(\epsilon\sqrt{\kappa})$ for
$\epsilon\in\left(0,\pi/(2\sqrt{\kappa})\right)$ (see [34]). Kuwae has
established bounds for the constants $p$ and $c$, illustrating their
interdependence [24, Proposition 2.5]. In particular, we note that if $c=2$,
then $p=2$. For all other $p\in(1,+\infty)$ the constant $c$ lies in the open
interval $(0,2)$. There is a connection between the modulus of convexity of a
Banach space $(Y,\|\cdot\|)$ given by
$\delta(\epsilon)\coloneqq\inf\left\\{1-\left\|\frac{x+y}{2}\right\|\mid
x,y\in Y,\|x\|=\|y\|=1,\|x-y\|\geq\epsilon\right\\}$, i.e. $Y$ will be
p-uniformly convex with constant $c>0$ if $\delta(\epsilon)\geq c\epsilon^{p}$
[24, Remark 2.7]. Finally, we will use the notation $(H,d)$ to indicate a
Hadamard space - a complete $CAT(0)$ space - and $\mathcal{H}$ will indicate a
Hilbert space.

For a set $D\subseteq G$ we denote by $\overline{\operatorname{co}{D}}$ the
closure of the convex hull of $D$. We denote the interior of $D$ by
$\operatorname{int\,}{D}$. The distance of a point $x$ to a set $D$ is with
respect to the metric $d$ is denoted $d(x,D):=\inf_{z\in D}d(x,z)$ and when
this distance is attained at some point $\overline{x}\in D$ we call this point
a projection of $x$ onto $D$. The mapping of a point $x$ to its set of
projections is called the projector and is denoted
$P_{D}(x):=\left\\{\overline{x}\,\middle|\,d(x,\overline{x})=d(x,D)\right\\}$.

A standard approach to showing the convergence of fixed point sequences is to
show that the residual of the fixed point operator vanishes. More precisely, a
self-mapping $T:G\to G$ is asymptotically regular at a point $x\in G$ whenever
$\lim_{k\to\infty}d(T^{(k)}x,T^{(k+1)}x)=0$. The mapping is said to be
asymptotically regular on $D\subset G$ if it is asymptotically regular at all
points on $D$. A sequence $(x_{k})_{k\in\mathbb{N}}$ is said to be
asymptotically regular whenever $\lim_{k\to\infty}d(x_{k},x_{k+1})=0$. In a
Banach space setting, firmly nonexpansive mappings possessing fixed points are
asymptotically regular, and sequences of fixed point iterations converge
weakly to a fixed point [35]. This is also true on $p$-uniformly convex
(nonlinear) spaces [3]. We extend these results to the generalization of
averaged mappings, what we call $\alpha$-firmly nonexpansive mappings, that
possess fixed points in Theorem 27. Rates of convergence of the iterates
$x_{k}$ are achieved in Theorem 30 under the additional assumption that the
fixed point mapping admits an error bound. The notion of $\alpha$-firm
nonexpansive operators greatly simplifies the analysis of algorithms, and
opens the door to a study of expansive operators [32] where
convexity/monotonicity plays no role.

###  2.1 $\alpha$-Firmly Nonexpansive Operators in Uniformly Convex Spaces

Extending Bruck’s origional definition of firmly nonexpansive mappings in
uniformly convex Banach spaces [11], Ariza-Ruiz, Leuştean and López-Acedo [2]
defined $\lambda$-firmly nonexpansive operators on subsets $D$ of W-hyperbolic
spaces, as those operators satisfying

$d(Tx,Ty)\leq d((1-\lambda)x\oplus\lambda Tx,(1-\lambda)y\oplus\lambda
Ty)\quad\forall x,y\in D$ (2)

for some $\lambda\in(0,1)$. If (2) holds for all $\lambda\in(0,1)$ the mapping
$T$ is called firmly nonexpansive in [2, 3]. The analog to $\alpha$-averaged
mappings is problematic since it requires the extension of geodesics beyond
the point $Tx$ (i.e. $\lambda\in\left(0,\tfrac{1-\alpha}{\alpha}\right)$).

Another notion of firm nonexpansiveness in the context of Hadamard spaces that
is equivalent to (2) for an operator $T:H\to H$ and $x,y\in H$ uses

$\phi_{T}(t):=d((1-t)x\oplus tTx,(1-t)y\oplus tTy),\quad\mbox{for }t\in[0,1].$
(3)

In [14, Chapter 24] an operator $T:H\to H$ is called firmly nonexpansive
whenever $\phi_{T}$ is nonincreasing on $[0,1]$ (see also [8, Definition
2.1.13]).

For reasons that will become apparent in Section 4.2 we define firmness of $T$
in terms of an auxilliary function that accounts for how $T$ deforms the
parallelogram with corners at $x$, $y$, $Tx$ and $Ty$. Define

$\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).$
(4)

In a Hilbert space setting this is recognizable as

$\|(\operatorname{Id}-T)x-(\operatorname{Id}-T)y\|^{2}=\psi^{(2,2)}_{T}(x,y).$

The next definition generalizes firmness to mappings that may violate the
inequality defining firmness in a manner analogous to such mappings studied in
[32, 29]. We do not fully develop the potential of this extension here, but
will use it in a result about proximal mappings in Corollary 23.

######  Definition 1.

Let $(G,d)$ be a $p$-uniformly convex metric space with constant $c$. The
operator $T:G\to G$ is pointwise almost $\alpha$-firmly nonexpansive at $y\in
D\subset G$ on $D$ if

$\exists\alpha\in(0,1),\epsilon>=0:\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.$ (5)

The smallest $\epsilon$ for which (5) holds is called the violation. If (5)
holds with $\epsilon=0$, then $T$ is pointwise $\alpha$-firmly nonexpansive at
$y\in D\subset G$ on $D$. If (5) 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 (5) holds at
all $y\in\operatorname{Fix}T$ with the same constant $\alpha$ then $T$ is said
to be almost quasi $\alpha$-firmly nonexpansive.

The transport discrepancy $\psi_{T}^{(p,c)}$ is closely related to another
object used by Berg and Nikolaev [10] in the study of CAT(0) space $(G,d)$. In
$p$-uniformly convex spaces with constant $c$ this takes the form:

$\Delta^{(p,c)}(x,y,u,v):=\frac{c}{4}(d(x,v)^{p}+d(y,u)^{p}-d(x,u)^{p}-d(y,v)^{p}).$
(6)

Specializing to a Hilbert space $\mathcal{H}$, this is identifiable with the
inner product:

$\langle
x-y,u-v\rangle=\frac{1}{2}(\|x-v\|^{2}+\|y-u\|^{2}-\|x-u\|^{2}-\|y-v\|^{2})=\Delta^{(2,2)}(x,y,u,v).$
(7)

In the context of characterizing the regularity of a mapping $T$, $u=Tx$ and
$v=Ty$ it is convenient to denote
$\Delta^{(p,c)}_{T}(x,y):=\Delta^{(p,c)}(x,y,Tx,Ty)$. This object was
introduced in [9, Chapter 7] in the context of Hadamard spaces ($p=c=2$) where
it was called the discrepancy mapping. In particular, note that

$\psi_{T}^{(p,c)}(x,y)=\tfrac{c}{2}\left(d(Tx,Ty)^{p}+d(x,y)^{p}\right)-2\Delta^{(p,c)}_{T}(x,y).$
(8)

This leads to the following equivalent characterization of pointwise
$\alpha$-firm nonexpansiveness.

######  Proposition 2.

Let $(G,d)$ be a p-uniformly convex space with constant $c>0$ and let $T:D\to
G$ for $D\subset G$. The mapping $T$ is pointwise almost $\alpha$-firmly
nonexpansive at $y\in D$ with constant $\alpha$ and violation $\epsilon$ on
$D$ if and only if

$\left(\alpha+(1-\alpha)\tfrac{c}{2}\right)d(Tx,Ty)^{p}+\left(\alpha(1+\epsilon)-(1-\alpha)\tfrac{c}{2}\right)d(x,y)^{p}\leq
2(1-\alpha)\Delta^{(p,c)}_{T}(x,y),\quad\forall x\in D.$ (9)

###### Proof.

Starting with the definition of pointwise $\alpha$-firm nonexpansiveness at
$y\in D$ we have for all $x\in D$

$\displaystyle d(Tx,Ty)^{p}\leq
d(x,y)^{p}-\tfrac{1-\alpha}{\alpha}\psi^{(p,c)}_{T}(x,y)$ $\displaystyle\iff$
$\displaystyle(1+\epsilon)\left(\alpha+(1-\alpha)\tfrac{c}{2}\right)d(Tx,Ty)^{p}\leq\left(\alpha(1+\epsilon)-(1-\alpha)\tfrac{c}{2}\right)d(x,y)^{p}\qquad\qquad\qquad\qquad$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad-(1-\alpha)\tfrac{c}{2}\left(d(Tx,x)^{p}+d(Ty,y)^{p}-d(Tx,y)^{p}-d(x,Ty)^{p}\right).$

Noting that

$-(1-\alpha)\tfrac{c}{2}\left(d(Tx,x)^{p}+d(Ty,y)^{p}-d(Tx,y)^{p}-d(x,Ty)^{p}\right)=(1-\alpha)2\Delta^{(p,c)}_{T}(x,y)$

establishes the equivalence. ∎

When $p=2$ and $c=2$, we show below in Proposition 4(v) that mappings $T$
satisfying (2) also satisfy

$d(Tx,Ty)^{p}\leq\Delta^{(p,c)}_{T}(x,y)\qquad\forall x,y\in G.$ (10)

Indeed, in this case, (10) is equivalent to Property $P_{2}$ of [3], which
Ariza-Ruiz, López-Acedo, and Nicolae show holds for mappings satisfying (2).
When (10) holds only pointwise at $y$ on a neighborhood $D\subset G$ of $y$ we
write

$d(Tx,Ty)^{p}\leq\Delta^{(p,c)}_{T}(x,y)\qquad\forall x\in D.$ (11)

This provides for a natural extension of monotonicity: an operator $T:G\to G$
is monotone whenever

$\Delta^{(p,c)}_{T}(x,y)\geqslant 0,\qquad\forall x,y\in G.$ (12)

From these definitions it follows that if $T$ satisfies (2) for all
$\lambda\in(0,1)$ then it is monotone. The correspondence between firmly
nonexpansive and nonexpansive mappings, in contrast, is a consequence of the
metric equivalent to the Cauchy-Schwarz inequality and does not hold in
general metric spaces. Nevertheless, the correspondence is recovered for
$p$-uniformly convex spaces for pointwise firmly nonexpansive mappings at
their fixed points. The first result below sorts out these various notions of
firm nonexpansiveness on CAT(0) spaces.

######  Proposition 3.

Let $(G,d)$ be a CAT(0) space. A mapping $T:G\to G$ satisfies (2) for all
$\lambda\in[0,1]$ if and only if $\phi_{T}(t)$ defined by (3) is a
nonincreasing function on $[0,1]$ for all $x,y\in G$. Any mapping $T$
satisfying (2) for all $\lambda\in(0,1]$ is $\alpha$-firmly nonexpansive in
the sense of (5) with $\alpha=1/2$.

###### Proof.

Equivalence of (2) for all $\lambda\in(0,1)$ and (3) is immediate from the
definition.

To prove the rest of the theorem, note that assumption $\phi_{T}(t)$ is a
nonincreasing function on $[0,1]$ for all $x,y\in G$ implies that
$\phi_{T}(1)\leq\phi_{T}(t)$ for all $t\in[0,1]$. On the other hand from
applying (1) with $p=2$ and $c=2$ twice we obtain

$\displaystyle\phi^{2}_{T}(t)$
$\displaystyle\leq(1-t)^{2}d(x,y)^{2}+t^{2}d(Tx,Ty)^{2}$
$\displaystyle+t(1-t)[d(x,Ty)^{2}+d(y,Tx)^{2}-d(x,Tx)^{2}-d(y,Ty)^{2}]$

Hence

$\phi^{2}_{T}(1)=d(Tx,Ty)^{2}\leq(1-t)^{2}d(x,y)^{2}+t^{2}d(Tx,Ty)^{2}+2t(1-t)\Delta^{(2,2)}_{T}(x,y)$

equivalently

$(1-t^{2})d(Tx,Ty)^{2}\leq(1-t)^{2}d(x,y)^{2}+2t(1-t)\Delta^{(2,2)}_{T}(x,y)$
(13)

Dividing by $1-t$ and letting $t\uparrow 1$ yields
$d(Tx,Ty)^{2}\leq\Delta^{(2,2)}_{T}(x,y)$. By Proposition 2 this is just
$\alpha$-firm nonexpansiveness with $\alpha=1/2$ as claimed. ∎

##  3 Properties of Pointwise Nonexpansive and $\alpha$-Firmly Nonexpansive
Mappings in Metric Spaces

Before developing the calculus of $\alpha$-firmly nonexpansive mappings, we
begin with some elementary properties of pointwise $\alpha$-firmly
nonexpansive mappings.

###  3.1 Elementary Properties of $\alpha$-Firmly Nonexpansive Operators

######  Proposition 4.

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.$ (14)

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 $\alpha$-firmly nonexpansive
at $y$ on $D$ if and only if

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

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

  3. (iii)

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

  4. (iv)

If at $y\in\operatorname{Fix}T$

$\exists\lambda\in(0,1):\quad d(Tx,y)\leq d((1-\lambda)x\oplus\lambda
Tx,y)\quad\forall x\in D,$ (16)

then $T$ is pointwise $\alpha$-firmly nonexpansive at $y$ with constant
$\alpha=1/(\lambda+1)$ on $D$.

  5. (v)

Let $p=2$ and $c=2$ (that is, $(G,d)$ is a CAT(0) space). Then

    1. (a)

$\Delta_{T}^{(2,2)}(x,y)\leq d(x,y)d(Tx,Ty)$ for all $x,y\in G$;

    2. (b)

$\psi_{T}^{(2,2)}(x,y)\geq 0$ for all $x,y\in G$;

    3. (c)

the following are equivalent:

      1. (1)

$T$ is pointwise $\alpha$-firmly nonexpansive at $y$ with constant
$\underline{\alpha}$ on $D$

      2. (2)

$T$ is pointwise $\alpha$-firmly nonexpansive at $y$ for all constants
$\alpha\in[\underline{\alpha},1]$ on $D$

      3. (3)

$(1+\lambda)d(Tx,Ty)^{2}\leq(1-\lambda)d(x,y)^{2}+2\lambda\Delta_{T}^{(2,2)}(x,y)\quad\forall
x\in D,\forall\lambda\in[0,\tfrac{1-\underline{\alpha}}{\underline{\alpha}}];$

    4. (d)

$T$ satisfying (2) is $\alpha$-firmly nonexpansive with constant
$\alpha=\tfrac{1}{1+\lambda}$ on $D$.

###### Proof.

(i). Fix $y\in\operatorname{Fix}T$. Equation (14) follows directly from (4),
from which the rest of the claim is immediate.

(ii). This is immediate from the definition and part (i).

(iii). This follows immediately from parts (i) and (ii).

(iv) Starting with (16), by the characterization of $p$-uniformly convex
spaces (1)

$\displaystyle d(Tx,y)^{p}$ $\displaystyle\leq$ $\displaystyle
d((1-\lambda)x\oplus\lambda Tx,y)^{p}$ $\displaystyle\leq$
$\displaystyle(1-\lambda)d(x,y)^{p}+\lambda
d(Tx,y)^{p}-(1-\lambda)\lambda\tfrac{c}{2}d(Tx,x)^{p}$

for all $x\in D$ and some $\lambda\in(0,1)$. Rearranging terms yields

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

When $y\in\operatorname{Fix}T$, by part (ii), this is equivalent to $T$ being
pointwise $\alpha$-firmly nonexpansive at $y$ with constant
$\alpha=\tfrac{1}{\lambda+1}$ on $D$.

(v)(a) This is a direct consequence of the inequality

$\Delta^{(2,2)}(x,y,u,v)\leq d(x,y)d(u,v)$ (17)

(see [21, Theorem 2.3.1] or [26, Lemma 2.1]).

(v)(b) By (8) and part (v)(a)

$\displaystyle\psi^{(2,2)}_{T}(x,y)$ $\displaystyle=$ $\displaystyle
d(x,y)^{2}+d(Tx,Ty)^{2}-2\Delta^{(2,2)}_{T}(x,y)$ $\displaystyle\geq$
$\displaystyle d(x,y)^{2}+d(Tx,Ty)^{2}-2d(x,y)d(Tx,Ty)$ $\displaystyle=$
$\displaystyle\left(d(x,y)-d(Tx,Ty)\right)^{2}\geq 0$

for all $x,y\in G$, as claimed.

(v)(c) By part (v)(b) if $T$ is pointwise $\alpha$-firmly nonexpansive at $y$
with constant $\underline{\alpha}$ on $D$ then

$\displaystyle d(Tx,Ty)^{2}\leq
d(x,y)^{2}-\tfrac{1-\underline{\alpha}}{\underline{\alpha}}\psi^{(2,2)}_{T}(x,y)\quad\forall
x\in D$ $\displaystyle\underset{(2)}{\overset{{(1)}}{\iff}}$ $\displaystyle
d(Tx,Ty)^{2}\leq
d(x,y)^{2}-\tfrac{1-\alpha}{\alpha}\psi^{(2,2)}_{T}(x,y)\quad\forall x\in
D,\forall\alpha\in[\underline{\alpha},1]$ $\displaystyle\iff$ $\displaystyle
d(Tx,Ty)^{2}\leq d(x,y)^{2}-\lambda\psi^{(2,2)}_{T}(x,y)\quad\forall x\in
D,\forall\lambda\in[0,\tfrac{1-\underline{\alpha}}{\underline{\alpha}}]$
$\displaystyle\underset{(3)}{\overset{{(2)}}{\iff}}$
$\displaystyle(1+\lambda)d(Tx,Ty)^{2}\leq(1-\lambda)d(x,y)^{2}+2\lambda\Delta^{(2,2)}_{T}(x,y)\quad\forall
x\in D,\forall\lambda\in[0,\tfrac{1-\underline{\alpha}}{\underline{\alpha}}]$

where the last equivalence follows from (8).

(v)(d) For fixed $\lambda\in[0,1)$ (13) in the proof of Proposition 3 yields

$\displaystyle(1+\lambda)d(Tx,Ty)^{2}$ $\displaystyle\leq$
$\displaystyle(1-\lambda)d(x,y)^{2}+2\lambda\Delta^{(2,2)}_{T}(x,y),\quad\forall
x,y\in D.$

By (v)(c), this implies that $T$ is $\alpha$-firmly nonexpansive at all $y\in
D$ for any constant $\alpha\in[\tfrac{1}{1+\lambda},1]$ on $D$. This completes
the proof. ∎

######  Remark 5.

Property (15) is a specialization of Property (P1) of [3] to $\alpha$-firmly
nonexpansive mappings (as we define them) on $p$-uniformly convex spaces.

Closedness and convexity of the set of fixed points of nonexpansive mappings
is easily established. Note, however, that convexity of the fixed point set
depends on convexity of the domain. In Section 4.2 we will not require
convexity of the domain.

######  Lemma 6.

Let $(G,d)$ be a $p$-uniformly convex metric space with constant $c>0$ and let
$D\subseteq G$ be closed and convex. Let $T:G\to G$ be pointwise nonexpansive
at all $y\in\operatorname{Fix}T\cap D\neq\emptyset$ on $D$. Then
$\operatorname{Fix}T\cap D$ is a closed and convex set.

###### Proof.

This statement for $T$ a nonexpansive (not pointwise) mapping on a uniquely
geodesic space is in [2, Lemma 6.2]. Their proof also works for pointwise
nonexpansive mappings. ∎

In [3] the central property of asymptotic regularity of a mapping $T$ at its
fixed points hinges on (i) existence of fixed points, and (ii) the validity of
inequality (15) at all $y\in\operatorname{Fix}T$. Proposition 4(ii) shows that
these two requirements are equivalent to $T$ being quasi $\alpha$-firmly
nonexpansive. We show in Theorem 27 that, as a consequence of the next theorem
on asymptotic regularity, pointwise $\alpha$-firm nonexpansiveness at
reasonable subsets of fixed points is all that is needed to achieve weak
convergence of fixed point iterations.

######  Theorem 7.

Let $(G,d)$ be a $p$-uniformly convex space, let $D\subset G$, and let $T:G\to
G$ with $\operatorname{Fix}T\cap D$ nonempty and $T(D)\subseteq D$. Suppose
further that $T$ is pointwise $\alpha$-firmly nonexpansive at all
$y\in\operatorname{Fix}T\cap D$ on $D$. Then given any starting point
$x_{0}\in D$ the sequence $(x_{k})_{k\in\mathbb{N}}$ defined by
$x_{k+1}=Tx_{k}$ is asymptotically regular on $D$.

###### Proof.

By Proposition 4(ii) and Remark 5, the statement is a specialization of [3,
Theorem 3.1] to the case of just a single operator. ∎

We show below, that compositions and convex combinations of (quasi)
$\alpha$-firmly nonexpansive mappings are quasi $\alpha$-firmly nonepxansive.
Therefore, by the theorem above, fixed point iterations of such compositions
and convex combinations are asymptotically regular.

###  3.2 Calculus of Nonexpansive Operators

Nonexpansiveness is preserved under compositions and, with some restrictions,
under convex combinations, as the next result shows.

######  Theorem 8.

Let $D\subset G$ where $(G,d)$ is a $p$-uniformly convex space with constant
$c>0$ and let $T_{1},T_{2}:D\to G$.

  1. (i)

If $\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}\neq\emptyset$ then any
convex combination of $T_{2}$ and $T_{1}$ is pointwise nonexpansive at
$y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$ on $D$ whenever
$T_{2}$ and $T_{1}$ are pointwise nonexpansive there.

  2. (ii)

When $(G,d)$ is a CAT(0) space, (that is, $p=2$, and $c=2$), then any convex
combination of $T_{2}$ and $T_{1}$ is pointwise nonexpansive at $y\in D$ on
$D$ whenever $T_{2}$ and $T_{1}$ are pointwise nonexpansive there.

  3. (iii)

For $D_{1}:=\\{z~{}|~{}z=T_{1}y,y\in D\\}$ let $T_{2}:D_{1}\to G$ be pointwise
nonexpansive at $T_{1}y\in D_{1}$ on $D_{1}$ and let $T_{1}$ be pointwise
nonexpansive at $y\in D$. Then the composition $T_{2}\circ T_{1}$ is pointwise
nonexpansive at $y$ on $D$.

In particular, the set of all nonexpansive operators in CAT(0) spaces is
closed under compositions and convex combinations.

###### Proof.

(i). Let $\lambda\in(0,1)$ and define
$T_{\lambda}:=(1-\lambda)T_{2}\oplus\lambda T_{1}$. Applying (1) first to
$T_{\lambda}y$ and then to $T_{\lambda}x$ yields

$\displaystyle d(T_{\lambda}x,T_{\lambda}y)^{p}$ $\displaystyle\leq$
$\displaystyle(1-\lambda)d(T_{\lambda}x,T_{2}y)^{p}+\lambda
d(T_{\lambda}x,T_{1}y)^{p}-\tfrac{c}{2}\lambda(1-\lambda)d(T_{2}y,T_{1}y)^{p}$
(18) $\displaystyle\leq$
$\displaystyle(1-\lambda)^{2}d(T_{2}x,T_{2}y)^{p}+\lambda^{2}d(T_{1}x,T_{1}y)^{p}+\lambda(1-\lambda)\left(d(T_{1}x,T_{2}y)^{p}+d(T_{2}x,T_{1}y)^{p}\right)$
$\displaystyle\qquad-\frac{\lambda(1-\lambda)c}{2}\left(d(T_{2}x,T_{1}x)^{p}+d(T_{2}y,T_{1}y)^{p}\right).$

For $y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$ this yields

$\displaystyle d(T_{\lambda}x,T_{\lambda}y)^{p}$ $\displaystyle\leq$
$\displaystyle(1-\lambda)d(T_{2}x,y)^{p}+\lambda d(T_{1}x,y)^{p}$
$\displaystyle\leq$ $\displaystyle(1-\lambda)d(x,y)^{p}+\lambda
d(x,y)^{p}=d(x,y)^{p}\quad\forall x\in D,$

where the last inequality uses pointwise nonexpansiveness of $T_{1}$ and
$T_{2}$ at $y$. Therefore $(1-\lambda)T_{2}\oplus\lambda T_{1}$ is pointwise
nonexpansive at $y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$ on
$D$ for all $\lambda\in[0,1]$, as claimed.

(ii). Let $\lambda\in(0,1)$ and define
$T_{\lambda}:=(1-\lambda)T_{2}\oplus\lambda T_{1}$. Applying (18) with $p=2$
and $c=2$ yields

$\displaystyle d(T_{\lambda}x,T_{\lambda}y)^{2}$
$\displaystyle\leq(1-\lambda)^{2}d(T_{2}x,T_{2}y)^{2}+\lambda^{2}d(T_{1}x,T_{1}y)^{2}$
$\displaystyle+(1-\lambda)\lambda(d(T_{2}x,T_{1}y)^{2}+d(T_{1}x,T_{2}y)^{2}-d(T_{2}y,T_{1}y)^{2}-d(T_{2}x,T_{1}x)^{2})$
$\displaystyle=(1-\lambda)^{2}d(T_{2}x,T_{2}y)^{2}+\lambda^{2}d(T_{1}x,T_{1}y)^{2}+(1-\lambda)\lambda\Delta^{(2,2)}(T_{2}x,T_{2}y,T_{1}x,T_{1}y)$

for any $x\in D$, where $\Delta^{(2,2)}$ is defined by (6). On the other hand
$(G,d)$ is a CAT(0)-space, so (17) holds, and in particular,

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

for any $x,y\in G$. Therefore

$d(T_{\lambda}x,T_{\lambda}y)^{2}\leq\left((1-\lambda)d(T_{2}x,T_{2}y)+\lambda
d(T_{1}x,T_{1}y)\right)^{2}\quad\forall x\in D.$

By assumption both $T_{2}$ and $T_{1}$ are pointwise nonexpansive at $y$ on
$D$, so

$d(T_{\lambda}x,T_{\lambda}y)^{2}\leq((1-\lambda)d(x,y)+\lambda
d(x,y))^{2}=d(x,y)^{2}\quad\forall x\in D$

and hence $d(T_{\lambda}x,T_{\lambda}y)\leq d(x,y)$ for all $x\in D$ as
claimed.

(iii). Let $\overline{T}:=T_{2}\circ T_{1}$. Then

$\displaystyle d(\overline{T}x,\overline{T}y)=d(T_{2}T_{1}x,T_{2}T_{1}y)\leq
d(T_{1}x,T_{1}y)\quad\forall T_{1}x\in D_{1}$ $\displaystyle\iff$
$\displaystyle d(\overline{T}x,\overline{T}y)\leq d(T_{1}x,T_{1}y)\quad\forall
x\in D$

since $T_{2}$ is pointwise nonexpansive at $T_{1}y\in D_{1}$ on $D_{1}$. But
since $T_{1}$ is pointwise nonexpansive at $y$ on $D$ this yields

$d(T_{1}x,T_{1}y)\leq d(x,y)\quad\forall x\in D$

which establishes the claim and completes the proof. ∎

###  3.3 Compositions of $\alpha$-Firmly Nonexpansive Operators

In this section we show how the composition of two $\alpha$-firmly
nonexpansive operators is again $\alpha$-firmly nonexpansive. In general this
does not hold, but the property does hold pointwise at fixed points of the
composite operator, and for many applications this is all that is needed. The
next lemma relates the fixed points of compositions of $\alpha$-firmly
nonexpansive mappings to the intersection of the fixed points of the
individual mappings.

######  Lemma 9.

Let $(G,d)$ be a metric space.

  1. (i)

Let $T_{2},T_{1}:G\to G$ satisfy
$\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}\neq\emptyset$. If $T_{2}$
is pointwise nonexpansive at all
$y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}\neq\emptyset$ on
$D\subset G$ where $\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}\subset
D$, and $T_{1}$ is pointwise $\alpha$-firmly nonexpansive at all
$y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$ on $D$, then
$\operatorname{Fix}T_{2}T_{1}=\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$.

  2. (ii)

Let $\\{T_{1},T_{2},\dots,T_{m}\\}$ be a collection of quasi $\alpha$-firmly
nonexpansive mappings, each with respective constants $\alpha_{j}$ on
$D\supset\cap_{j=1}^{m}\operatorname{Fix}T_{j}\neq\emptyset$. Then
$\operatorname{Fix}\left(T_{m}\circ T_{m-1}\circ\cdots\circ
T_{1}\right)=\cap_{j=1}^{m}\operatorname{Fix}T_{j}$.

###### Proof.

(i) The inclusion
$\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}\subseteq\operatorname{Fix}T_{2}T_{1}$
is obvious. Now let $x$ be any point is $\operatorname{Fix}T_{2}T_{1}$ and $y$
any point in $\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$. There are
three mutually exclusive cases. First let $T_{1}x\in\operatorname{Fix}T_{2}$
then $T_{1}x=T_{2}T_{1}x=x$ implies
$x\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$. Second let
$x\in\operatorname{Fix}T_{1}$ then $x=T_{2}T_{1}x=T_{2}x$ implies
$x\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$. Finally, let
$x\notin\operatorname{Fix}T_{1}$ and $T_{1}x\notin\operatorname{Fix}T_{2}$.
This yields

$\displaystyle d(x,y)^{p}=d(T_{2}T_{1}x,T_{2}y)^{p}\leq d(T_{1}x,y)^{p}$
$\displaystyle=d(T_{1}x,T_{1}y)^{p}$ $\displaystyle\leq
d(x,y)^{p}-\frac{1-\alpha}{\alpha}\tfrac{c}{2}d(x,T_{1}x)^{p}$

where the first inequality follows from pointwise nonexpansiveness of $T_{2}$
at $y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$ on $D$, and the
second inequality follows from the assumption that $T_{1}$ is pointwise
$\alpha$-firmly nonexpansive at
$y\in\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$ on $D$ and
Proposition 4(ii). But this implies that $d(x,y)^{p}<d(x,y)^{p}$, which is
impossible. Therefore
$\operatorname{Fix}T_{2}T_{1}\subseteq\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$
as claimed.

(ii) In light of Remark 5, this follows immediately from [3, Proposition 2.1].
∎

######  Lemma 10.

Let $(G,d)$ be a $p$-uniformly convex space with constant $c$ and let
$D\subset G$. Let $T_{1}:D\to G$ be pointwise $\alpha$-firmly nonexpansive at
$y$ on $D$ with constant $\alpha_{1}$ and let $T_{2}:D_{1}\to G$ be pointwise
$\alpha$-firmly nonexpansive at $T_{1}y$ on $D_{1}$ with constant $\alpha_{2}$
where $D_{1}:=\\{T_{1}x~{}|~{}x\in D\\}$. Then the composition
$\overline{T}:=T_{2}\circ T_{1}$ is pointwise $\alpha$-firmly nonexpansive at
$y$ on $D$ whenever

$\exists~{}\overline{\alpha}\in(0,1):\quad\frac{1-\alpha_{1}}{\alpha_{1}}\psi^{(p,c)}_{T_{1}}(x,y)+\frac{1-\alpha_{2}}{\alpha_{2}}\psi^{(p,c)}_{T_{2}}(T_{1}x,T_{1}y)\geq\frac{1-\overline{\alpha}}{\overline{\alpha}}\psi^{(p,c)}_{\overline{T}}(x,y)\quad\forall
x\in D.$ (19)

###### Proof.

Since $T_{2}$ is pointwise $\alpha$-firmly nonexpansive at $T_{1}y$ with
constant $\alpha_{2}$ on $D_{1}$ we have

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

where $\psi^{(p,c)}_{T_{2}}$ is defined by (4). On the other hand,
$\\{x~{}|~{}T_{1}x\in D_{1}\\}=D$, and since $T_{1}$ is pointwise
$\alpha$-firmly nonexpansive at $y$ on $D$ with constant $\alpha_{1}$ we have

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

Whenever (19) holds, we can conclude that

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

∎

######  Theorem 11.

Let $(G,d)$ be a $p$-uniformly convex space. Let $T_{1}:D\to G$ for $D\subset
G$, $T_{2}:D_{1}\to G$ for $D_{1}:=\\{T_{1}x~{}|~{}x\in D\\}$, define
$\overline{T}:=T_{2}\circ T_{1}$ and let
$\operatorname{Fix}\overline{T}\subset D$ and
$\operatorname{Fix}T_{1}\cap\operatorname{Fix}T_{2}$ both be nonempty. If
$T_{1}$ is pointwise $\alpha$-firmly nonexpansive at all
$y\in\operatorname{Fix}\overline{T}$ with constant $\alpha_{1}$ on $D$, and if
$T_{2}$ is pointwise $\alpha$-firmly nonexpansive at all
$y\in\operatorname{Fix}\overline{T}$ with constant $\alpha_{2}$ on $D_{1}$,
then the composite operator $\overline{T}$ is quasi $\alpha$-firmly
nonexpansive on $D$ with constant

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

###### Proof.

By Lemma 10, it suffices to show (19) at all points
$y\in\operatorname{Fix}\overline{T}$. First, note that by Lemma 9,
$\operatorname{Fix}\overline{T}=\operatorname{Fix}T_{2}\cap\operatorname{Fix}T_{1}$,
so by (14) we have $\psi^{(p.c)}_{T_{1}}(x,y)=\tfrac{c}{2}d(x,T_{1}x)^{p}$,
$\psi^{(p.c)}_{T_{2}}(T_{1}x,T_{1}y)=\tfrac{c}{2}d(T_{1}x,\overline{T}x)^{p}$,
and $\psi^{(p.c)}_{\overline{T}}(x,y)=\tfrac{c}{2}d(x,\overline{T}x)^{p}$.
Then whenever $y\in\operatorname{Fix}\overline{T}$ the inequality (19)
simplifies to

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

where $\kappa_{1}:=\frac{1-\alpha_{1}}{\alpha_{1}}$,
$\kappa_{2}:=\frac{1-\alpha_{2}}{\alpha_{2}}$ 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_{1}x,(1-t)x\oplus
t\overline{T}x)^{p}$ (22) $\displaystyle\leq$
$\displaystyle(1-t)d(T_{1}x,x)^{p}+td(T_{1}x,\overline{T}x)^{p}\quad\forall
x\in G,\forall t\in(0,1).$

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

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

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

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

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

######  Remark 12.

The fact that quasi $\alpha$-firm nonexpansiveness hinges on inequality (19)
or, more specifically (21), is a property of the individual operators $T_{2}$
and $T_{1}$. Whether or not the subsequent inequality (21) holds is a property
of the space and is entirely independent of the operators. Also note that the
constant $\overline{\alpha}$ given in (20) corresponds exactly to the constant
found in [7, Proposition 4.44] for mappings on Hilbert spaces.

######  Corollary 13 (finite compositions of quasi $\alpha$-firmly
nonexpansive operators are quasi $\alpha$-firmly nonexpansive).

Let $(G,d)$ be a $p$-uniformly convex space. Let $T_{1}:D_{1}\to G$ where
$D_{1}\subset G$ and for $j=2,3,\dots,m$ let $T_{j}:D_{j}\to G$ for
$D_{j}:=\\{T_{j-1}x~{}|~{}x\in D_{j-1}\\}$. If $T_{j}$ is quasi
$\alpha$-firmly nonexpansive with constant $\alpha_{j}$ on $D_{j}$
($j=1,2,\dots,m$) and $\operatorname{Fix}(T_{m}\circ T_{m-1}\circ\cdots\circ
T_{1})\subset D_{1}$ is nonempty, then the composite operator $T:=T_{m}\circ
T_{m-1}\circ\cdots\circ T_{1}$ is quasi $\alpha$-firmly nonexpansive on
$D_{1}$ with constant given recursively by

$\overline{\alpha}_{m}=\frac{\overline{\kappa}_{m-1}+\kappa_{m}}{\frac{c}{2}\overline{\kappa}_{m-1}\kappa_{m}+\overline{\kappa}_{m-1}+\kappa_{m}}\quad(m\geq
3)$ (24a) where $\displaystyle\overline{\kappa}_{j}$ $\displaystyle=$
$\displaystyle\frac{1-\overline{\alpha}_{j}}{\overline{\alpha}_{j}}\quad(j\geq
2)$ (24b) $\displaystyle\kappa_{j}$ $\displaystyle:=$
$\displaystyle\frac{1-\alpha_{j}}{\alpha_{j}}\quad(j\geq 1)$ (24c)
$\displaystyle\overline{\alpha}_{2}$ $\displaystyle:=$
$\displaystyle\frac{\kappa_{1}+\kappa_{2}}{\tfrac{c}{2}\kappa_{1}\kappa_{2}+\kappa_{1}+\kappa_{2}}.$
(24d)

###### Proof.

The result follows from Theorem 11 and an elementary induction argument. ∎

######  Remark 14.

It is well known that the composition of two firmly nonexpansive mappings (for
instance, projectors) in a Hilbert space ($\alpha=1/2$, $p=2$, and $c=2$) are
$\alpha$-firmly nonexpansive with constant $\overline{\alpha}=\tfrac{2}{3}$.
Theorem 11 yields this as a special case.

###  3.4 Convex Combinations of $\alpha$-Firmly Nonexpansive Operators

In this chapter we see that $\alpha$-formnes ist preserved under $p$-convex
combinations of operators. To prove this we use the concept of $p$-uniformly
convex functions.

######  Definition 15.

Let $(G,d)$ be a $p$-uniformly convex space. A function $f\colon
G\rightarrow\mathbb{R}$ is said to be $p$-uniformly convex with constant $m>0$
if

$\displaystyle f(tx\oplus(1-t)y)\leq
tf(x)+(1-t)f(y)-\frac{1}{2}mt(1-t)d(x,y)^{p}\quad\forall x,y\in G,~{}\forall
t\in[0,1].$

######  Remark 16.

It is obvious from the definition that the sum of two $p$-uniformly convex
functions with constants $m_{1}$ and $m_{2}$ is $p$-uniformly convex with
constant $m=m_{1}+m_{2}$. For any $y\in G$ the distance function $x\mapsto
d(x,z)$ is a $p$-uniformly convex function with constant $m=c$ if $(G,d)$ is a
$p$-uniformly convex space with constant $c>0$.

######  Lemma 17.

Let $f\colon G\rightarrow\mathbb{R}$ be $p$-uniformly convex with constant
$m>0$ and $x\in\operatorname{argmin\,}f\neq\emptyset$. Then

$\displaystyle f(y)\geq f(x)+\frac{m}{2}d(x,y)^{p}\quad\forall y\in G\text{
and }x\in\operatorname{argmin\,}f.$

###### Proof.

Let $x\in\operatorname{argmin\,}f$ and $f$ be $p$-uniformly convex with
constant $m$. Then

$\displaystyle(1-t)f(y)$ $\displaystyle\geq
f(tx\oplus(1-t)y)-tf(x)+\frac{m}{2}t(1-t)d(x,y)^{p}$
$\displaystyle\geq(1-t)f(x)+\frac{m}{2}t(1-t)d(x,y)^{p}$

by the definition of $p$-uniformly convex functions and
$x\in\operatorname{argmin\,}f$. Now divide by $1-t$ and take the limit
$t\rightarrow 1$ to obtain the claim. ∎

The $p$-convex combination of $n$ points $x_{1},\ldots,x_{n}$ with weights
$\omega_{1},\omega_{2},\ldots,\omega_{n}\in[0,1]$ such that
$\sum_{i=1}^{n}\omega_{i}=1$ is denoted
${}_{p}\\!\\!\oplus_{i}^{n}\omega_{i}x_{i}$ where

${}_{p}\\!\\!\oplus_{i}^{n}\omega_{i}x_{i}:=\operatorname{argmin\,}_{y}\sum_{i=1}^{n}\omega_{i}d(y,x_{i})^{p}.$
(25)

For the convex combination of Operators $T_{i}$ is defined by

$\displaystyle\mathscr{T}x\coloneqq\operatorname{argmin\,}_{y}\sum_{i=1}^{n}\omega_{i}d(y,T_{i}x)^{p}$
(26)

and we denote $\mathscr{T}=_{p}\\!\\!\oplus_{i}^{n}\omega_{i}T_{i}x$.

Due to the next proposition $p$-convex combinations exist and are unique in
complete p-uniformly convex spaces.

######  Proposition 18.

Let $(G,d)$ be a complete $p$-uniformly convex space with constant $c>0$. Then
the $\operatorname{argmin\,}$ in (25) exists and is unique.

This is a special case of existence and uniqueness of p-barycenters in
$p$-uniform convex spaces (see [24, Lemma 3.5].

###### Proof.

Let $y_{k}$ be a minimizing sequence of
$y\mapsto\sum_{i=1}^{n}\omega_{i}d(y,x_{i})^{p}$. Then (1) yields

$\displaystyle\sum_{i=1}^{n}\omega_{i}d(ty_{k}\oplus(1-t)y_{l},x_{i})^{p}\leq\sum_{i=1}^{n}\omega_{i}[td(y_{k},x_{i})^{p}+(1-t)d(y_{l},x_{i})^{p}-\frac{c}{2}t(1-t)d(y_{k},y_{l})^{p}]$

rearranging with $t=\frac{1}{2}$ and yields

$\displaystyle\limsup_{k,l\rightarrow\infty}\frac{c}{8}d(y_{k},y_{l})^{p}$
$\displaystyle\leq\limsup_{k,l\rightarrow\infty}\frac{1}{2}\sum_{i=1}^{n}\omega_{i}d(y_{k},x_{i})^{p}+\frac{1}{2}\sum_{i=1}^{n}\omega_{i}d(y_{l},x_{i})^{p}-\sum_{i=1}^{n}\omega_{i}d(\frac{1}{2}y_{k}\oplus\frac{1}{2}y_{l},x_{i})^{p}$
$\displaystyle\leq(\frac{1}{2}+\frac{1}{2}-1)\inf_{y}\sum_{i=1}^{n}\omega_{i}d(y,x_{i})^{p}=0.$

Hence $y_{k}$ is a Cauchy sequence and converges to a unique limit that is a
minimizer of (25). ∎

######  Definition 19 ([24]).

Let $(G,d)$ be a geodesic space. Let $\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.$

Examples for symmetric perpendicular spaces are $CAT(0)$ spaces and
$CAT(\kappa)$ spaces for $\kappa>0$ with diameter strictly less than
$\frac{\pi}{2\sqrt{\kappa}}$ [24, Theorem 2.11].

######  Theorem 20.

Let $(G,d)$ be a complete, p-uniformly convex space and for $i=1,2,\dots,n$
let the mappings $T_{i}:G\rightarrow G$ be pointwise $\alpha$-firmly
nonexpansive on $\operatorname{Fix}T_{i}$ with constant $\alpha_{i}$. Then for
$\mathscr{T}$ defined by (26),
$\cap_{i\in\\{1,\ldots,n\\}}\operatorname{Fix}T_{i}\subset\operatorname{Fix}\mathscr{T}$.
Suppose in addition that
$\cap_{i\in\\{1,\ldots,n\\}}\operatorname{Fix}T_{i}\neq\emptyset$ and $G$ is
symmetric perpendicular, then
$\operatorname{Fix}\mathscr{T}=\cap_{i\in\\{1,\ldots,n\\}}\operatorname{Fix}T_{i}$.

###### Proof.

The inclusion
$\operatorname{Fix}\mathscr{T}\supset\cap_{i=1}^{n}\operatorname{Fix}T_{i}$ is
clear. To see the converse inclusion when the intersection
$\cap_{i\in\\{1,\ldots,n\\}}\operatorname{Fix}T_{i}\neq\emptyset$ and $G$ is
symmetric perpendicular, let $x\notin\cap_{i=1}^{n}\operatorname{Fix}T_{i}$
and $y\in\cap_{i=1}^{n}\operatorname{Fix}T_{i}$. For at least one
$j\in\\{1,\ldots,n\\}$ we have $x\notin\operatorname{Fix}T_{j}$. We use a
contradiction to prove $P_{[x,y]}(T_{j}x)\neq x$. Therefore assume that
$P_{[x,y]}(T_{j}x)=x$. Then $[x,T_{j}x]\perp_{x}[x,y]$ and by symmetric
perpendicularity $[x,y]\perp_{x}[x,T_{j}x]$. Hence $d(y,x)\leq d(y,T_{j}x)$
this contradicts $d^{p}(y,T_{j}x)\leq
d^{p}(x,y)-\frac{1-\alpha_{i}}{\alpha_{j}}\frac{c}{2}d^{p}(T_{j}x,x)<d^{p}(y,x)$.
Therefore $t=0$ is not a minimum of the convex function $t\mapsto
g_{j}(t)\coloneqq d(\mathscr{T}x,ty\oplus(1-t)x)^{p}$ on the interval $[0,1]$
and the right side derivative $d^{+}g_{j}(0)<0$ for all $j$ with $T_{j}x\neq
x$. For $i$ with $T_{i}x=x$ we have $g_{i}(t)=t^{p}$ and hence
$d^{+}g_{i}(0)=0$. So the function

$\displaystyle
g(t)\coloneqq\sum_{i=1}^{n}\omega_{i}d(ty\oplus(1-t)x,T_{i}x)^{p}=\sum_{i=1}^{n}\omega_{i}g_{i}(t)$

has $d^{+}g(0)<0$, and hence $x$ can not be a minimum of

$\displaystyle z\mapsto\sum_{i=1}^{n}\omega_{i}d(z,T_{i}x)^{p}.$

This shows that $\mathscr{T}x\neq x$ and completes the proof. ∎

######  Theorem 21 (averages of pointwise $\alpha$-firm mappings are pointwise
$\alpha$-firm).

Let $(G,d)$ be a $p$-uniformly convex space with constant $c>0$ that is
symmetric perpendicular. Let $T_{i}$ be pointwise $\alpha$-firmly nonexpansive
with constant $\alpha_{i}$ ($i=1,2,\dots,n$) at all points in
$\cap_{i=1}^{n}\operatorname{Fix}T_{i}\neq\emptyset$ on $D$, and
$\omega_{i}\in[0,1]$ with $\sum_{i=1}^{n}\omega_{i}=1$. Then $\mathscr{T}$
defined by (26) is pointwise $\alpha$-firmly nonexpansive at all
$y\in\operatorname{Fix}\mathscr{T}$ on $D$ with

$\displaystyle\alpha=\max_{i}\alpha_{i}$

###### Proof.

Let $x\in D$. By convexity of $d(\cdot,y)^{p}$ and Jensen’s inequality [24,
Theorem 4.1] for $p$-uniformly convex spaces with the symmetric perpendicular
property we have

$\displaystyle d(\mathscr{T}x,\mathscr{T}y)^{p}$
$\displaystyle=d(~{}_{p}\\!\\!\oplus_{i}^{n}\omega_{i}T_{i}x,y)^{p}$ (27a)
$\displaystyle\leq~{}_{p}\\!\\!\oplus_{i}^{n}\omega_{i}d(T_{i}x,y)^{p}$ (27b)
$\displaystyle=\operatorname{argmin\,}_{t\in\mathbb{R}}\sum_{i=1}^{n}\omega_{i}|t-d(T_{i}x,y)^{p}|^{p}$
(27c)
$\displaystyle\leq\operatorname{argmin\,}_{t\in\mathbb{R}}\sum_{i=1}^{n}\omega_{i}|t-(d(x,y)^{p}-\frac{1-\alpha_{i}}{\alpha_{i}}\frac{c}{2}d(x,T_{i}x)^{p})|^{p}$
(27d)
$\displaystyle\leq\operatorname{argmin\,}_{t\in\mathbb{R}}\sum_{i=1}^{n}\omega_{i}|t-(d(x,y)^{p}-\frac{1-\alpha}{\alpha}\frac{c}{2}d(x,T_{i}x)^{p})|^{p}$
(27e)
$\displaystyle=d(x,y)^{p}-\operatorname{argmin\,}_{t\in\mathbb{R}}\sum_{i=1}^{n}\omega_{i}|t-\frac{1-\alpha}{\alpha}\frac{c}{2}d(x,T_{i}x)^{p}|^{p}$
(27f) $\displaystyle\leq
d(y,x)^{p}-\frac{1-\alpha}{\alpha}\frac{c}{2}d(x,~{}_{p}\\!\\!\oplus_{i}^{n}\omega_{i}T_{i}x)^{p}$
(27g)
$\displaystyle=d(y,x)^{p}-\frac{1-\alpha}{\alpha}\frac{c}{2}d(x,\mathscr{T}x)^{p}$
(27h)

For the estimation in (27d) and (27e) we used the property that
$\operatorname{argmin\,}_{t\in\mathbb{R}}\sum_{i=1}^{n}\omega_{i}|t-\lambda_{i}|^{p}$
is increasing in every constant $\lambda_{i}$. This can be easily concluded
since $\sum_{i=1}^{n}\omega_{i}|t-\lambda_{i}|^{p}$ is a convex function and

$\displaystyle\partial_{t}\sum_{i=1}^{n}\omega_{i}|t-\lambda_{i}|^{p}=\sum_{i=1}^{n}\omega_{i}p|t-\lambda_{i}|^{p-1}sgn(t-\lambda)$

is decreasing in every $\lambda_{j}$ for fixed $t$. ∎

###  3.5 Constructing $\alpha$-firmly nonexpansive operators

In a complete $p$-uniformly convex space the $p$-proximal mapping of a proper
function lower semicontinuous $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(x,y)^{p}.$ (28)

The $\operatorname{argmin\,}$ in (28) exists and is unique if $f$ is proper,
lsc and convex [19, Proposition 2.7]. This is a very natural definition of the
proximal mapping, as the corresponding Moreau-Yosida envelope given by

$\displaystyle e^{p}_{f,\lambda}(x)\coloneqq\inf_{y\in
G}f(y)+\frac{1}{p\lambda^{p-1}}d(x,y)^{p}$

satisfies the semigroup property
$e^{p}_{(e^{p}_{f,\lambda}),{\mu}}=e^{p}_{f,\lambda+\mu}$ (see [20] [25]).

######  Proposition 22 ([19, Lemma 2.8]).

Let $(G,d)$ be a p-uniformly convex space with parameter $c>0$, $\lambda>0$
and $f\colon G\rightarrow(-\infty,+\infty]$ be a proper, convex and lower
semicontinuous function. Then for all $x,y\in G$ we have

$\displaystyle
d(\operatorname{prox}^{p}_{f,\lambda}(x),\operatorname{prox}^{p}_{f,\lambda}(y))^{p}\leq\frac{1}{c}[d(v,y)^{p}+d(x,w)^{p}-d(x,v)^{p}-d(y,w)^{p}]=\Delta_{\operatorname{prox}^{p}_{f,\lambda}}^{(p,\frac{4}{c})}(x,y)$

for $v=\operatorname{prox}^{p}_{f,\lambda}(x)$ and
$w=\operatorname{prox}^{p}_{f,\lambda}(y)$.

###### Proof.

This follows directly from [19, Lemma 2.8] with $\mu=\frac{p\lambda}{2}$. ∎

######  Corollary 23 (proximal mappings are almost $\alpha$-firm).

Let $(G,d)$ be a p-uniformly convex space with parameter $c\in(1,2]$,
$\lambda>0$ and let $f\colon G\rightarrow(-\infty,+\infty]$ be a proper,
convex, and lsc. Then $\operatorname{prox}^{p}_{f,\lambda}$ is almost
$\alpha$-firmly nonexpansive with constant $\alpha_{c}=\frac{c-1}{c}$ and
violation $\epsilon_{c}=\frac{2-c}{c-1}$.

###### Proof.

Let $x\in\operatorname{Fix}\operatorname{prox}^{p}_{f,\lambda}$, $y\in G$ and
$w=\operatorname{prox}^{p}_{f,\lambda}(y)$. Then by Proposition 22 and
elementary calculations

$\displaystyle
d(x,w)^{p}\leq\frac{1}{c-1}(d(x,y)^{p}-d(y,w)^{p})=(1+\epsilon_{c})d(x,y)^{p}-\frac{1-\alpha_{c}}{\alpha_{c}}d(y,w)^{p}.$

∎

######  Remark 24.

In the special case $c=2$ and hence $p=2$ the violation is $\epsilon_{2}=0$
and $\operatorname{prox}^{2}_{f,\lambda}$ is quasi $\alpha$-firm with constant
$\alpha=\frac{1}{2}$.

######  Proposition 25 (projectors are pointwise firmly nonexpansive).

Let $(G,d)$ be a complete, symmetric perpendicular $p$-uniformly convex space,
$C\subset G$ a convex subset. The metric projection onto the set $C$, denoted
$P_{C}$, is pointwise $\alpha$-firmly nonexpansive at any $y\in C$ with
constant $\alpha=\frac{1}{2}$.

###### Proof.

First note that $[x,P_{C}x]\perp_{P_{C}x}[y,P_{C}x]$ since $P_{C}$ is the
metric projector. Then $[y,P_{C}x]\perp_{P_{C}x}[x,P_{C}x]$ by symmetric
perpendicularity of the space. Hence $t=0$ is a minimum of the function
$t\mapsto d(tx\oplus(1-t)P_{C}x,y)^{p}$ on the interval $[0,1]$ and

$\displaystyle d(tx\oplus(1-t)P_{C}x,y)^{p}\leq
td(x,y)^{p}+(1-t)d(P_{C}x,y)^{p}-\frac{c}{2}t(1-t)d(x,P_{C}x)^{p},$

with equality at $t=0$. Now $t=0$ has to be a minimum of the right hand side
and

$\displaystyle 0$
$\displaystyle\leq~{}\derivative{t}\Big{|}_{t=0}td(x,y)^{p}+(1-t)d(P_{C}x,y)^{p}-\frac{c}{2}t(1-t)d(x,P_{C}x)^{p}$
$\displaystyle=d(x,y)^{p}-d(P_{C}x,y)^{p}-\frac{c}{2}d(x,P_{C}x)^{p},$

which yields the claim. ∎

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

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

###### Proof.

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

$\displaystyle d(y,T_{\lambda}x)^{p}$ $\displaystyle=d(y,\lambda
Tx\oplus(1-\lambda)x)^{p}$ $\displaystyle\leq\lambda
d(y,Tx)^{p}+(1-\lambda)d(y,x)^{p}-\frac{c}{2}\lambda(1-\lambda)d(x,Tx)^{p}$
$\displaystyle\leq
d(x,y)^{p}-\frac{c}{2}\frac{1-\lambda}{\lambda^{p-1}}d(x,T_{\lambda}x)^{p}.$

Solving $\frac{1-\lambda}{\lambda^{p-1}}=\frac{1-\alpha}{\alpha}$ for $\alpha$
yields the claim. ∎

##  4 Convergence of Iterated $\alpha$-Firmly Nonexpansive Mappings

The asymptotic center [13] of a bounded sequence $(x_{k})_{k\in\mathbb{N}}$ in
a metric space $(G,d)$ is the set

$A((x_{k})_{k\in\mathbb{N}}):=\left\\{x\in
G\,\middle|\,\limsup_{k\to\infty}d(x,x_{k})=r((x_{k})_{k\in\mathbb{N}})\right\\}$
(29)

where

$r((x_{k})_{k\in\mathbb{N}}):=\inf\left\\{\limsup_{k\to\infty}d(y,x_{k})\,\middle|\,y\in
G\right\\}.$ (30)

Following [28], a sequence $(x_{k})_{k\in\mathbb{N}}$ is said to
$\Delta$-converge to $\overline{x}\in G$ whenever $\overline{x}$ is the unique
asymptotic center of every subsequence of $(x_{k})_{k\in\mathbb{N}}$. In this
case $\overline{x}$ is said to be the $\Delta$-limit of the sequence and we
write $x_{k}\overset{\Delta}{\to}\overline{x}$.

###  4.1 Convergence - No Rate

The next theorem is a slight, but important generalization of analogous
results that can be found elsewhere in the literature. There are two main
differences: namely, that only quasi $\alpha$-firm nonexpansiveness is
required, and secondly, nonexpansiveness is only required at the asymptotic
centers of all subsequences. Our proof is nearly identical to the proof of [3,
Theorem 4.1], but the stronger assumptions of the theorem of that work
obscures the relationship between pointwise nonexpansiveness at asymptotic
centers and $\Delta$-convergence. In both [2] and [3], $\alpha$-firm
nonexpansiveness implies nonexpansiveness, which is not the case here.
Moreover, in general it would be far too restrictive to require $\alpha$-firm
nonexpansiveness everywhere when the property is really only required at its
fixed points where there is still hope that the property enjoys a reasonable
calculus.

######  Theorem 27.

Let $(G,d)$ be a $p$-uniformly convex space, let $D\subseteq G$ be convex, and
let $T:G\to G$ with $T(D)\subseteq D$ be pointwise $\alpha$-firmly
nonexpansive at all $y\in\operatorname{Fix}T\cap D$ on $D$. Define the
sequence $(x_{k})_{k\in\mathbb{N}}$ by $x_{k+1}=Tx_{k}$ with $x_{0}\in D$. If
this sequence is pointwise nonexpansive at the asymptotic centers of all
subsquences on $D$, then the asymptotic centers of all subsequences coincide
at a single $\overline{x}\in\operatorname{Fix}T\cap D$ and
$x_{k}\overset{\Delta}{\to}\overline{x}$. In particular, if $T$ is
nonexpansive on $D$, then every fixed point sequence initialized in $D$
$\Delta$-converges to a point in $\operatorname{Fix}T$. If, in addition,
$T(D)$ is a boundedly compact subset of $G$, then
$x_{k}\to\overline{x}\in\operatorname{Fix}T$.

###### Proof.

Let $\mathcal{N}$ denote any infinite subset of $\mathbb{N}$ and consider the
corresponding subsequence $(x_{k})_{k\in\mathcal{N}}$. This subsequence is
bounded since $T$ is a self-mapping on $D$ and pointwise $\alpha$-firmly
nonexpansive – and hence by Proposition 4(iii) nonexpansive – at all
$y\in\operatorname{Fix}T\cap D$ on $D$. Since $D$ is convex, this subsequence
therefore possesses a unique asymptotic center [27], which we denote by
$\overline{x}_{\mathcal{N}}$. Since $T$ is pointwise nonexpansive at
$\overline{x}_{\mathcal{N}}$ on $D$, we have

$\displaystyle\forall k\in\mathcal{N}\qquad
d(T\overline{x}_{\mathcal{N}},x_{k})$ $\displaystyle\leq$ $\displaystyle
d(T\overline{x}_{\mathcal{N}},Tx_{k})+d(Tx_{k},x_{k})$ $\displaystyle\leq$
$\displaystyle d(\overline{x}_{\mathcal{N}},x_{k})+d(Tx_{k},x_{k}).$

Again, since $T$ is pointwise $\alpha$-firmly nonexpansive at all
$y\in\operatorname{Fix}T\cap D$, by Theorem 7 we have $d(Tx_{k},x_{k})\to 0$
as $k\to\infty$. Therefore by [2, Lemma 2.11] (see also [27]), this implies
that $T\overline{x}_{\mathcal{N}}=\overline{x}_{\mathcal{N}}$, that is,
$\overline{x}_{\mathcal{N}}\in\operatorname{Fix}T$.

Denote the unique asymptotic center of the entire sequence
$(x_{k})_{k\in\mathbb{N}}$ by $\overline{x}$. Then

$\displaystyle\limsup_{k\underset{\mathcal{N}}{\to}\infty}d(x_{k},\overline{x}_{\mathcal{N}})$
$\displaystyle\leq$
$\displaystyle\limsup_{k\underset{\mathcal{N}}{\to}\infty}d(x_{k},\overline{x})$
$\displaystyle\leq$
$\displaystyle\limsup_{k\underset{\mathbb{N}}{\to}\infty}d(x_{k},\overline{x})$
$\displaystyle\leq$
$\displaystyle\limsup_{k\underset{\mathbb{N}}{\to}\infty}d(x_{k},\overline{x}_{\mathcal{N}})$
$\displaystyle=$
$\displaystyle\lim_{k\underset{\mathbb{N}}{\to}\infty}d(x_{k},\overline{x}_{\mathcal{N}})=\lim_{k\underset{\mathcal{N}}{\to}\infty}d(x_{k},\overline{x}_{\mathcal{N}}),$

where the first equality follows from the fact that the sequence of distances
is monotone decreasing and bounded below. Therefore
$\overline{x}_{\mathcal{N}}=\overline{x}$. Since $\mathcal{N}$ was an
arbitrary infinite subset of $\mathbb{N}$, this establishes
$\Delta$-convergence of $(x_{k})$.

To see strong convergence when $T(D)$ is boundedly compact, since
$(x_{k})_{k\in\mathbb{N}}$ is a bounded sequence in $T(D)$, it has a
convergent subsequence with limit $\overline{x}$. Whenever
$(d(x_{k},\overline{x}))_{k\in\mathbb{N}}$ converges, we can conclude that
$x_{k}\to\overline{x}$. ∎

###  4.2 Quantitative Convergence - Error Bounds

Our analysis of the convergence of fixed point iterations follows the same
pattern developed in [32, 31, 16]. In addition to pointwise $\alpha$-firm
nonexpansiveness developed above, we use the notion of gauge monotonicity of
sequences and metric subregularity. What we are calling gauge monotone
sequences were first introduced in [31] where they are called $\mu$-monotone.
Recall that $\rho:[0,\infty)\to[0,\infty)$ is a gauge function if $\rho$ is
continuous, strictly increasing with $\rho(0)=0$, and
$\lim_{t\to\infty}\rho(t)=\infty$.

######  Definition 28 (gauge monotonicity [31]).

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}.$ (31)

  2. (ii)

$(x_{k})_{k\in\mathbb{N}}$ is said to be _linearly monotone with respect to
$D$_ with rate $c$ if (31) 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 [7] are linearly monotone (with constant $c=1$)
but the converse does not hold (see Proposition 1 and Example 1 of [31]).
Gauge-monotonic convergence for a linear gauge in the definition above is just
$R$-linear convegence.

The definition of metric subregularity below is modeled mainly after [17,
Definition 2.1b)] and [18, Definition 1 b)].

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

Let $(G_{1},d_{1})$ and $(G_{2},d_{2})$ be metric spaces and let
$\mathcal{T}:\,G_{1}\to G_{2}\,$, $U_{1}\subset G_{1}$, $U_{2}\subset G_{2}$.
For $\Lambda\subset G_{1}$, the mapping $\mathcal{T}$ is called _metrically
regular on $U_{1}\times U_{2}$ relative to $\Lambda$ with gauge $\rho$_
whenever

$d_{1}\left(x,\mathcal{T}^{-1}(y)\cap\Lambda\right)\leq\rho(d_{2}\left(y,\mathcal{T}(x)\right))$
(32)

holds for all $x\in U_{1}\cap\Lambda$ and $y\in U_{2}$ with
$0<\rho(d_{2}\left(y,\mathcal{T}(x)\right))$ where
$\mathcal{T}^{-1}(y):=\left\\{z\,\middle|\,\mathcal{T}(z)=y\right\\}$. When
the set $U_{2}$ consists of a single point, $U_{2}=\\{\bar{y}\\}$, then
$\mathcal{T}$ is said to be _metrically subregular for $\bar{y}$ on $U_{1}$
relative to $\Lambda$ with gauge $\rho$_.

The usual definition of metric subregularity is in the case where the gauge is
just a linear function: $\rho(t)=\kappa t$. The “relative to” part of the
definition is also not common in the literature, but allows one to isolate the
regularity to subsets (mostly manifolds) where the iterates of algorithms are
naturally confined. See [4, Example 1.8] for a concrete example. In [22,
Example 3.9] this is placed in a context of the modulus of regularity of a
mapping with respect to its zeros. For our purposes, the easiest way to
understand metric subregularity is as one-sided Lipschitz continuity of the
(set-valued) inverse mapping $\mathcal{T}^{-1}$. We will refer to the case
when the gauge is linear to linear metric subregularity.

We construct $\rho$ 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.$
(33)

The gauge we will use satisfies

$\rho\left(\left(\frac{t^{p}-\left(\theta(t)\right)^{p}}{\tau}\right)^{1/p}\right)=t\quad\iff\quad\theta(t)=\left(t^{p}-\tau\left(\rho^{-1}(t)\right)^{p}\right)^{1/p}$
(34)

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

In the case of linear metric subregularity on a $2$-uniformly convex space
(think Hilbert space) we have

$\rho(t)=\kappa
t\quad\iff\quad\theta(t)=\left(1-\frac{\tau}{\kappa^{2}}\right)^{1/2}t\quad(\kappa\geq\sqrt{\tau}).$

The condition $\kappa\geq\sqrt{\tau}$ is spurious since, if (32) is satisfied
for some $\kappa^{\prime}>0$, then it is satisfied for all
$\kappa\geq\kappa^{\prime}$.

From the transport discrepancy $\psi^{(p,c)}_{T}$ defined in (4) and a subset
$S\subset G$ we construct the following surrogate mapping
$\mathcal{T}_{S}:\,G\to\mathbb{R}_{+}\,\cup\\{+\infty\\}$ by

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

If $S=\emptyset$ then, by definition, $\mathcal{T}_{S}(x):=+\infty$ for all
$x$. When $S\subseteq\operatorname{Fix}T$, then by Proposition 4(i)

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

Hence, this function is proper (finite at least at one point, and does not
take the value $-\infty$) when $S\subseteq\operatorname{Fix}T$ is nonempty.
This can be interpreted as the pointwise transport discrepancy relative to the
fixed points and will be used to characterize the regularity of the mapping
$T$ at fixed points.

######  Theorem 30 (quantitative convergence).

Let $(G,d)$ be a $p$-uniformly convex space, let $D\subset G$, let $T:G\to G$
with $T(D)\subseteq D$ boundedly compact, and let $S:=\operatorname{Fix}T\cap
D$ be nonempty. Assume

  1. (i)

$T$ is pointwise $\alpha$-firmly nonexpansive at all points $y\in S$ with the
same constant $\overline{\alpha}$ on $D$;

  2. (ii)

$\mathcal{T}_{S}$ defined by (35) is metrically subregular for $0$ relative to
$D$ on $D$ with gauge $\rho$ given by (34) for
$\tau=c(1-\overline{\alpha})/(2\overline{\alpha})$, that is,

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

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},$ (38)

where $\theta$ given implicitly by (34) satisfies (33). 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 the result, we establish convergence of gauge monotone
sequences.

######  Lemma 31 (gauge monotonicity and quasi $\alpha$-firmness imply
convergence to fixed points).

Let $(G,d)$ be a complete, $p$-uniformly convex metric space with constant
$c$. Let $T:G\to G$ with $T(D)\subseteq D\subseteq G$ and $T(D)$ boundedly
compact. Suppose that $\operatorname{Fix}T\cap D$ is nonempty and that $T$ is
pointwise $\alpha$-firmly nonexpansive at all $y\in\operatorname{Fix}T\cap D$
with the same constant $\overline{\alpha}$ 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 (33), 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.

By (14), the assumption that $T$ is pointwise $\alpha$-firmly nonexpansive at
all $y\in\operatorname{Fix}T\cap D$ with constant $\overline{\alpha}$ on $D$
yields

$d(Tx,y)^{p}\leq
d(x,y)^{p}-\tfrac{c(1-\overline{\alpha})}{2\overline{\alpha}}d(x,Tx)^{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(D)$ is boundedly compact and $T$ is pointwise
$\alpha$-firmly nonexpansive at all points in $\operatorname{Fix}T\cap D$ on
$D$, by Proposition 4(iii) and Lemma 6, $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 we have

$d(x_{k+1},\bar{x}_{k})^{p}\leq
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{c(1-\overline{\alpha})}{2\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{c(1-\overline{\alpha})}{2\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{c(1-\overline{\alpha})}{2\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{c(1-\overline{\alpha})}{2\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 (33). 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})\to 0$ monotonically as $k\to\infty$ and hence
$(x_{k})_{k\in\mathbb{N}}$ is a Cauchy sequence. Because $(G,d)$ is a complete
metric space we conclude that $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{c(1-\overline{\alpha})}{2\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}$ we have

$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 by
Lemma 6 $\operatorname{Fix}T\cap D$ is closed, hence
$x^{*}\in\operatorname{Fix}T\cap D$. ∎

Proof of Theorem 30.  Since $S=\operatorname{Fix}T\cap D$, by Proposition 4(i)
we have $\psi^{(p,c)}_{T}(x,y)=\tfrac{c}{2}d(Tx,x)^{p}$ for all
$y\in\operatorname{Fix}T$, so in fact $\mathcal{T}_{S}(x)=d(Tx,x)$. Also by
Proposition 4(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 (ii) and the
definition of metric subregularity (Definition 29)

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

In other words,

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

On the other hand, by assumption (i) we have

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

Incorporating (39) into (40) and rearranging the inequality yields

$\displaystyle d(Tx,y)^{p}\\!$ $\displaystyle\leq$
$\displaystyle\\!d(x,y)^{p}-\tfrac{1-\overline{\alpha}}{\overline{\alpha}}\tfrac{c}{2}\left(\rho^{-1}\left(d(x,\operatorname{Fix}T\cap
D)\right)\right)^{p}\quad\forall y\in\operatorname{Fix}T\cap D,\forall x\in
D.$ (41)

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

$d\left(x_{k+1},\,y\right)\leq\sqrt[p]{d\left(x_{k},\,y\right)^{p}-\frac{1-\overline{\alpha}}{\overline{\alpha}}\tfrac{c}{2}\left(\rho^{-1}\left(d\left(x_{k},\,\operatorname{Fix}T\cap
D\right)\right)\right)^{p}}\quad\forall y\in\operatorname{Fix}T\cap
D,~{}\forall k\in\mathbb{N}.$ (42)

Equation (42) simplifies. Indeed, by Lemma 6, $\operatorname{Fix}T\cap D$ is
closed. Moreover, since $T(D)$ is assumed to be boundedly compact, 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
d(x_{k},y_{k})^{p}-\tfrac{1-\overline{\alpha}}{\overline{\alpha}}\tfrac{c}{2}\left(\rho^{-1}\left(d(x_{k},y_{k})\right)\right)^{p}\quad\forall
k\in\mathbb{N}.$ (43)

Taking the $p$-th root and recalling (34) yields (38).

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.(33). By Lemma 31 we conclude 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$

In [31, Theorem 2] it is shown that if every fixed point sequence initialized
on $D\subset G$ is linearly monotone with respect to $\operatorname{Fix}T\cap
D$ with rate $c<1$ then the surrogate mapping $\Psi$ is linearly metrically
subregular for $0$ relative to $D$ on $D$. From this they establish that
linear metric subregularity is in fact necessary for linear convergence of
fixed point sequences generated by almost $\alpha$-firmly nonexpansive
mappings [31, Corollary 1]. We show that this extends more generally to fixed
point iterations in $p$-uniform metric spaces of quasi $\alpha$-firmly
nonexpansive mappings where the iterates converge at a rate characterized by
$\theta$.

######  Theorem 32 (necessity of metric subregularity for monotone sequences).

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 (33). 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 (35) is metrically subregular for $0$ relative to
$D$ on $D$ with gauge $\rho(\cdot)=(\operatorname{Id}-\theta)^{-1}(\cdot)$.

###### Proof.

If the fixed point sequence is gauge monotone relative to $S$ with rate
$\theta$ satisfying (33) then by the triangle inequality

$\displaystyle d(x_{k+1},x_{k})$ $\displaystyle\geq$ $\displaystyle
d(x_{k},S)-d(x_{k+1},S)$ (44) $\displaystyle\geq$ $\displaystyle
d(x_{k},S)-\theta\left(d(x_{k},S)\right)\quad\forall k\in\mathbb{N}.$

On the other hand, as shown in the proof of Theorem 30

$\displaystyle\mathcal{T}_{S}^{-1}(0)$ $\displaystyle=$
$\displaystyle\operatorname{Fix}T,$ $\displaystyle
d(0,\mathcal{T}_{S}(x_{k}))$ $\displaystyle=$ $\displaystyle d(x_{k+1},x_{k})$
(45)

Combining (44) and (45) yields

$d(0,\mathcal{T}_{S}(x_{k}))\geq d(x_{k},\mathcal{T}_{S}^{-1}(0)\cap
D)-\theta\left(d(x_{k},\mathcal{T}_{S}^{-1}(0)\cap D)\right)\quad\forall
k\in\mathbb{N}$ (46)

By assumption $(\operatorname{Id}-\theta)^{-1}(\cdot)$ is continuous on
$\mathbb{R}_{+}$, strictly increasing, and
$(\operatorname{Id}-\theta)^{-1}(0)=0$, so

$(\operatorname{Id}-\theta)^{-1}\left(d(0,\mathcal{T}_{S}(x_{k}))\right)\geq
d(x_{k},\mathcal{T}_{S}^{-1}(0)\cap D)\quad\forall k\in\mathbb{N}.$ (47)

Since this holds for any sequence $(x_{k})_{k\in\mathbb{N}}$ initialized in
$D$, we conclude that $\mathcal{T}_{S}$ is metrically subregular for $0$ on
$D$ with gauge $\rho=(\operatorname{Id}-\theta)^{-1}$. ∎

The next corollary is an immediate consequence of Lemma 31 and Theorem 32.

######  Corollary 33 (necessity of metric subregularity for gauge monotone
convergence).

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 and that $T$ is $\alpha$-firmly nonexpansive at all $y\in S$ on $D$.
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 (33). Suppose, in addition, that
$(\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 (35) is metrically subregular for $0$ relative to $D$ on $D$ with
gauge $\rho(\cdot)=(\operatorname{Id}-\theta)^{-1}(\cdot)$.

##  5 Examples

Most of the concrete examples provided here are for $p$-uniformly convex
spaces with $p=c=2$, i.e. CAT(0) spaces, and these are mostly known. We hint
at a path beyond this setting and in the case of cyclic projections obtain an
extension of [3, Proposition 4.1] to complete, symmetric perpendicular,
$p$-uniformly convex spaces.

###  5.1 Proximal Splitting

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

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

In this setting, the $p$-proximal mapping of $f$ (28) simplifies to

$\operatorname{prox}^{2}_{f,\lambda}(x):=\operatorname{argmin\,}_{y\in
H}\left\\{f(y)+\tfrac{1}{2\lambda}d(x,y)^{2}\right\\}.$ (49)

This has been studied in CAT(0) spaces in [21, 6, 2] and in the Hilbert ball
in [23]. To reduce notational clutter, we drop the superscript $2$. In these
earlier works it was already known that resolvents of lsc convex functions are
(everywhere) $\alpha$-firmly nonexpansive with $\alpha=1/2$. The
specialization of Corollary 23 to the case $p=c=2$ confirms this. 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 H$.

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

We are certainly not the first to study this algorithm. Indeed, convergence
has been established already in [3, Theorem 4.1]. This conclusion also follows
immediately from Theorem 27 upon application of Corollary 13 which shows that
the composition of quasi-$\alpha$-firmly nonexpansive $\operatorname{prox}$
mappings, $\operatorname{prox}_{f_{i},\lambda_{i}}$, is quasi-$\alpha$-firmly
nonexpansive on $H$ with constant $\overline{\alpha}_{N}$ given recursively by
(24). If on a neighborhood of $\operatorname{Fix}T$, denoted by $D$, the
mapping $\mathcal{T}_{\operatorname{Fix}T\cap D}$ defined by (35) – which by
Proposition 4(i) simplifies to (36) – satisfies

$d(x,\operatorname{Fix}T\cap D)\leq\rho(d(Tx,x))\quad\forall x\in D$ (50)

where $\rho$ is a gauge given by (34) for
$\tau=\tfrac{1-\overline{\alpha}_{N}}{\overline{\alpha}_{N}}$, then by Theorem
30 the sequence $(x_{k})$ converges gauge monotonically to some
$x^{*}\in\operatorname{Fix}T$ 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 (34).

By Corollary 23, on spaces with curvature bounded above, the $p$-proximal
mapping is only almost $\alpha$-firmly nonexpansive, which then yields that
the composition of $p$-proximal mappings is also only almost $\alpha$-firmly
nonexpansive. However, the violation $\epsilon_{c}=\frac{2-c}{c-1}$, where $c$
is the constant of curvature of the space. This constant can be made
arbitrarily small by choosing a small enough domain. In this way, the
violation can also be made arbitrarily small. As shown in [32, 29] in the
context of Euclidean spaces, if $\mathcal{T}_{\operatorname{Fix}T}$ is
metrically subregular, then the violation of $\alpha$-firm nonexpansiveness
can be overcome to yield quantifiable (e.g. linear) convergence on
neighborhoods of $\operatorname{Fix}T$. This would then yield for the first
time convergence of proximal splitting algorithms on spaces with positive
curvature. This will be the subject of a future study.

###  5.2 Projected Gradients

Here we specialize problem (48) to the case $N=2$ and $f_{2}=\iota_{C}$, the
indicator function of some closed convex set $C\subset H$. Recall, in a
Hadamard space Moreau-Yosida envelope of $f$ is defined by

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

In a Hilbert space setting, the proximal mapping of a convex function $f$ and
the resolvent of its subdifferential are one and the same. Moreover,
$e_{f,\lambda}$ is continuously differentiable with $\nabla
e_{f,\lambda}=\frac{1}{\lambda}\left(\operatorname{Id}-\operatorname{prox}_{f,\lambda}\right)$.
A step of length $\tau$ in the direction of steepest descent of the Moreau-
Yosida envelope of $f$ takes the form

$x-\tau\nabla
e_{f,\lambda}(x)=\left((1-\tau)\operatorname{Id}+\tau\operatorname{prox}_{f,\lambda}\right)(x).$

Formally transposing this to a CAT(0) space yields the nonlinear analog to the
direction of steepest descent for $e_{f,\lambda}$:

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

This leads to Algorithm 2, the analog to projected gradients in CAT(0) space,
which is nothing more than a projected resolvent/ projected proximal
iteration.

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

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

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

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

Algorithm 2 Metric Projected Gradients

Theorem 21 establishes that the mapping
$x\mapsto\left((1-\tau)\operatorname{Id}\oplus\tau\operatorname{prox}_{f,\lambda}\right)$
is $\alpha$-firmly nonexpansive with constant $\overline{\alpha}=1/2$.
Therefore, by Theorem 11 the operator $T_{PG}$ is $\alpha$-firmly nonexpansive
on $H$ with constant $\widehat{\alpha}=\tfrac{2}{3}$. Theorem 27 then
guarantees that the sequence $(x_{k})$ is $\Delta$-convergent to some
$x^{*}\in\operatorname{Fix}T_{GF}$, with strong convergence whenever $T_{GF}$
is boundedly compact. If in addition (50) is satisfied with $T$ replaced by
$T_{PG}$ and with gauge $\rho$ given by (34) for $\tau=1/2$, then, again, by
Theorem 30 the sequence $(x_{k})$ converges gauge monotonically to some
$x^{*}\in\operatorname{Fix}T$ 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 (34).

###  5.3 Cyclic Projections in $p$-uniformly Convex Spaces

For compositions of projectors we are not confined to Hadamard spaces. 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 Proposition 25 these are pointwise $\alpha$-firmly nonexpansive at all
points in $\cap_{i}C_{i}$ (assuming, of course, that this is nonempty). By
Lemma 10 the cyclic projections mapping

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

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$. The only
asymptotic centers of subsequences of cyclic projections are points in this
intersection, and here the projectors, and hence the cyclic projections
mapping, are pointwise nonexpansive. So by Theorem 27 the cyclic projections
sequence $\Delta$-converges to a point in $\cap_{i}C_{i}$ whenever this is
nonempty, and converges strongly whenever at least one of the sets $C_{i}$ is
compact. This generalizes [3, Proposition 4.1] which is limited to
CAT($\kappa$) spaces (i.e. $p=2$, $c<2$ small enough).

If in addition

$d(x,\cap_{i}C_{i})\leq\rho(d(T_{CP}x,x))\quad\forall x\in G$ (53)

where $\rho$ is a gauge given by (34) for $\tau=\tfrac{1}{N-1}$, then by
Theorem 30 the sequence $(x_{k})$ converges gauge monotonically to some
$x^{*}\in\operatorname{Fix}T$ 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 (34).

##  6 Open Problems

Nonexpansiveness is a fairly robust property that carries over to compositions
and convex combinations of mappings without requiring that those operators
share fixed points. Our notion of $\alpha$-firm mappings appears to be much
more demanding. Our development begs the question: is the $\alpha$-firmness
property preserved in some sense under compositions and convex compositions of
(pointwise) $\alpha$-firm mappings that do not share common fixed points? The
answer to this question has immediate bearing on the analysis of simple
algorithms like cyclic projections for inconsistent feasibility or coordinate
descents in nonlinear spaces.

The other open problem, whose solution was hinted at above, is whether
compositions and averages of $p$-proximal mappings converge at some rate under
reasonable assumptions of metric subregularity at fixed points. The notion of
almost  $\alpha$-firm nonexpansiveness was used in [32] primarily for the
purpose of handling projectors onto nonconvex sets, and other prox-mappings of
nonconvex functions. Since the technology of almost $\alpha$-firmness is
required for the $p$-proximal mappings of even convex functions, a study in
this direction will also account for $p$-proximal mappings of nonconvex
functions, including projections onto nonconvex sets.

## References

  * [1] A. D. Alexandrov.  A theorem on triangles in a metric space and some of its applications.  Trudy Mat. Inst. Steklova, 38:5–23, 1951.
  * [2] D. Ariza-Ruiz, L. Leuştean, and G. López-Acedo.  Firmly nonexpansive mappings in classes of geodesic spaces.  Trans. Am. Math. Soc., 366(8):4299–4322, 2014.
  * [3] 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.
  * [4] 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.
  * [5] J. B. Baillon, R. E. Bruck, and S. Reich.  On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces.  Houston J. Math., 4(1):1–9, 1978.
  * [6] S. Banert.  Backward–backward splitting in Hadamard spaces.  Journal of Math. Anal. and Appl., 414(2):656–665, 2014.
  * [7] H. H. Bauschke and P. L. Combettes.  Convex analysis and monotone operator theory in Hilbert spaces. 2nd edition. Cham: Springer, 2nd edition edition, 2017.
  * [8] M. Bačák.  Computing medians and means in Hadamard spaces.  SIAM J. Optim., 24(3):1542–1566, 2014.
  * [9] A. Bërdëllima.  Investigations in Hadamard Spaces.  PhD thesis, Georg-August Universität Göttingen, Göttingen, 2020\.
  * [10] I. D. Berg and I. G. Nikolaev.  Quasilinearization and curvature of Aleksandrov spaces.  Geom. Dedicata, 133:195–218, 2008.
  * [11] R. E. Bruck.  Nonexpansive projections on subsets of Banach spaces.  Pacific J. Math., 47:341–355, 1973.
  * [12] J. Eckstein.  Splitting Methods for Monotone Operators with Applications to Parallel Optimization.  PhD thesis, MIT, Cambridge, MA, 1989.
  * [13] M. Edelstein.  The construction of an asymptotic center with a fixed-point property.  Bull. Am. Math. Soc., 78:206–208, 1972.
  * [14] K. Goebel and S. Reich.  Uniform convexity, hyperbolic geometry, and nonexpansive mappings., volume 83.  Marcel Dekker, Inc., New York, NY, 1984.
  * [15] M. Gromov.  CAT($\kappa$)-spaces: construction and concentration.  Zap. Nauch. Sem. POMI, 280:101–140, 2001.
  * [16] N. Hermer, D. R. Luke, and A. Sturm.  Random function iterations for consistent stochastic feasibility.  Numer. Funct. Anal. Opt., 40(4):386–420, 2019.
  * [17] A. D. Ioffe.  Regularity on a fixed set.  SIAM J. Optim., 21(4):1345–1370, 2011.
  * [18] A. D. Ioffe.  Nonlinear regularity models.  Math. Program., 139(1-2):223–242, 2013.
  * [19] 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.
  * [20] J. Jost.  Convex functionals and generalized harmonic maps into spaces of non positive curvature.  Comment. Math. Helv., 70(4):659–673, 1995.
  * [21] J. Jost.  Nonpositive Curvature: Geometric and Analytic Aspects.  Lectures in Mathematics. ETH Zurich. Birkhäuser, Basel, 1997.
  * [22] U. Kohlenbach, G. López-Acedo, and A. Nicolae.  Moduli of regularity and rates of convergence for Fejér monotone sequences.  Isr. J. Math., 232(1):261–297, 2019.
  * [23] Eva Kopecká and Simeon Reich.  Asymptotic behavior of resolvents of coaccretive operators in the Hilbert ball.  Nonlinear Anal., Theory Methods Appl., Ser. A, Theory Methods, 70(9):3187–3194, 2009.
  * [24] K. Kuwae.  Jensen’s inequality on convex spaces.  Calc. Var. Partial Differ. Equ., 49(3-4):1359–1378, 2014.
  * [25] K. Kuwae.  Resolvent flows for convex functionals and $p$-harmonic maps.  Anal. Geom. Metr. Spaces, 3:46–72, 2015.
  * [26] U. Lang, B. Pavlović, and V. Schroeder.  Extensions of Lipschitz maps into Hadamard spaces.  Geom. Funct. Anal., 10(6):1527–1553, 2000.
  * [27] L. Leuştean.  Nonexpansive iterations in uniformly convex $W$-hyperbolic spaces.  In Nonlinear analysis and optimization I. Nonlinear analysis. A conference in celebration of Alex Ioffe’s 70th and Simeon Reich’s 60th birthdays, Haifa, Israel, June 18–24, 2008, pages 193–210. Providence, RI: American Mathematical Society (AMS); Ramat-Gan: Bar-Ilan University, 2010\.
  * [28] T. C. Lim.  Remarks on some fixed point theorems.  Proc. Am. Math. Soc., 60:179–182, 1976.
  * [29] D. R. Luke and A.-L. Martins.  Convergence analysis of the relaxed Douglas-Rachford algorithm.  SIAM J. Opt., 30(1):542–584, 2020.
  * [30] D. R. Luke, S. Sabach, and M. Teboulle.  Optimization on spheres: Models and proximal algorithms with computational performance comparisons.  SIAM J. Math. Data Sci., 1(3):408–445, 2019.
  * [31] 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.
  * [32] 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.
  * [33] A. Naor and L. Silberman.  Poincaré inequalities, embeddings, and wild groups.  Compos. Math., 147(5):1546–1572, 2011.
  * [34] S. Ohta.  Convexities of metric spaces.  Geom. Dedicata, 125:225–250, 2007.
  * [35] S. Reich and I. Shafrir.  The asymptotic behavior of firmly nonexpansive mappings.  Proc. Am. Math. Soc., 101:246–250, 1987.
  * [36] S. Reich and I. Shafrir.  Nonexpansive iterations in hyperbolic spaces.  Nonlinear Anal., Theory Methods Appl., 15(6):537–558, 1990.
  * [37] R. T. Rockafellar and R. J. Wets.  Variational Analysis.  Grundlehren Math. Wiss. Springer-Verlag, Berlin, 3 edition, 2009.
  * [38] K.-T. Sturm.  Probability measures on metric spaces of nonpositive curvature.  In Heat kernels and analysis on manifolds, graphs, and metric spaces. Lecture notes from a quarter program on heat kernels, random walks, and analysis on manifolds and graphs, April 16–July 13, 2002, Paris, France, pages 357–390. Providence, RI: American Mathematical Society (AMS), 2003.