Quantitative convergence analysis of iterated expansive, set-valued mappings

Introduction

We present a program of analysis that enables one to quantify the rate of convergence of sequences generated by fixed point iterations of expansive, set-valued mappings. The framework presented here subsumes earlier approaches for analyzing fixed point iterations of relaxed nonexpansive mappings and opens up new results for expansive mappings. Our approach has its roots in the pioneering work of Mann, Krasnoselski, Edelstein, GurinWe learned from Alex Kruger that Gurin’s name was misprinted as Gubin in the translation of his work into English., Polyak and Raik who wrote seminal papers in the analysis of (firmly) nonexpansive and averaged mappings although the terminology “averaged” wasn’t coined until sometime later . Our strategy is also indebted to the developers of notions of stability, in particular metric regularity and its more recent refinements . We follow a pattern of proof used in and for Picard iterations of set-valued mappings, though this approach was actually inspired by the analysis of alternating projections in .

The idea is to isolate two properties of the fixed point mapping. The first property is a generalization of the averaging property, what we call almost averaging. When a self-mapping is averaged and fixed points exist, then the Picard iteration converges to a fixed point (weakly in the Hilbert space setting) without any additional assumptions. (See [61, Theorem 3]. See also [70, 3. Satz] for the statement under the assumption that the mapping is weakly continuous.) In order to quantify convergence, a second property is needed. In their analysis of Krasnoselski-Mann relaxed cyclic projections for convex feasibility, Gurin, Polyak and Raik assume that the set-intersection has interior [31, Theorem 1]. Interiority is an assumption about stability of the fixed points of the mapping, and this generalizes considerably. Even if rates of convergence are not the primary interest, if the averaging property is relaxed in any meaningful way, monotonicity of Picard iterations with respect to the set of fixed points is lost. In order to recover convergence in this case, we appeal to stability of the set of fixed points to overcome the lack of monotonicity of the fixed point mapping. The second property we require of the mapping is a characterization of the needed stability at fixed points. Metric subregularity of the mapping at fixed points is one well-established notion that fulfills this stability and provides quantitative estimates for the rate of convergence of the iterates. This is closely related (actually synonymous) to the existence of error bounds. The almost averaging and the stability properties are defined and quantified on local neighborhoods, but our approach is not asymptotic. Indeed, when convexity or nonexpansivity is assumed, these local neighborhoods extend to the whole space and the corresponding results are global and recover the classical results.

We take care to introduce the notions of almost averaging, stability and metric subregularity, and to present the most general abstract results in Section 2. Almost averaged mappings are developed first in Section 2.1, after which abstract convergence results are presented in Section 2.2. In Section 2.3 the notion of metric regularity and its variants is presented and applied to the abstract results of Section 2.2. The rest of the paper, Section 3, is a tutorial on the application of these ideas to quantitative convergence analysis of algorithms for, respectively, nonconvex and inconsistent feasibility (Section 3.1) and structured optimization (Section 3.2). We focus our attention on just a few simple algorithms, namely cyclic projections, projected gradients and Douglas–Rachford.

Among the new and recent concepts are: almost nonexpansive/averaged mappings (Section 2.1), which are a generalization of averaged mappings and satisfy a type of strong calmness of set-valued mappings; submonotonicity of set-valued self-mappings (Definition 2.9), which is equivalent to almost firm-nonexpansiveness of their resolvents (Proposition 2.8) generalizing Minty’s classical identification of monotone mappings with firmly-nonexpansive resolvents ; elementally subregular sets (Definition 3.1 from [42, Definition 5]); subtransversality of collections of sets at points of nonintersection (Definition 3.6); and gauge metric subregularity (Definition 2.17 from ). These objects are applied to obtain a number of new results: local linear convergence of nonconvex cyclic projections for inconsistent feasibility problems (Theorem 3.14) with some surprising special cases like two nonintersecting circles (Example 3.18) and practical (inconsistent) phase retrieval (Example 3.20); global R-linear convergence of cyclic projections onto convex sets (Corollary 3.15); local linear convergence of forward-backward-type algorithms without convexity or strong monotonicity (Theorem 3.24); local linear convergence of the Douglas–Rachford algorithm for structured nonconvex optimization (Theorem 3.33) and a specialization to the relaxed averaged alternating reflections (RAAR) algorithm for inconsistent phase retrieval (Example 3.35).

The quantitative convergence results presented here focus on linear convergence, but this framework is appropriate for a wider range of behaviors, particularly sublinear convergence. The emphasis on linear convergence is in part due to its simplicity, but also because it is surprisingly prevalent in first order algorithms for common problem structures (see the discussions of phase retrieval in Examples 3.20 and 3.35). To be sure, there are constants that would, if known, determine the exact rate, and these are either hard or impossible to calculate. But in many instances the order of convergence – linear or sublinear – can be determined a priori. As such, a posteriori error bounds can be estimated in some cases, with the usual epistemological caveats, from the observed behavior of the algorithm. For problems where the solution to the underlying variational problem, as opposed to its optimal value, is the only meaningful result of the numerical algorithm, such error bounds are essential. One important example is image processing with statistical constraints studied in and . Here the images are physical measurements and solutions to the variational image processing problems have a quantitative statistical interpretation in terms of the experimental data. In contrast, the more common analysis determining that an algorithm for computing these solutions merely converges, or even that the objective value converges at a given rate, leads unavoidably to vacuous assurances.

Here the notation $x^{k}\stackrel{{\scriptstyle[}}{{f}}\,]{}{\to}{\overline{x}}$ means that $x^{k}\to{\overline{x}}\in\operatorname{{dom\,}}f$ and $f(x^{k})\to f({\overline{x}})$. When $f$ is convex, (1) reduces to the usual convex subdifferential given by

When ${\overline{x}}\notin\operatorname{{dom\,}}f$ the subdifferential is defined to be empty. Elements of the subdifferential are called subgradients.

$T$ is called strongly monotone on $\Omega$ if there exists a $\tau>0$ such that

When $T$ is single-valued, calmness is just pointwise Lipschitz continuity:

where ${\mathcal{T}}_{\Omega}$ is the tangent cone mapping associated with the set $\Omega$ defined by

Here the notation $x^{k}\stackrel{{\scriptstyle[}}{{\Omega}}\,]{}{\to}{\overline{x}}$ means that the sequence of points $\{x^{k}\}$ approaches ${\overline{x}}$ from within $\Omega$.

is the corresponding projector. An element $y\in P_{\Omega}(x)$ is called a projection. Closely related to the projector is the prox mapping

Throughout this note we will assume the distance corresponds to the Euclidean norm, though most of the statements are not limited to this. When $\operatorname{dist}(x,y)=\|x-y\|$ then one has the following variational characterization of the projector: ${\overline{z}}\in P^{-1}_{\Omega}{\overline{x}}$ if and only if

Following , we use this object to define the various normal cone mappings, which in turn lead to the subdifferential of the indicator function $\iota_{\Omega}$.

The $\varepsilon$-normal cone to $\Omega$ at ${\overline{x}}\in\Omega$ is defined

The (limiting) normal cone to $\Omega$ at ${\overline{x}}\in\Omega$, denoted ${N}_{\Omega}\left({\overline{x}}\right)$, is defined as the limsup of the $\varepsilon$-normal cones. That is, a vector $v\in{N}_{\Omega}\left({\overline{x}}\right)$ if there are sequences $x^{k}\stackrel{{\scriptstyle[}}{{\Omega}}\,]{}{\to}{\overline{x}}$, $v^{k}\to v$ with $v^{k}\in{\widehat{N}}^{\varepsilon_{k}}_{\Omega}\left(x^{k}\right)$ and $\varepsilon_{k}\searrow 0$. The proximal normal cone to $\Omega$ at ${\overline{x}}$ is the set

If ${\overline{x}}\notin\Omega$, then all normal cones are defined to be empty.

The proximal normal cone need not be closed. The limiting normal cone is, of course, closed by definition. See [55, Definition 1.1] or [68, Definition 6.3] (where this is called the regular normal cone) for an in-depth treatment as well as [55, page 141] for historical notes. When the projection is with respect to the Euclidean norm, the limiting normal cone can be written as the limsup of proximal normals:

General theory: Picard iterations

Our ultimate goal is a quantitative statement about convergence to fixed points for set-valued mappings. Preparatory to this, we first must be clear what is meant by a fixed point of a set-valued mapping.

In the set-valued setting, it is important to keep in mind a few things that can happen that cannot happen when the mapping is single-valued.

Here $P_{B}(1,1)=\left\{(0,1),(1,0)\right\}$ and the point $(1,1)$ is a fixed point of $T$ since $(1,1)\in P_{A}\left\{(0,1),(1,0)\right\}$. However, the point $P_{A}(0,1)$ is also in $T(1,1)$, and this is not a fixed point of $T$. $\Box$

To help rule out inhomogeneous fixed point sets like the one in the previous example, we introduce the following strong calmness of fixed point mappings that is an extension of conventional nonexpansiveness and firm nonexpansiveness. What we call almost nonexpansive mappings below were called $(S,\epsilon)$-nonexpansive mappings in [32, Definition 2.3], and almost averaged mappings are slight generalization of $(S,\epsilon)$-firmly nonexpansive mappings also defined there.

$T$ is said to be pointwise almost nonexpansive on $D$ at $y\in D$ if there exists a constant $\varepsilon\in[0,1)$ such that

If (18) holds with $\varepsilon=0$ then $T$ is called pointwise nonexpansive at $y$ on $D$.

If $T$ is pointwise (almost) nonexpansive at every point on a neighborhood of $y$ (with the same violation constant $\varepsilon$) on $D$, then $T$ is said to be (almost) nonexpansive at $y$ (with violation $\varepsilon$) on $D$.

If $T$ is pointwise (almost) nonexpansive on $D$ at every point $y\in D$ (with the same violation constant $\varepsilon$), then $T$ is said to be pointwise (almost) nonexpansive on $D$ (with violation $\varepsilon$). If $D$ is open and $T$ is pointwise (almost) nonexpansive on $D$, then it is (almost) nonexpansive on $D$.

$T$ is called pointwise almost averaged on $D$ at $y$ if there is an averaging constant $\alpha\in(0,1)$ and a violation constant $\varepsilon\in[0,1)$ such that the mapping $\widetilde{T}$ defined by

is pointwise almost nonexpansive at $y$ with violation $\varepsilon/\alpha$ on $D$.

Likewise if $\widetilde{T}$ is (pointwise) (almost) nonexpansive on $D$ (at $y$) (with violation $\varepsilon$), then $T$ is said to be (pointwise) (almost) averaged on $D$ (at $y$) (with averaging constant $\alpha$ and violation $\alpha\varepsilon$).

If the averaging constant $\alpha=1/2$, then $T$ is said to be (pointwise) (almost) firmly nonexpansive on $D$ (with violation $\varepsilon$) (at $y$).

Note that the mapping $T$ need not be a self-mapping from $D$ to itself. In the special case where $T$ is (firmly) nonexpansive at all points $y\in\operatorname{\mathsf{Fix}\,}T$, mappings satisfying (18) are also called quasi-(firmly)nonexpansive .

The term “almost nonexpansive” has been used for different purposes by Nussbaum and Rouhani . Rouhani uses the term to indicate sequences, in the Hilbert space setting, that are asymptotically nonexpansive. Nussbaum’s definition is the closest in spirit and definition to ours, except that he defines $f$ to be locally almost nonexpansive when $\|f(y)-f(x)\|\leq\|y-x\|+\varepsilon$. In this context, see also . At the risk of some confusion, we re-purpose the term here. Our definition of pointwise almost nonexpansiveness of $T$ at ${\overline{x}}$ is stronger than calmness [68, Chapter 8.F] with constant $\lambda=\sqrt{1+\varepsilon}$ since the inequality must hold for all pairs $x^{+}\in Tx$ and $y^{+}\in Ty$, while for calmness the inequality would hold only for points $x^{+}\in Tx$ and their projections onto $Ty$. We have avoided the temptation to call this property “strong calmness” in order to make clearer the connection to the classical notions of (firm) nonexpansiveness. A theory based only on calm mappings, what one might call “weakly almost averaged/nonexpansive” operators is possible and would yield statements about the existence of convergent selections from sequences of iterated set-valued mappings. In light of the other requirement of the mapping $T$ that we will explore in Section 2.3, namely metric subregularity, this would illuminate an aesthetically pleasing and fundamental symmetry between requirements on $T$ and its inverse. We leave this avenue of investigation open. Our development of the properties of almost averaged operators parallels the treatment of averaged operators in .

$T$ is pointwise almost averaged at $y$ on $U$ with violation $\varepsilon$ and averaging constant $\alpha$.

For all $x\in U,\,x^{+}\in T(x)$ and $y^{+}\in T(y)$ it holds that

Consequently, if $T$ is pointwise almost averaged at $y$ on $U$ with violation $\varepsilon$ and averaging constant $\alpha$ then $T$ is pointwise almost nonexpansive at $y$ on $U$ with violation at most $\varepsilon$.

Proof. This is a slight extension of [11, Proposition 4.25].

Let $T:=P_{A}P_{B}$ for the closed sets $A$ and $B$ defined below.

If $A$ and $B$ are convex, then $T$ is nonexpansive and averaged (i.e. pointwise everywhere, no violation).

The mapping $T$ is not almost nonexpansive on any neighborhood for any finite violation at $y=(0,0)\in\operatorname{\mathsf{Fix}\,}T$, but it is pointwise nonexpansive (no violation) at $y=(0,0)$ and nonexpansive at all $y\in(A\cap B)\setminus\{0\}$ on small enough neighborhoods of these points.

$T$ is pointwise averaged at $(1,1)$ when

This illustrates that whether or not $A$ and $B$ have points in common is not relevant to the property.

$T$ is not pointwise almost averaged at $(1,1)$ for any $\varepsilon>0$ when

In light of Example 2.2, this shows that the pointwise almost averaged property is incompatible with inhomogeneous fixed points (see Proposition 2.6).

Proof. By the definition of pointwise nonexpansive on $D$ at ${\overline{x}}$, it holds that

for all $x\in D,\,x^{+}\in T(x)$ and ${\overline{x}}^{+}\in T({\overline{x}})$. In particular, setting $x={\overline{x}}$ gives yields

That is, $x^{+}={\overline{x}}^{+}$ and hence we conclude that $T$ is single-valued at ${\overline{x}}$.

Almost firmly nonexpansive mappings have particularly convenient characterizations. In our development below and thereafter we use the set $S$ to denote the collection of points at which the property holds. This is useful for distinguishing points where the regularity holds from other distinguished points, like fixed points. In Section 2.3 the set $S$ is used to isolate a subset of fixed points. The idea here is that the properties needed to quantify convergence need not hold on the space where a problem is formulated, but may only hold on a subset of this space where the iterates of a particular algorithm may be, naturally, confined. This is used in to achieve linear convergence results for the alternating directions method of multipliers algorithm. Alternatively, $S$ can also include points that are not fixed points of constituent operators in an algorithm, but are closely related to fixed points. One example of this is local best approximation points, that is, points in one set that are locally nearest to another. In section 3.1 we will need to quantify the violation of the averaging property for a projector onto a nonconvex set $A$ at points in another set, say $B$, that are locally nearest points to $A$. This will allow us to tackle inconsistent feasibility where the alternating projections iteration converges not to the intersection, but to local best approximation points.

$T$ is pointwise almost firmly nonexpansive on $U$ at all $y\in S$ with violation $\varepsilon$.

is pointwise almost nonexpansive on $U$ at all $y\in S$ with violation $2\varepsilon$, that is, $T$ can be written as

$\left\|x^{+}-y^{+}\right\|^{2}\leq\frac{\varepsilon}{2}\left\|x-y\right\|^{2}+\langle x^{+}-y^{+},x-y\rangle$ for all $x^{+}\in Tx$, and all $y^{+}\in Ty$ at each $y\in S$ whenever $x\in U$.

Proof. i$\iff$ii: Follows from Proposition 2.4 when $\alpha=1/2$.

ii$\implies$iii: Note first that at each $x\in U$ and $y\in S$

iii$\implies$ii: Use (23a) to replace $\left\langle x^{+}-y^{+},~{}x-y\right\rangle$ in iii and rearrange the resulting inequality to conclude that $2T-\operatorname{Id}$ is pointwise almost nonexpansive at $y\in S$ with violation $2\varepsilon$ on $U$.

iv$\iff$iii: First, note that $(u,z)\in\operatorname{gph}F$ if and only if $\left(u+z,u\right)\in\operatorname{gph}\left(\operatorname{Id}+F\right)^{-1}$. From this it follows that for $u\in Tx$ and $v\in Ty$, the points $(u,z)$ and $(v,w)$ with $z=x-u$ and $w=y-v$, are in $\operatorname{gph}F$. So starting with iii, at each $x\in U$ and $y\in S$,

for all $u\in Tx$ and $v\in Ty$. Separating out $\left\|u-v\right\|^{2}$ from the inner product on the left hand side of (25) yields the result.

Property iv of Proposition 2.8 is a type of submonotonicity of the mapping $F$ on $D$ with respect to $S$. We use this descriptor to distinguish this notion from another well-established property known as hypomonotonicity .

The mapping $F$ is said to be submonotone on $U$ if (26) holds for all ${\overline{v}}$ on $U$.

If (27) holds for all ${\overline{v}}\in U$ then $F$ is said to be hypomonotone with constant $\tau$ on $U$.

This also points to a relationship to cohypomonotonicity developed in . More recently the notion of pointwise quadratically supportable functions was introduced [51, Definition 2.1]; for smooth functions, this class – which is not limited to convex functions – was shown to include functions whose gradients are pointwise strongly monotone (pointwise hypomonotone with constant $\tau<0$) [51, Proposition 2.2]. A deeper investigation of the relationships between these different notions is postponed to future work.

The next result shows the inheritance of the averaging property under compositions and averages of averaged mappings.

If $U:=U_{1}=U_{2}=\dots=U_{m}$ and $S:=S_{1}=S_{2}=\cdots=S_{m}$ then the weighted mapping $T:=\sum_{j=1}^{m}w_{j}T_{j}$ with weights $w_{j}\in$, $\sum_{j=1}^{m}w_{j}=1$, is pointwise almost averaged at all $y\in S$ with violation $\varepsilon=\sum_{j=1}^{m}w_{j}\varepsilon_{j}$ and averaging constant $\alpha=\max_{j=1,2,\dots,m}\left\{\alpha_{j}\right\}$ on $U$.

If $T_{j}U_{j}\subseteq U_{j-1}$ and $T_{j}S_{j}\subseteq S_{j-1}$ for $j=2,3,\dots,m$, then the composite mapping $T:=T_{1}\circ T_{2}\circ\cdots\circ T_{m}$ is pointwise almost nonexpansive at all $y\in S_{m}$ on $U_{m}$ with violation at most

If $T_{j}U_{j}\subseteq U_{j-1}$ and $T_{j}S_{j}\subseteq S_{j-1}$ for $j=2,3,\dots,m$, then the composite mapping $T:=T_{1}\circ T_{2}\circ\cdots\circ T_{m}$ is pointwise almost averaged at all $y\in S_{m}$ on $U_{m}$ with violation at most $\varepsilon$ given by (29) and averaging constant at least

Proof. Statement i is a formal generalization of [11, Proposition 4.30] and follows directly from convexity of the squared norm and Proposition 2.4iii.

Statement ii follows from applying the definition of almost nonexpansivity to each of the operators $T_{j}$ inductively, from $j=1$ to $j=m$.

Statement iii is formal generalization of [11, Proposition 4.32] and follows from more or less the same pattern of proof. Since it requires a little more care, the proof is given here. Define $\kappa_{j}:=\alpha_{j}/(1-\alpha_{j})$ and set $\kappa=\max_{j}\left\{\kappa_{j}\right\}$. Identify $y_{j-1}$ with any $y^{+}_{j}\in T_{j}y_{j}\subseteq S_{j-1}$ for $j=2,3,\dots,m$ and choose any $y_{m}\in S_{m}$. Likewise, identify $x_{j-1}$ with any $x^{+}_{j}\in T_{j}x_{j}\subseteq U_{j-1}$ for $j=2,3,\dots,m$ and choose any $x_{m}\in U_{m}$. Denote $u^{+}\in T_{1}\circ T_{2}\circ\cdots\circ T_{m}u$ for $u:=x_{m}$ and $v^{+}\in T_{1}\circ T_{2}\circ\cdots\circ T_{m}v$ for $v:=y_{m}$. By convexity of the squared norm and Proposition 2.4iii one has

Replacing $\kappa_{j}$ by $\kappa$ yields

The composition $T$ is therefore almost averaged with violation

and averaging constant $\alpha=m/(m+1/\kappa)$. Finally, an induction argument shows that

We remark that Proposition 2.10ii holds in the case when $T_{j}$ ($j=1,2,\dots,m$) are merely pointwise almost nonexpansive. The counterpart for $T_{j}$ ($j=1,\dots,m$) pointwise almost nonexpansive to Proposition 2.10i is given by allowing $\alpha=0$.

Let $\lambda\in$ and define $T_{\lambda}:=\left(1-\lambda\right)\operatorname{Id}+\lambda T$ for $T$ pointwise almost averaged at $y$ with violation $\varepsilon$ and averaging constant $\alpha$ on $U$. Then $T_{\lambda}$ is pointwise almost averaged at $y$ with violation $\lambda\varepsilon$ and averaging constant $\alpha$ on $U$. In particular, when $\lambda=1/2$ the mapping $T_{1/2}$ is pointwise almost firmly nonexpansive at $y$ with violation $\varepsilon/2$ on $U$.

A particularly attractive consequence of Corollary 2.12 is that the violation of almost averaged mappings can be mitigated by taking smaller steps via Krasnoselski-Mann relaxation.

To conclude this section we prove the following lemma, a special case of which will be required in Section 3.1.3, which relates the fixed point set of the composition of pointwise almost averaged operators to the corresponding difference vector.

Proof. First observe that, since ${\overline{\zeta}}\in\mathcal{Z}(\bar{u})$, there exists ${\overline{z}}=({\overline{z}}_{1},{\overline{z}}_{2},\ldots,{\overline{z}}_{m})\in W_{0}$ with ${\overline{z}}_{1}=\bar{u}$ such that ${\overline{\zeta}}={\overline{z}}-\Pi{\overline{z}}$, hence $U$, and thus $U_{j}=p_{j}(U)$, is nonempty since it at least contains ${\overline{z}}$ (and ${\overline{z}}_{j}\in U_{j}$ for $j=1,2,\ldots,m$). Consider a second point $u\in S_{0}$ and let $\zeta\in\mathcal{Z}(u)$. Similarly, there exists $z=(z_{1},z_{2},\ldots,z_{m})\in W_{0}$ such that $z_{1}=u$ and $\zeta=z-\Pi z\in U$. For each $j=1,2,\dots,m$, we therefore have that

and, since $T_{j}$ is pointwise almost averaged at ${\overline{z}}_{j}$ with constant $\alpha_{j}$ and violation $\varepsilon_{j}$ on $U_{j}$,

where ${\overline{z}}_{0}:={\overline{z}}_{m}$ and $z_{0}=z_{m}$. Altogether this yields

which proves (35). If in addition, for all $j=1,2,\ldots,m$, the mappings $T_{j}$ are pointwise averaged, then $\varepsilon_{1}=\varepsilon_{2}=\dots=\varepsilon_{m}=0$, and the proof is complete.

2 Convergence of Picard iterations

T is pointwise almost averaged at all points $y\in S$ with violation $\varepsilon$ and averaging constant $\alpha\in(0,1)$ on ${\mathcal{O}}\cap\Lambda$, and

there exists a neighborhood ${\mathcal{V}}$ of $\operatorname{\mathsf{Fix}\,}T\cap S$ and a $\kappa>0$, such that for all $y^{+}\in Ty,~{}y\in S,$ and all $x^{+}\in Tx$ the estimate

holds whenever $x\in\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$.

whenever $x\in\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$.

In particular, if $\kappa<\sqrt{\frac{1-\alpha}{\varepsilon\alpha}}$, then for all $x^{0}\in{\mathcal{O}}\cap\Lambda$ the iteration $x^{j+1}\in Tx^{j}$ satisfies

with $c:=\left(1+\varepsilon-\frac{1-\alpha}{\alpha\kappa^{2}}\right)^{1/2}<1$ for all $j$ such that $x^{i}\in\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$ for $i=1,2,\dots,j$.

Before presenting the proof, some remarks will help clarify the technicalities. The role of assumption a is clear in the two-property scheme we have set up. The second assumption b is a characterization of the required stability of the fixed points and their preimages. It is helpful to consider a specialization of this assumption which simplifies things considerably. First, by Proposition 2.6, since $T$ is almost averaged at all points in $S$, then it is single-valued there and one can simply write $Ty$ for all $y\in S$ instead of $y^{+}\in Ty$. The real simplification comes when one considers the case $S=\operatorname{\mathsf{Fix}\,}T$. In this case $Ty=y$ for all $y\in S$ and condition (38) simplifies to

for all $x\in\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$ where $\Phi:=T-\operatorname{Id}$. The statement on annular regions $\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$ can be viewed as an assumption about the existence of an error bound on that region. For earlier manifestations of this and connections to previous work on error bounds see . In the present context, this condition will be identified in Section 2.3 with metric subregularity of $\Phi$, though, of course error bounds and metric subregularity are related.

The assumptions lead to the conclusion that the iterates approach the set of fixed points at some rate that can be bounded below by a linear characterization on the region $\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$. This will lead to convergence in Corollary 2.16 where on all such annular regions there is some lower linear convergence bound.

The possibility to have $S\subset\operatorname{\mathsf{Fix}\,}T$ and not $S=\operatorname{\mathsf{Fix}\,}T$ allows one to sidestep complications arising from the not-so-exotic occurrence of fixed point mappings that are almost nonexpansive at some points in $\operatorname{\mathsf{Fix}\,}T$ and not at others (see Example 2.5ii). It would be too restrictive in the statement of the theorem, however, to have $S\subseteq\operatorname{\mathsf{Fix}\,}T$, since this does not allow one to tackle inconsistent feasibility, studied in depth in Section 3.1. In particular, we have in mind the situation where sets $A$ and $B$ do not intersect, but still the alternating projections mapping $T_{AP}:=P_{A}P_{B}$ has nice properties at points in $B$ that, while not fixed points, at least locally are nearest to $A$. The full richness of the structure is used in Theorem 3.14 were we establish, for the first time, sufficient conditions for local linear convergence of the method of cyclic projections for nonconvex inconsistent feasibility.

Proof of Theorem 2.15 If ${\mathcal{O}}\cap{\mathcal{V}}={\mathcal{O}}$ there is nothing to prove. Assume, then, that there is some $x\in\left({\mathcal{O}}\cap\Lambda\right)\setminus\left({\mathcal{V}}\cap\Lambda\right)$. Choose any $x^{+}\in Tx$ and define ${\overline{x}}^{+}\in T{\overline{x}}$ for ${\overline{x}}\in P_{S}x$. Inequality (38) implies

Assumption a and Proposition 2.4iii, together with (42) then yield

Note in particular that $0\leq 1+\varepsilon-\frac{1-\alpha}{\alpha\kappa^{2}}$. Since ${\overline{x}}^{+}\in T({\overline{x}})\subset\operatorname{\mathsf{Fix}\,}T\cap S$, this proves the first statement.

If, in addition, $\kappa<\sqrt{\frac{1-\alpha}{\varepsilon\alpha}}$ then $c:=\left(1+\varepsilon-\frac{1-\alpha}{\alpha\kappa^{2}}\right)^{1/2}<1$. Since clearly $S\supset\operatorname{\mathsf{Fix}\,}T\cap S$, (39) yields

If $x^{1}\in{\mathcal{O}}\setminus{\mathcal{V}}$ then the first part of this theorem yields

Proceeding inductively then, the relation $\operatorname{dist}(x^{j},\operatorname{\mathsf{Fix}\,}T\cap S)\leq c^{j}\operatorname{dist}(x^{0},S)$ holds until the first time $x^{j-1}\notin{\mathcal{O}}\setminus{\mathcal{V}}$. $\Box$

The inequality (39) by itself says nothing about convergence of the iteration $x^{j+1}=Tx^{j}$, but it does clearly indicate what needs to hold in order for the iterates to move closer to a fixed point of $T$. This is stated explicitly in the next corollary.

$T$ is pointwise almost averaged at all $y\in S$ with violation $\varepsilon$ and averaging constant $\alpha$ on ${\mathcal{O}}_{\overline{\delta}}\cap\Lambda$, and

at each $y^{+}\in Ty$ for all $y\in S$ there exists a $\kappa\in\left[0,\sqrt{\frac{1-\alpha}{\varepsilon\alpha}}\right)$ such that

at each $x^{+}\in Tx$ for all $x\in\left({\mathcal{O}}_{\overline{\delta}}\cap\Lambda\right)\setminus\left({\mathcal{V}}_{\delta}\cap\Lambda\right)$.

Then for any $x^{0}$ close enough to $S$ the iterates $x^{i+1}\in Tx^{i}$ satisfy $\operatorname{dist}(x^{i},\operatorname{\mathsf{Fix}\,}T\cap S)\to 0$ as $i\rightarrow\infty$.

In the latter case, since $x^{(0,0)}\in{\mathcal{O}}_{{\overline{\delta}}_{0}}\cap\Lambda$, Theorem 2.15 shows that

for $c_{0}:=\sqrt{1+\varepsilon_{0}-\frac{1-\alpha_{0}}{\kappa_{0}^{2}\alpha_{0}}}<1$. Moreover, clearly $\operatorname{dist}\left(x^{(0,1)},S\right)\leq\operatorname{dist}\left(x^{(0,1)},\operatorname{\mathsf{Fix}\,}T\cap S\right)$, so in either case $x^{(0,1)}\in{\mathcal{O}}_{{\overline{\delta}}_{0}}$, and the alternative reduces to either $x^{(0,1)}\in{\mathcal{V}}_{\delta_{0}}$ or $x^{(0,1)}\notin{\mathcal{V}}_{\delta_{0}}$. Proceeding by induction for some $j\geq 1$ it holds that $x^{(0,\nu)}\in\left({\mathcal{O}}_{{\overline{\delta}}_{0}}\cap\Lambda\right)\setminus\left({\mathcal{V}}_{\delta_{0}}\cap\Lambda\right)$ for all $\nu=0,1,2\dots j-1$ and $x^{(0,j)}\in{\mathcal{O}}_{{\overline{\delta}}_{0}}\cap\Lambda$ with either $x^{(0,j)}\notin{\mathcal{V}}_{\delta_{0}}$ or $x^{(0,j)}\in{\mathcal{V}}_{\delta_{0}}$. If $x^{(0,j)}\notin{\mathcal{V}}_{\delta_{0}}$, then since $x^{(0,j)}\in{\mathcal{O}}_{{\overline{\delta}}_{0}}\cap\Lambda$, by Theorem 2.15,

To see this, suppose that there is no such $J_{0}$. Then $x^{(0,j)}\in\left({\mathcal{O}}_{{\overline{\delta}}_{0}}\cap\Lambda\right)\setminus\left({\mathcal{V}}_{\delta_{0}}\cap\Lambda\right)$ and

for all $j\geq 1$. Since, by assumption $c_{0}<1$, it holds that $\operatorname{dist}\left(x^{(0,j)},\operatorname{\mathsf{Fix}\,}T\cap S\right)\to 0$ at least linearly with constant $c_{0}$, in contradiction with the assumption that $x^{(0,j)}\notin{\mathcal{V}}_{\delta_{0}}$ for all $j$.

So $\operatorname{dist}\left(x^{i},\operatorname{\mathsf{Fix}\,}T\cap S\right)\to 0$ as $i\to\infty$. As this is just a reindexing of the Picard iteration, this completes the proof.

An interesting avenue of investigation would be to see to what extent the proof mining techniques of could be applied to quantify convergence in the present setting.

3 Metric regularity

The key insight into condition b of Theorem 2.15 is the connection to metric regularity of set-valued mappings (cf., ). This approach to the study of algorithms has been advanced by several authors . We modify the concept of metric regularity with functional modulus on a set suggested in [35, Definition 2.1 (b)] and [36, Definition 1 (b)] so that the property is relativized to appropriate sets for iterative methods. 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$.

Relaxing the requirements on the sets $U$ and $V$ from neighborhoods to the more ambiguous sets in Definition 2.17 allows the same definition and terminology to unambiguously cover well-known relaxations of metric regularity such as metric subregularity ($U$ is a neighborhood of ${\overline{x}}$ and $V=\{{\overline{y}}\}$, ) and metric hemi/semiregularity ($U=\{{\overline{x}}\}$ and $V$ is a neighborhood of ${\overline{y}}$ [55, Definition 1.47]). For our purposes, we will use the flexibility of choosing $U$ and $V$ in Definition 2.17 to exclude the reference point ${\overline{x}}$ and to isolate the image point ${\overline{y}}$. This is reminiscent of the Kurdyka-Łojasiewicz (KL) property for functions which requires that the subdifferential posses a sharpness property near (but not at) critical points of the function. However, since the restriction of $V$ to a point features prominently in our development, we retain the terminology metric subregularity to ease the technicality of the presentation. The reader is cautioned, however, that our usage of metric subregularity does not precisely correspond to the usual definition (see ) since we do not require the domain $U$ to be a neighborhood.

$T$ is pointwise almost averaged at all $y\in S$ with averaging constant $\alpha_{i}$ and violation $\varepsilon_{i}$ on $S_{\gamma^{i}{\overline{\delta}}}$, and

$\operatorname{dist}\left(x,S\right)\leq\operatorname{dist}\left(x,\Phi^{-1}({\overline{y}})\cap\Lambda\right)$ for all $x\in R_{i}$ and ${\overline{y}}\in\Phi(P_{S}(x))\setminus\Phi(x)$,

$\Phi$ is metrically regular with gauge $\mu_{i}$ relative to $\Lambda$ on $R_{i}\,\times\,\Phi(P_{S}(R_{i}))$, where $\mu_{i}$ satisfies

Then, for any $x^{0}\in\Lambda$ close enough to $S$, the iterates $x^{j+1}\in Tx^{j}$ satisfy $\operatorname{dist}\left(x^{j},\operatorname{\mathsf{Fix}\,}T\cap S\right)\to 0$ and

where $c_{i}:=\sqrt{1+\varepsilon_{i}-\left(\tfrac{1-\alpha_{i}}{\kappa_{i}^{2}\alpha_{i}}\right)}<1$.

In particular, if $\varepsilon_{i}$ is bounded above by ${\overline{\varepsilon}}$ and $\kappa_{i}\leq{\overline{\kappa}}<\sqrt{\frac{1-{\overline{\alpha}}}{{\overline{\alpha}}\,{\overline{\varepsilon}}}}$ for all $i$ large enough, then convergence is eventually at least linear with rate at most ${\overline{c}}:=\sqrt{1+{\overline{\varepsilon}}-\left(\tfrac{1-{\overline{\alpha}}}{{\overline{\kappa}}^{2}{\overline{\alpha}}}\right)}<1$.

The first inequality in (46) is a condition on the gauge function $\mu_{i}$ and would not be needed if the statement were limited to linearly metrically regular mappings. Essentially, it says that the gauge function characterizing metric regularity of $\Phi$ can be bounded above by a linear function. The second inequality states that the constant of metric regularity $\kappa_{i}$ is small enough relative to the violation of the averaging property $\varepsilon_{i}$ to guarantee a linear progression of the iterates through the region $R_{i}$.

Proof of Theorem 2.18. To begin, note that by assumption b, for any $x\in R_{i}$, ${\overline{x}}\in P_{S}(x)$, and ${\overline{y}}\in\Phi({\overline{x}})$ with ${\overline{y}}\notin\Phi(x)$,

Let ${\overline{y}}={\overline{x}}^{+}-{\overline{x}}$ for ${\overline{x}}^{+}\in T{\overline{x}}$. The above statement yields

whence (47) holds with constant $c_{i}<1$ given by (46).

The final claim of the theorem follows immediately.

When $S=\operatorname{\mathsf{Fix}\,}T\cap\Lambda$ in Theorem 2.18, the condition b bi can be dropped from the assumptions, as the next corollary shows.

$T$ is pointwise almost averaged at all $y\in\operatorname{\mathsf{Fix}\,}T\cap\Lambda$ with averaging constant $\alpha_{i}$ and violation $\varepsilon_{i}$ on $S_{\gamma^{i}{\overline{\delta}}}$, and

$\Phi$ is metrically subregular for on $R_{i}$ (metrically regular on $R_{i}\times\{0\}$) with gauge $\mu_{i}$ relative to $\Lambda$, where $\mu_{i}$ satisfies

Then, for any $x^{0}\in\Lambda$ close enough to $\operatorname{\mathsf{Fix}\,}T\cap\Lambda$, the iterates $x^{j+1}\in Tx^{j}$ satisfy $\operatorname{dist}\left(x^{j},\operatorname{\mathsf{Fix}\,}T\cap\Lambda\right)\to 0$ and

where $c_{i}:=\sqrt{1+\varepsilon_{i}-\left(\tfrac{1-\alpha_{i}}{\kappa_{i}^{2}\alpha_{i}}\right)}<1$.

In particular, if $\varepsilon_{i}$ is bounded above by ${\overline{\varepsilon}}$ and $\kappa_{i}\leq{\overline{\kappa}}<\sqrt{\frac{1-{\overline{\alpha}}}{{\overline{\alpha}}\,{\overline{\varepsilon}}}}$ for all $i$ large enough, then convergence is eventually at least linear with rate at most ${\overline{c}}:=\sqrt{1+{\overline{\varepsilon}}-\left(\tfrac{1-{\overline{\alpha}}}{{\overline{\kappa}}^{2}{\overline{\alpha}}}\right)}<1$.

The following example explains why gauge metric regularity on a set (Definition 2.17) fits well in the framework of Theorem 2.18, whereas the conventional metric (sub)regularity does not.

Using Corollary 2.19, we characterize sublinear convergence in this example as linear convergence on annular sets. To proceed, we set

This corresponds to setting ${\overline{\delta}}=1$ and $\gamma=1/2$ in Corollary 2.19. The task that remains is to estimate the constant of metric subregularity, $\kappa_{i}$, of $\Phi$ on each $R_{i}$. Indeed, we have

where $f:[0,\infty)\to[0,\infty)$ is given by $f(t):=t\left(1-1/\sqrt{t^{2}+1}\right)$. The function $f$ is continuous strictly increasing and satisfies $f(0)=0$ and $\lim_{t\to\infty}f(t)=\infty$. Hence, $f$ is a gauge function.

We can now characterize sublinear convergence of $P_{A}P_{B}$ explicitly without resorting to annular sets. Note first that since $f(t)<t$ for all $t\in(0,\infty)$ the function $g:[0,\infty)\to[0,\infty)$ given by

is a gauge function and satisfies $g(t)<t$ for all $t\in(0,\infty)$. Note next that $T:=P_{A}P_{B}$ is (for all points in $A$) averaged with constant $2/3$ together with (53), we get for any $x\in A$

The following proposition, taken from , characterizes metric subregularity in terms of the graphical derivative defined by (9).

If, in addition, $T$ is single-valued and continuously differentiable on $U$, then the two conditions hold if and only if $\nabla\Phi$ has rank $n$ at ${\overline{x}}$ with $\left\|\left[\left[\nabla\Phi\left(x\right)\right]^{\intercal}\right]^{-1}\right\|\leq\kappa$ for all $x$ on $U$.

While the characterization (54) appears daunting, the property comes almost for free for polyhedral mappings.

Proof. If $T$ is polyhedral, so is $\Phi^{-1}:=(T-\operatorname{Id})^{-1}$. The statement now follows from [28, Propositions 3I.1 and 3I.2], since $\Phi^{-1}$ is polyhedral and ${\overline{x}}$ is an isolated point of $\Phi^{-1}(0)\cap\Lambda$.

where $c=\sqrt{1+\varepsilon-\frac{1-\alpha}{\kappa^{2}\alpha}}$ and $\kappa$ is the modulus of metric subregularity of $\Phi:=T-\operatorname{Id}$ for on $U$ relative to $\Lambda$. If, in addition $\kappa<\sqrt{(1-\alpha)/(\alpha\varepsilon)}$, then the fixed point iteration $x^{j+1}\in Tx^{j}$ converges linearly to ${\overline{x}}$ with rate $c<1$ for all $x^{0}\in U\cap\Lambda$.

Proof. The result follows immediately from Proposition 2.23 and Corollary 2.19.

Applications

The idea of the previous section is simple. Formulated as Picard iterations of a fixed point mapping $T$, in order to establish the quantitative convergence of an algorithm, one must establish two properties of this mapping: first that $T$ is almost averaged and second that it is metrically subregular at fixed points relative to an appropriate subset. This section serves as a tutorial for how to do this for fundamental first-order algorithms. Each of the problems studied below represents a distinct region on the map of numerical analysis, each with its own dialect. Part of our goal is to show that the phenomena that these different dialects describe sort into one of the two more general properties of fixed point mappings established above. While the technicalities can become quite dense, particularly for feasibility, the two principles above offer a reliable guide through the details.

The feasibility problem is to find ${\overline{x}}\in\cap_{j=1}^{m}\Omega_{j}$. If the intersection is empty, the problem is called inconsistent, but a meaningful solution still can be found in the sense of best approximation in the case of just two sets, or in some other appropriate sense when there are three or more sets. The most prevalent algorithms for solving these problems are built on projectors onto the individual sets (indeed, we are aware of no other approach to the problem). The regularity of the fixed point mapping $T$ that encapsulates a particular algorithm (in particular, pointwise almost averaging and coercivity at the fixed point set) stems from the regularity of the underlying projectors and the way the projectors are put together to construct $T$. Our first task is to show in what way the regularity of the underlying projectors is inherited from the regularity of the sets $\Omega_{j}$.

The following definition of what we call elemental regularity was first presented in [42, Definition 5]. This places under one schema the many different kinds of set regularity appearing in .

$\Omega$ is elementally subregular of order $\sigma$ relative to $\Lambda$ at ${\overline{x}}$ for $\left({\overline{y}},{\overline{v}}\right)$ with constant $\varepsilon$ if there exists a neighborhood $U$ of ${\overline{x}}$ such that

The set $\Omega$ is said to be uniformly elementally subregular of order $\sigma$ relative to $\Lambda$ at ${\overline{x}}$ for $\left({\overline{y}},{\overline{v}}\right)$ if for any $\varepsilon>0$ there is a neighborhood $U$ (depending on $\varepsilon$) of ${\overline{x}}$ such that (55) holds.

The set $\Omega$ is said to be elementally regular of order $\sigma$ at ${\overline{x}}$ for $\left({\overline{y}},{\overline{v}}\right)$ with constant $\varepsilon$ if it is elementally subregular of order $\sigma$ relative to $\Lambda=\Omega$ at ${\overline{x}}$ for all $\left({\overline{y}},v\right)$ with constant $\varepsilon$ where $v\in{N}_{\Omega}({\overline{y}})\cap V$ for some neighborhood $V$ of ${\overline{v}}$.

The set $\Omega$ is said to be uniformly elementally regular of order $\sigma$ at ${\overline{x}}$ for $\left({\overline{y}},{\overline{v}}\right)$ if it is uniformly elementally subregular of order $\sigma$ relative to $\Lambda=\Omega$ at ${\overline{x}}$ for all $\left({\overline{y}},v\right)$ where $v\in{N}_{\Omega}({\overline{y}})\cap V$ for some neighborhood $V$ of ${\overline{v}}$.

If $\Lambda=\{{\overline{x}}\}$ in i or ii, then the respective qualifier “relative to” is dropped. If $\sigma=0$, then the respective qualifier “of order” is dropped in the description of the properties. The modulus of elemental (sub)regularity is the infimum over all $\varepsilon$ for which (55) holds.

In all properties in Definition 3.1, ${\overline{x}}$ need not be in $\Lambda$ and ${\overline{y}}$ need not be in either $U$ or $\Lambda$. In case of order $\sigma=0$, the properties are trivial for any constant $\varepsilon\geq 1$. When saying a set is not elementally (sub)regular but without specifying a constant, it is meant for any constant $\varepsilon<1$.

(circle) The humble circle is central to the phase retrieval problem,

(Packman eating a piece of pizza) Consider again the sets

The set $B$, however, is not elementally regular at ${\overline{x}}=0$ for any $(0,v)\in\operatorname{gph}{{N}_{B}}$ because by choosing $x=tv\in B$ (where $0\neq v\in B\cap{N}_{B}(0)$, $t\downarrow 0$), we get $\left\langle v,~{}x\right\rangle=\|v\|\|x\|>0$.

To see how the language of elemental regularity unifies the existing terminology, we list the following equivalences first established in [42, Proposition 4].

Let $A\cap B\neq\emptyset$ and suppose that there is a neighborhood $W$ of ${\overline{x}}\in A\cap B$ and a constant $\varepsilon>0$ such that for each

Then, $A$ is $\sigma$-Hölder regular relative to $B$ at ${\overline{x}}$ in the sense of [59, Definition 2] with constant $c=\varepsilon^{2}$ and neighborhood $W$ of ${\overline{x}}$ if and only if $A$ is elementally subregular of order $\sigma$ relative to $A\cap P^{-1}_{B}\left(a+v\right)$ at ${\overline{x}}$ for each $(a,v)\in V$ with constant $\varepsilon=\sqrt{c}$ and the respective neighborhood $U(a,v)$.

The set $A$ is Clarke regular at ${\overline{x}}\in A$ [68, Definition 6.4] if and only if $A$ is uniformly elementally regular at ${\overline{x}}$ for all $({\overline{x}},v)$ with $v\in{N}_{A}({\overline{x}})$. Consequently, Clarke regularity implies $(\varepsilon,\delta)$-regularity.

The following relations reveal a similarity to almost firm-nonexpansiveness of the projector onto elementally subregular sets on the one hand, and almost nonexpansiveness of the same projector on the other.

holds with $y^{\prime}=y+v$ whenever $x^{\prime}\in U\cap\Lambda$ and $x\in P_{\Omega}x^{\prime}$.

holds with $y^{\prime}=y+v$ whenever $x^{\prime}\in U\cap\Lambda$ and $x\in P_{\Omega}x^{\prime}$.

Proof. i: This is just a rearrangement of the inequality in (55). ii: Follows by applying the Cauchy-Schwarz inequality to the inner product on the right hand side of (58).

The next theorem is an update of [32, Theorem 2.14] to the current terminology. It establishes the connection between elemental subregularity of a set and almost nonexpansiveness/averaging of the projector onto that set. Since the cyclic projections algorithm applied to inconsistent feasibility problems involves the properties of the projectors at points that are outside the sets, we show the how the properties depend on whether the reference points are inside or outside of the sets. The theorem uses the symbol $\Lambda$ to indicate subsets of the sets and the symbol $\Lambda^{\prime}$ to indicate points on some neighborhood whose projection lies in $\Lambda$. Later, the sets $\Lambda^{\prime}$ will be specialized in the context of cyclic projections to sets of points $S_{j}$ whose projections lie in $\Omega_{j}$. One thing to note in the theorem below is that the almost nonexpansive/averaging property degrades rapidly as the reference points move away from the sets. Our estimate is severe and could be sharpened somewhat, but it serves our purposes.

with constant $\varepsilon$ on the neighborhood $U$, then the following hold.

The projector $P_{\Omega}$ is pointwise almost nonexpansive at each $y\in\Lambda$ on $U$ with violation $\varepsilon^{\prime}:=2\varepsilon+\varepsilon^{2}$. That is, at each $y\in\Lambda$

Let $\varepsilon\in[0,1)$. The projector $P_{\Omega}$ is pointwise almost nonexpansive at each $y^{\prime}\in\Lambda^{\prime}$ with violation ${\widetilde{\varepsilon}}$ on $U$ for ${\widetilde{\varepsilon}}:=4\varepsilon/\left(1-\varepsilon\right)^{2}$. That is, at each $y^{\prime}\in\Lambda^{\prime}$

The projector $P_{\Omega}$ is pointwise almost firmly nonexpansive at each $y\in\Lambda$ with violation $\varepsilon^{\prime}_{2}:=2\varepsilon+2\varepsilon^{2}$ on $U$. That is, at each $y\in\Lambda$

Let $\varepsilon\in[0,1)$. The projector $P_{\Omega}$ is pointwise almost firmly nonexpansive at each $y^{\prime}\in\Lambda^{\prime}$ with violation ${\widetilde{\varepsilon}}_{2}:=4\varepsilon\left(1+\varepsilon\right)/\left(1-\varepsilon\right)^{2}$ on $U$. That is, at each $y^{\prime}\in\Lambda^{\prime}$

The reflector $R_{\Omega}$ is pointwise almost nonexpansive at each $y\in\Lambda$ (respectively, $y^{\prime}\in\Lambda^{\prime}$) with violation $\varepsilon^{\prime}_{3}:=4\varepsilon+4\varepsilon^{2}$ (respectively, ${\widetilde{\varepsilon}}_{3}:=8\varepsilon\left(1+\varepsilon\right)/\left(1-\varepsilon\right)^{2}$ ) on $U$; that is, for all $y\in\Lambda$ (respectively, $y^{\prime}\in\Lambda^{\prime}$)

Proof. First, some general observations about the assumptions. The projector is nonempty since $\Omega$ is closed. Note also that, since $\Lambda\subset\Omega$, $P_{\Omega}y=y$ for all $y\in\Lambda$. Since $\Lambda\subset\Lambda^{\prime}$, $\Omega$ is elementally subregular at ${\overline{x}}$ relative to $\Lambda$ for each $(x,v)\in V$ with constant $\varepsilon$ on the neighborhood $U$ of ${\overline{x}}$, though the constant $\varepsilon$ may not be optimal for $\Lambda$ even if it is optimal for $\Lambda^{\prime}$. Finally, for all $x^{\prime}\in U$ it holds that $(x,x^{\prime}-x)\in V$ for all $x\in P_{\Omega}(x^{\prime})$. To see this, take any $x^{\prime}\in U$ and any $x\in P_{\Omega}(x^{\prime})$. Then $v=x^{\prime}-x\in N^{\text{\rm prox}}_{\Omega}(x)$ and, by definition $(x,v)\in V$.