Scaled relative graphs: nonexpansive operators via 2D Euclidean geometry

Many iterative methods in applied mathematics can be thought of as fixed-point iterations, and such algorithms are usually analyzed analytically, with inequalities. In this paper, we present a geometric approach to analyzing contractive and nonexpansive fixed point iterations with a new tool called the scaled relative graph. The SRG provides a correspondence between nonlinear operators and subsets of the 2D plane. Under this framework, a geometric argument in the 2D plane becomes a rigorous proof of convergence.

1. The winding number of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point. A definition, based on the complex analysis and the Cauchy residue theorem can be found in Section 4.1 of [2].

We thank Pontus Giselsson for the illuminating discussion on metric subregularity. We thank Minyong Lee and Yeoil Yoon for helpful discussions on inversive geometry and its use in high school mathematics competitions. We thank Xinmeng Huang for the aid in drawing Figure 5. We thank the Erwin Schrödinger Institute and the organizers of its workshop in February 2019, which provided us with fruitful discussions and helpful feedback that materially improved this paper.

Authors and Affiliations

1. Department of Mathematical Sciences, Seoul National University, Seoul, South Korea

   Ernest K. Ryu

2. Department of Mathematics, University of California, Los Angeles, USA

   Robert Hannah & Wotao Yin

Corresponding author

Correspondence to Wotao Yin.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was partially supported by AFOSR MURI FA9550-18-1-0502, NSF Grant DMS-1720237, ONR Grant N000141712162, the New Faculty Startup Fund from Seoul National University, the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) [No. 2020R1F1A1A01072877], and the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) [No. 2017R1A5A1015626].

Further discussion

1.1 The role of maximality

A fixed-point iteration \(x^{k+1}=Tx^k\) becomes undefined if its iterates ever escape the domain of T. This is why we assume the monotone operators are maximal as maximality ensures \({\mathrm {dom}( J_{\alpha A})}=\mathcal {H}\). The results of this work are otherwise entirely independent of the notion of maximality.

In Sect. 2, we define \({\mathcal {M}}\) to contain all monotone operators (maximal or not). This choice is necessary to make \({\mathcal {M}}\) SRG-full. For the other classes \({\mathcal {L}}_{L}\), \({\mathcal {C}}_{\beta }\), \({\mathcal {M}}_{\mu }\), and \({\mathcal {N}}_\theta \), we make no restriction on the domain or maximality so that they can be SRG-full.

1.2 Minkowski-type set notation

Given \(\alpha \in \mathbb {R}\) and sets \(U,V\subseteq \mathcal {H}\), write

Notice that if either U or V is \(\emptyset \), then \(U+V=\emptyset \).

Given \(Z,W\subseteq \mathbb {C}\), write

Given \(\alpha \in \mathbb {C}\), \(\alpha \ne 0\), and \(Z\subseteq \overline{\mathbb {C}}\), write

Given a class of operators \({\mathcal {A}}\) and \(\alpha \ne 0\), write

Given classes of operators \({\mathcal {A}}\) and \({\mathcal {B}}\) and \(\alpha >0\), write

1.3 SRG-full classes

There is one degenerate case to keep in mind for the sake of rigor. The SRG-full class of operators \({\mathcal {A}}_\text {null}\) represented by \(h(a,b,c)=a+b+|c|\) has \({\mathcal {G}}({\mathcal {A}}_\text {null})=\emptyset \). However, the class \({\mathcal {A}}_\text {null}\) is not itself empty; it contains operators whose graph contains zero or one pair, i.e., \(A\in {\mathcal {A}}_\text {null}\) if and only if we have either a) \({\mathrm {dom}(A)}=\emptyset \) or b) \({\mathrm {dom}(A)}=x\) and \(Ax=\{y\}\) for some \(x,y\in \mathcal {H}\).

Theorem 3 does not apply when the operator classes are not SRG-full. For example, although

we have the strict containment

Invariant circle number

Let \({\mathcal {A}}\) be an SRG-full class such that \({\mathcal {G}}({\mathcal {A}})\ne \emptyset \) and \({\mathcal {G}}({\mathcal {A}})\ne \overline{\mathbb {C}}\). Define the circle number of \({\mathcal {A}}\) as

which is a positive integer or \(\infty \). For example, \({\mathcal {M}}\cap {\mathcal {L}}_1\) has circle number 2 since

In this section, we show that the circle number of an operator class is invariant under certain operations. This is analogous to how the genus or the winding number are topological invariants under homeomorphisms. That it is impossible to continuously deform a donut into a sphere since they have different numbers of holes, an invariant, is a standard argument of topology. The circle number serves as an analogous invariant for operator classes.

Theorem 10

The circle number of an SRG-full operator class is invariant under non-zero pre and post-scalar multiplication, addition by identity, and inversion.

Proof

Let T be a one-to-one mapping from an operator to an operator and let \(T'\) the the corresponding one-to-one mapping from \(\overline{\mathbb {C}}\) to \(\overline{\mathbb {C}}\). In particular, consider the following four cases: first \(T(A)=\alpha A\) and \(T'(z)=\alpha z\), second \(T(A)= A\alpha \) and \(T'(z)=\alpha z\), third \(T(A)= I+A \) and \(T'(z)=1+z\), and fourth \(T(A)= A^{-1} \) and \(T'(z)={\bar{z}}^{-1}\).

If

then

where \(T'(B_1),\dots ,T'(B_k)\) are each a disk or a half-space. Therefore, the circle number of \(T({\mathcal {A}})\) satisfies

Since T and \(T'\) are invertible mappings, the argument goes in the other direction as well, and we conclude that the infimums are equal. \(\square \)

Corollary 3

There is no one-to-one mapping from \(\mathcal {M}\) to \(\mathcal {M}\cap \mathcal {L}_L\) constructed via pre and post-scalar multiplication, addition with the identity operator, and operator inversion.

Such one-to-one mappings between operator classes are used for translating a nice result on a simple operator class to another operator class. In [7, 8, 64] the maximal monotone extension theorem was translated to extension theorems of other operator classes. Corollary 3 shows that this approach will not work for \(\mathcal {M}\cap \mathcal {L}_L\), a class of operators considered by the extragradient method [38], forward-backward-forward splitting [68], and other related methods [14, 45]. In fact, [64] shows that certain simple interpolation condition for \({\mathcal {M}}\) fails for \(\mathcal {M}\cap \mathcal {L}_L\).

Spherical triangle inequality: \(|\theta -\varphi |\le \psi \le \theta +\varphi \)

Full size image

Deferred proofs

Fact 17

(Spherical triangle inequality) Any nonzero \(a,b,c\in \mathcal {H}\) satisfies

Figure 8 illustrates the inequality. We use the spherical triangle inequality in Theorem 7 to argue that there is no need to consider a third dimension and that we can continue the analysis in 2D.

Proof of spherical triangle inequality

Although this result is known, we provide a proof for completeness. Without loss of generality, assume a, b, and c are unit vectors. Let \(\theta =\angle (a,b)\) and \(\varphi =\angle (b,c)\), and without loss of generality, assume \(\theta \ge \varphi \). Then we have

where u and v are unit vectors orthogonal to b, and

Since \(\theta ,\varphi \in [0, \pi ]\), we have \(\sin \theta \sin \varphi \ge 0\). Since \(\Vert u\Vert =\Vert v\Vert =1\), we have \(|\langle u,v\rangle | \le 1\). Therefore

Since \(\cos (\alpha \pm \beta )=\cos \alpha \cos \beta \mp \sin \alpha \sin \beta \), [2, p. 72, 4.3.17] we have

and we conclude

\(\square \)

Proof of Fact 7

First consider the case \(\mu <1/(2\beta )\). By Proposition 1 and Theorem 4, we have the geometry

To clarify, O is the center of the circle with radius \({\overline{OB}}\) (lighter shade) and C is the center of the circle with radius \({\overline{AC}}={\overline{CB}}\) defining the inner region (darker shade). With two applications of the Pythagorean theorem, we get

Since \(\overline{B'B}\) is a chord of circle O, it is within the circle. Since 2 non-identical circles intersect at at most 2 points, and since A is within circle O, arc is within circle O. Finally, the region bounded by (darker shade) is within circle O (lighter shade).

In the cases \(\mu =1/(2\beta )\) and \(\mu >1/(2\beta )\), we have a slightly different geometry, but the same arguments and calculations hold.

The containment holds for R and fails for smaller R. Since \({\mathcal {L}}_R\) is SRG-full by Theorem 2, the containment of the SRG in \(\overline{\mathbb {C}}\) equivalent to the containment of the class. \(\square \)

We quickly state Stewart’s theorem [65], which we use for the Proof of Fact 12. For a triangle \(\triangle ABC\) and Cevian \({\overline{CD}}\) to the side \({\overline{AB}}\),

the lengths of the line segments satisfy

Full Proof of Fact 12 By Proposition 1 and Theorems 4 and 5, we have the geometry

A closer look gives us

To clarify, B is the center of the circle with radius \({\overline{BA}}\) and C is the center of the circle with radius \({\overline{CA}}\). By Stewart’s theorem [65], we have

Since 2 non-identitcal circles intersect at at most 2 points, and since D is within circle B, arc is within circle O. By the same reasoning, arc is within circle O. Finally, the region bounded by (darker shade) is within circle O (lighter shade).

The containment holds for R and fails for smaller R. Since \({\mathcal {L}}_R\) is SRG-full by Theorem 2, the containment of the SRG in \(\overline{\mathbb {C}}\) equivalent to the containment of the class. \(\square \)

Proof of Fact 16

Let

First, we show \(Q=[0,1]C=[0,1]Q\). To clarify, [0, 1] is the set of real numbers between 0 and 1 and [0, 1]C and [0, 1]Q are Minkowski products of sets of complex numbers. Given any point \(A\in Q\backslash C\), define \(A'\) as the nonzero intersection of the line extending \({\overline{OA}}\) and circle C. Since A is on the line and inside the circle, the nonzero intersection \(A'\) exists.

Since \(A\in \overline{OA'}\subseteq [0,1]C\), we have \(Q\subseteq [0,1]C\). On the other hand, \(Q\supseteq [0,1]C\) follows from noting that given any point \(A'\) on C, the line segment \(\overline{OA'}\) is a chord of the circle C and therefore is within the disk Q. Therefore, \(Q=[0,1]C\). As a corollary, we have \(Q=[0,1]C=([0,1][0,1])C=[0,1]([0,1]C)=[0,1]Q\).

Next, define

In geometric terms, this construction takes a point on the circle C, draws the disk whose diameter is the line segment between this point and the origin, and takes the union of such disks.

The dashed circle is the unit circle. The solid circle is C. The shaded circles represent instances of \(S_{\varphi _1}\). We can characterize \({\mathcal {G}}({\mathcal {N}}_{1/2}{\mathcal {N}}_{1/2})\) by analyzing this construction since

by Proposition 1 and Theorem 7.

We now show \(S=\left\{ re^{i\varphi }\,|\,0\le r\le \cos ^2(\varphi /2)\right\} \). This fact is known and can be analytically derived through the envelope theorem [60, Exercise 5.22]. We provide a geometric proof, which was inspired by [37, Exercise 4.15].

Throughout this proof, we write \({\mathcal {I}}:\overline{\mathbb {C}}\rightarrow \overline{\mathbb {C}}\) for the mapping \({\mathcal {I}}(z)={\bar{z}}^{-1}\). We map S into the inverted space, i.e., we analyze

Again, \({\mathcal {I}}(z)={\bar{z}}^{-1}\). The dashed circle, the unit circle, is mapped onto itself. Circle C, the solid circle, is mapped to \({\mathcal {I}}(C)\), the verticle line going through 1. Each shaded circle \(S_{\varphi _1}\) is mapped to a half-space \({\mathcal {I}}(S_{\varphi _1})\). Let point A be the nonzero intersection between C and the boundary of \(S_{\varphi _1}\). Then point \({\mathcal {I}}(A)\) is the non-infinite intersection between \({\mathcal {I}}(C)\) and the boundary of \({\mathcal {I}}(S_{\varphi _1})\). By construction, \({\overline{OA}}\) is the diameter of \(S_{\varphi _1}\). The (infinite) line containing O, A, and \({\mathcal {I}}(A)\) is mapped onto itself, excluding the origin. Since \({\mathcal {I}}\) is conformal, the right angle at A between the boundary of \(S_{\varphi _1}\) and the diameter \({\overline{OA}}\) is mapped to a right angle between boundary of \({\mathcal {I}}(S_{\varphi _1})\) and \(\overline{O{\mathcal {I}}(A)}\).

Next, we show that the union of the half-spaces is described by a parabola. Define line D as the vertical line going through 2. Consider any point \(A'\) on the line \({\mathcal {I}}(C)\). Consider the line through \(A'\) perpendicular to \(\overline{OA'}\) and the half-space to the right of the line including \(\infty \). Define point E as the intersection of line D and the line extending \({\overline{OA}}\). Draw a line through point E perpendicular to line D, and define point B as the intersection of this line with the boundary of the half-space. Since E is within the half-space and the boundary of the half-space is not horizontal, this intersection exists and B is to the left of E. Since \(\overline{OA'}=\overline{A'E}\), we have \(\triangle BA'O\cong \triangle BA'E\) by the side-angle-side (SAS) congruence, and \({\overline{OB}}={\overline{BE}}\). The union of all such points corresponding to B forms a parabola. with directrix D, focus (0, 0) and vertex (1, 0).

The boundary of the half-space is tangent to the parabola at B, i.e., the line intersects the parabola at no other point. To see why, consider any other point \(B'\) on the boundary of the half-space. Then \(\overline{OB'}=\overline{B'E}\) by SAS congruence. However, \(\overline{B'E}\) is not perpendicular to D, i.e., \(\overline{B'E}\) is not a horizontal line. Therefore \(\overline{OB'}\) is longer than the distance of \(B'\) to D, and therefore \(B'\) is not on the parabola. Since each half-space is tangent to the parabola at B, all points to the right of B are in \({\mathcal {I}}(S)\) and no points strictly to the left of the parabola are in \({\mathcal {I}}(S)\). Therefore \({\mathcal {I}}(S)\) is characterized by the closed region to the right of the parabola including \(\infty \).

The region exterior to the circle centered at \(-1\) with radius 2 contains the region towards the right of the parabola. This is easily verified with calculus. The circle with the lighter shade corresponds to \({\mathcal {G}}({\mathcal {N}}_{2/3})\) by Proposition 1. Since \({\mathcal {N}}_{2/3}\) is SRG-full by Theorem 2, strict containment of the SRG in \(\overline{\mathbb {C}}\) implies strict containment of the class. The inverse curve of the parabola with the focus as the center of inversion is known as the cardioid and it has the polar coordinate representation \(r(\varphi )\le \cos ^2(\varphi /2)\). The expression of the Theorem is the region bounded by this curve. \(\square \)

Reprints and permissions