Computing scaled relative graph of composition of operators in Mathematica

Shuvomoy Das Gupta

November 17, 2020

This blog is based on a question I posted here on and the answer provided by user64494.

Suppose, we are given two operators A,BA,B, and we know their scale relative graphs, denoted by G(A)\mathcal{G}(A) and G(B)\mathcal{G}(B), respectively. We are interested to figure out the scaled relative graph of their composition AB:xA(B(x))AB:x\mapsto A(B(x)). For simplicity, we will assume that the regularity conditions under which G(AB)=G(A)G(B)\mathcal{G}(AB)=\mathcal{G}(A)\mathcal{G}(B) hold; for more details, please see the paper on scaled relative graph by Ryu et al.

Table of contents


As an example, let us assume that AA is β\beta-cocoercive and BB is θ\theta-averaged (θ(0,1)\theta\in (0,1)). Then, the scaled relative graph (SRG) of AA will be

G(A)={zCRe(z)βz2}, \mathcal{G}(A)=\left\{z \in \mathbf{C} \mid \rm{Re}(z) \geq \beta |z|^2\right\},

and the SRG of BB will be

G(B)={zC2(1θ)Re(z)z2+(12θ)}. \mathcal G(B)= \left\{ z\in \mathbf{C} \mid 2(1-\theta)\rm{Re}(z) \geq |z|^2 + (1-2\theta)\right\}.

For this example, let us assume, β=1/2,θ=1/2\beta = 1/2, \theta = 1/2.

Drawing individual SRGs

Let us first draw the individual SRGs for AA and BB.

SRG of AA. First, we draw the SRG of AA by typing the following code. We denote the real and imaginary variables corresponding to G(A)\mathcal G(A) by x,yx,y, respectively.

\[Beta] = 1/2;

(*Inequality that defines the SRG of A*)
gAineq = ComplexExpand[Re[z] - \[Beta]*Abs[z]^2 /. z -> x + I*y]

(*Plot the SRG of A*)
srgA = RegionPlot[gAineq >= 0, {x, -2, 2}, {y, -2, 2}]


We see that

G(A)={(x,y)gAineq(x,y)0}. \mathcal G(A) = \left\{ (x,y) \mid \texttt{gAineq}(x,y) \geq 0\right\}.

SRG of BB. First, we draw the SRG of BB by typing the following code. We denote the real and imaginary variables corresponding to G(B)\mathcal G(B) by s,ts,t, respectively.

\[Theta] = 1/2;

(*Inequality that defines the SRG of B*) 
gBineq = ComplexExpand[
  2 (1 - \[Theta]) Re[w] - Abs[w]^2 - (1 - 2 \[Theta]) /. w -> s + I t]

(*Plot the SRG of B*)
srgB = RegionPlot[gBineq >= 0, {s, -2, 2}, {t, -2, 2}]



G(B)={(s,t)gBineq(s,t)0}. \mathcal G(B) = \left\{ (s,t) \mid \texttt{gBineq}(s,t) \geq 0\right\}.

Quantifier definition of G(A)G(B)\mathcal {G}(A) \mathcal {G}(B)

We now write down the quantifier definition of G(A)G(B)\mathcal {G}(A) \mathcal {G}(B).

By definition:

z=x+iyG(A),w=s+itG(B)zw=u+ivG(A)G(B). z=x+ i y \in \mathcal {G}(A), w=s+it\in \mathcal{G}(B)\Leftrightarrow zw = u + iv \in \mathcal {G}(A) \mathcal {G}(B).

We can break down the equivalence above more by writing it down explicitly into real and imaginary parts.

(*Find out what zw is*)
 zw = ComplexExpand[(x + I y) (s + I t), Reals]

(*Find the imaginary component of zw*) 
v = Plus @@ (Cases[zw, _Complex _]/I)

(*Find the real component of zw*) u = Expand[zw - I v]

<img src="" alt="image-20201118084143443" style="zoom:67%;" />

So, in terms of quantifier notation, the set description of G(A)G(B)\mathcal {G}(A) \mathcal {G}(B) will be the following:

G(AB)=G(A)G(B)={(u,v)u=sxty,v=tx+sy,gAineq(x,y)0,gBineq(s,t)0}.(1) \begin{align*} & \mathcal{G}(AB)\\ & =\mathcal{G}(A)\mathcal{G}(B)\\ & =\left\{ (u,v)\mid u=sx-ty,v=tx+sy,\texttt{gAineq}(x,y)\geq0,\texttt{gBineq}(s,t)\geq0\right\}. \qquad(1) \end{align*}

Finding G(AB)\mathcal{G}(AB) explicitly

In (1)(1), we have G(AB)\mathcal{G}(AB) in a parametric form where we do not have u,vu,v explicitly, but it is expressed in terms of x,yx,y. To figure out the explicit description of G(AB)\mathcal{G}(AB), we use quantifier elimination technique in Mathematica. First step is to observe that:

(u,v)G(AB)x,y,s,tR(u=sxty, v=tx+sy, gAineq(x,y)0, gBineq(s,t)0). \begin{align*} & (u,v)\in\mathcal{G}(AB)\\ \Leftrightarrow & \exists_{x,y,s,t\in\mathbf{R}}\left(u=sx-ty,\;v=tx+sy,\;\texttt{gAineq}(x,y)\geq0,\;\texttt{gBineq}(s,t)\geq0\right). \end{align*}

We next write down this quantifier definition in Mathematica. (The rest of the code is self-contained, by only changing the defining inequalities for A,BA,B we can find G(AB)\mathcal{G}(AB) for any A,BA,B.)

(* Clear the memory *)

(* Set value of \[Beta] and \[Theta] *)
\[Beta] = 1/2; \[Theta] = 1/2;

(* Define gAineq[x,y], which defines the SRG of operator A via gAineq[x,y] >= 0 *)
gAineq[x_, y_] := 
  ComplexExpand[Re[z] - \[Beta]*Abs[z]^2 /. z -> x + I*y];

(* Define gBineq[s,t], which defines the SRG of operator B via gBineq[s,t] >= 0 *)
gBineq[s_, t_] := 
   2 (1 - \[Theta]) Re[w] - Abs[w]^2 - (1 - 2 \[Theta]) /. 
    w -> s + I t];

(* Define the quantifier definition for G(AB) *)
quantgAB = 
 Exists[{x, y, s, t}, 
  u == x s - y t && v == x t + y s && gAineq[x, y] >= 0 && 
   gBineq[s, t] >= 0]

which gives the output:

<img src="" alt="image-20201118084216189" style="zoom: 50%;" />

Next, we can find the explicit form of G(AB)\mathcal{G}(AB) in (u,v)(u,v) by using the Resolve command.

(* This will find the explicit form of SRG of AB *)
gAB = Resolve[quantgAB, Reals]

which produces the output:


Finally, we can plot G(AB)\mathcal{G}(AB) as follows.

Region[ImplicitRegion[gAB, {u, v}]]

The output is: