Polynomial and rational convergence ratesTrefethen

# Polynomial and rational convergence rates for Laplace problems on planar
domains ††thanks: Submitted to the editors DATE.

Lloyd N. Trefethen () School of Engineering and Applied Sciences, Harvard
University, Cambridge, MA 02138, USA<EMAIL_ADDRESS>
###### Abstract

Laplace problems on planar domains can be solved by means of least-squares
expansions associated with polynomial or rational approximations. Here it is
shown that, even in the context of an analytic domain with analytic boundary
data, the difference in convergence rates may be huge when the domain is
nonconvex. Our proofs combine the theory of the Schwarz function for analytic
continuation, potential theory for polynomial and rational approximation
rates, and the theory of crowding of conformal maps.

###### keywords:

Laplace problem, polynomial approximation, rational approximation, Schwarz
function, analytic continuation, inverted ellipse, potential theory, crowding

30E10, 35J05, 41A20, 65N80, 31A15, 65E05

##  1 Introduction

Suppose we wish to solve numerically the Laplace problem

(1) $\Delta u=0,~{}z\in\Omega,\qquad u=h,~{}z\in\Gamma$

in a simply-connected planar domain $\Omega$ bounded by an analytic Jordan
curve $\Gamma$, as suggested in Figure 1, where $h$ is a real analytic
function.111By an analytic Jordan curve we mean the one-to-one image of the
unit circle under an analytic function with nonvanishing derivative. See [28,
p. 2] or [39, p. 2]. (Everything can be generalized to less smooth geometries
or data, to other types of boundary conditions, and to domains with holes. In
Figure 1(b), $\Gamma$ is not analytic.) For convenience we think of $\Omega$
as complex, identifying $z=x+iy$. An old idea, going back to Walsh and Curtiss
nearly a century ago [7, 38], is to approximate $u$ as the real part of a
polynomial,

(2) $u(z)\approx\hbox{\rm Re\kern 1.0pt}p(z),$

so that the problem reduces to the approximation of $h$ by $\hbox{\rm Re\kern
1.0pt}p$ on $\Gamma$. This idea builds on the facts that $u$ must be the real
part of a function $f$ that is analytic in $\overline{\Omega}$ [1],

(3) $u(z)=\hbox{\rm Re\kern 1.0pt}\kern-0.5ptf(z),$

and that $f$ can be approximated on $\overline{\Omega}$ by a polynomial,

(4) $f(z)\approx p(z).$

In particular, Runge showed in 1885 that $f$ can be approximated arbitrarily
closely by polynomials in the supremum norm [26].

Figure 1:  Solutions of Laplace problems by polynomials and rational functions
of various degrees on three domains. On the smooth convex domain (a), both
methods converge rapidly. On the domain (b) with a corner singularity,
rational approximations are much more efficient than polynomials, an effect
going back to Newman in $1964$ [24]. On the smooth nonconvex domain (c) with
an inlet, rational approximations are again much more efficient, the new
observation of this paper. Red dots mark the poles of rational approximations
that achieve error about $10^{-8}$. These computations and comparisons are
made possible by approximation algorithms developed in the last five years [4,
6, 20].

In the old days, computing good approximations $p$ would have been problematic
even if today’s computers had been available, because of the difficulty of
finding well-distributed boundary points for interpolation and also the lack
of a well-conditioned basis in which to represent the polynomial. Today, the
first difficulty is bypassed by the use of least-squares fitting in a large
number of sample points on $\Gamma$, a proposal originating perhaps with Moler
in 1969 [19], and the second is taken care of by the use of the Vandermonde-
with-Arnoldi method of on-the-fly Stieltjes orthogonalization [4]. As a
result, numerical solution of planar Laplace problems by polynomial
approximation is entirely practical nowadays, so long as polynomials exist
that approximate $f$ efficiently. For many problems this is an excellent
numerical method, quick and accurate and delivering a result that is exactly
analytic and trivial to differentiate. Figure 1(a) is of this kind, and for
further illustrations, see [33] and [4, Figure 6.1].

However, sometimes good approximating polynomials do not exist. Figure 1(b)
shows a context in which this has been known since the work of Bernstein,
Jackson, and de la Vallée Poussin in the 1910s, where $u$ has a boundary
singularity. Here the boundary contains a corner, and this prevents rapid
convergence by any polynomial approximations.

The first purpose of this paper is to show that the same effect may arise even
when $\Gamma$ and $h$ are analytic, as illustrated in Figure 1(c). This is the
situation when $\Omega$ is nonconvex, containing an inlet. The figure shows
that polynomial approximations may converge at a negligible rate in such
cases, and we shall prove this mathematically. Although the convergence is
exponential, the convergence constant is exponentially close to $1$, rendering
polynomial approximations useless in practice (Theorem 4).

On the other hand, instead of approximating $u$ by a polynomial on $\Gamma$,
one may approximate it by a rational function with no poles in $\Omega$,

(5) $u(z)\approx\hbox{\rm Re\kern 1.0pt}r(z),$

which implicitly makes use of an approximation

(6) $f(z)\approx r(z).$

Walsh considered this idea too [38], though it was even further out of
practical range in those days, with no robust algorithms available for
computing rational approximations, even if suitable computers had been at
hand. Much more recently Hochman, Leviatan, and White developed a method of
this kind in 2013 [16], and the AAA-least squares method, which appeared a few
years later, has made these computations quick and easy [6], so that rational
approximations are now a very practical method for solving Laplace problems.

The second purpose of this paper is to prove that the speedups possible with
rational functions are transformative, not just in cases like Figure 1(b),
where the power of rational approximations has been known for a long time, but
also in cases like Figure 1(c), whose analysis is new.

Although this paper includes numerical illustrations to make the points clear,
its main purpose is theoretical. The power of rational approximations for
solving Laplace and related problems has been illustrated abundantly by
numerical experiments in other works [2, 5, 6, 9, 10, 16, 40]. The same power
applies to Helmholtz problems too [10], although here there is less literature
and no theory.

One instance of a nonconvex domain is particularly tidy, the case of an
inverted ellipse, where everything can be worked out explicitly. For the
inverted ellipse of parameter $\rho>1$, we show that the degree of a
polynomial approximation must be increased asymptotically by
$(\log(10)/1.16)\exp((\pi^{2}/4)/(\kern 0.7pt\rho-1))\approx
2.0\cdot(11.8)^{1/(\kern 0.7pt\rho-1)}$ for each additional digit of
approximation accuracy (Theorem 5). With $\rho=1.3$, for example, hardly an
extreme case, each digit of accuracy requires an increase of the polynomial
degree by about $7000$ (Table 1). With rational approximations, on the other
hand, each new digit of accuracy requires an increase in the rational degree
by just $\sim{1\over 2}\log(10)/(\kern 0.7pt\rho-1)\approx 1.2/(\kern
0.7pt\rho-1)$, so for $\rho=1.3$, about $4$ rather than $7000$ (Theorem 9).
See Figure 7.

There are a number of theoretical details in the upcoming pages, but the
essential argument can be summarized compactly, as follows. Convergence rates
of polynomial and rational approximations to Laplace solutions depend on
analytic continuation outside $\Gamma$. This analytic continuation is
described by the theory of the Schwarz function, which asserts that there will
usually be branch point singularities not far from $\Gamma$ (Theorems 1 and
2). This is true for both convex and nonconvex domains, as one can see by
comparing the pole locations in Figures 1(a) and 1(c), which in both cases are
near the boundary but not extremely near. The significance of nonconvexity
arises at the next step of the argument, where we track the consequences of
these singularities. For polynomial approximation, convergence is determined
by a conformal map of the exterior of $\Gamma$ to the exterior of the unit
disk (Theorems 3–4 and Figures 3–4), and in the case of an inlet, the
singularity will map to a point exponentially close to the disk, resulting in
a convergence factor exponentially close to $1$ (section 7). For rational
approximation, on the other hand, poles can line up near branch cuts of the
analytic continuation, leading to a much faster exponential convergence rate
associated with a more forgiving doubly connected conformal mapping problem
onto an annulus (Theorems 6–8 and Figures 5–6). In a word, the freedom of a
rational function to place poles near $\Gamma$ rather than just at $\infty$
eliminates the “crowding” phenomenon that causes exponential slow-down for
polynomial approximations around inlets.

It is hard to find works in the literature that are close to the present
paper, particularly in combining ideas of analytic continuation of Laplace
solutions with polynomial and rational approximation theory. Two important
related papers are by Millar [18], who applies the Schwarz function to track
singularities of analytic continuations of Helmholtz solutions across
boundaries, and Barnett and Betcke [3], who apply the method of fundamental
solutions to Helmholtz problems, also with the aid of the Schwarz function,
and show that good positioning of the singularities outside the domain is
crucial to obtaining well-conditioned bases. In these and other works related
to analytic continuation of solutions of elliptic PDE, it is common to
formulate the problem in terms of two independent complex variables, following
Vekua in the 1950s [14, 36]. However, so far as I know, this is not needed in
the special case of the Laplace equation.

I must end this introduction with a historical and personal remark. Most of
the theory of this paper has connections with Joseph Walsh, the great mid-20th
century expert on polynomial and rational approximation, who was a mathematics
faculty member at Harvard during 1921–1966 until he retired and took a
position at the University of Maryland. None of the algorithms that make these
computations practicable were available in his day, however, not to mention
computers of the necessary capabilities. Today, we can apply this Walsh-style
theory in an entirely new environment. Meanwhile my own career has brought me
to retirement after 26 years at Oxford, whereupon, in a strange symmetry, I
have taken a position at Harvard. This is the first paper I have written at my
new institution. I never met Walsh, but I had indirect connections to him
through his students Ted Rivlin, Dick Varga, and Ed Saff, and with affection I
think of the present paper as a continuation of Walsh’s research interests
into a computational era he could not have imagined.

##  2 Analytic continuation and the Schwarz function

The starting point of our analysis is analytic continuation across the
boundary curve $\Gamma$. Let $h$ be the boundary data function of
$(\ref{problem})$, which we have assumed is real analytic. This implies that
$h$ can be analytically continued to a complex analytic function in a
neighborhood of $\Gamma$. Similarly, let $f$ be the complex analytic function
of (3) whose real part is the solution $u$ of the Laplace problem (1). (The
imaginary part of $f$ is determined up to a constant, which plays no role in
the discussion.) Like $h$, $f$ must extend to an analytic function in a
neighborhood of $\Gamma$. Along with $f$ and $h$, a third analytic function
whose analytic continuation across $\Gamma$ we shall work with is the
difference,

(7) $d(z)=f(z)-h(z).$

The important property of $d$ is that it is pure imaginary on $\Gamma$,
because $f$ and $h$ have equal real parts there. Thus $h$ and $d$ are analytic
functions in a neighborhood of $\Gamma$ that map $\Gamma$ to subsets of the
real and imaginary axes, respectively. If $\Gamma$ were a straight line
segment or an arc of a circle, we could now describe the relationship of $h$
and $d$ inside and outside $\Gamma$ by the Schwarz reflection principle. In
our more general case where $\Gamma$ is an analytic arc, the generalization
that comes into play is based on what is known as the Schwarz function [8,
28].

The Schwarz function of $\Gamma$ is defined as the unique function $S(z)$ that
is analytic in a neighborhood of $\kern 0.5pt\Gamma$ and takes the values
$S(z)=\overline{z}$ for $z\in\Gamma$. Note that $S(z)$ is determined by
$\Gamma$, not $f$ or $h$ or $d$. The significance of $S$ is that its complex
conjugate, $\overline{S}\kern 0.7pt(z)$, maps points close to $\Gamma$ on one
side to their analytic reflections on the other side. Specifically, it is
known that in a sufficiently small neighborhood $U$ of $\Gamma$, $S$ is
analytic and satisfies the reflection property $\overline{S}\kern
0.7pt(\overline{S}\kern 0.7pt(z))=z$. Here is how $S$ enables analytic
continuation: if $h$ or $d$ is analytic in the part of $U$ interior or
exterior to $\Gamma$, then it extends analytically to the other side by the
reflection formula

(8) $h(\kern 0.7pt\overline{S}\kern 0.7pt(z))=\overline{h(z)},\quad z\in U$

or

(9) $d(\kern 0.7pt\overline{S}\kern 0.7pt(z))=-\overline{d(z)},\quad z\in U,$

respectively. In words, the values of $h$ and $d$ at $\overline{S}\kern
0.7pt(z)$ are the reflections in the real and imaginary axes, respectively, of
their values at $z$. For details of these developments see [8, chap. 6] or
[28, Prop. 1.2].

Figure 2: An analytic Jordan curve $\Gamma$ and the poles of a rational
approximation on $\Gamma$ to its Schwarz function $S$. The clustered strings
of poles indicate that $S$ has five branch points of $S$ near $\Gamma$ in the
interior and another five in the exterior. The red and green dots mark four
arbitrarily chosen points on one side of $\Gamma$ and their reflections on the
other side. Analytic continuation of a function $d$ analytic and imaginary on
$\Gamma$ is carried out by applying the reflection condition $(\ref{contin})$
at such points.

For an idea of the shape of the Schwarz function, consider Figure 2. This
shows an analytic Jordan curve $\Gamma$ for which a degree 107 AAA rational
approximation $r$ to $S$ has been computed. (This took 2/3 s on our laptop
based on the Chebfun command `[r,poles] = aaa(conj(Z),Z)`, where Z is a vector
of 2000 sample points along the boundary.) For $z\in\Gamma$, $r$ matches
$S(z)=\overline{z}$ to accuracy $10^{-13}$. The black dots are the poles of
$r$, and they give an indication of the behavior of $S$ for $z\not\in\Gamma$.
Roughly speaking, with rational approximations we expect poles to line up
along the branch cuts of the function being approximated. More precisely, like
all analytic functions, $S$ does not intrinsically have branch cuts; these are
only introduced by humans when we wish to make the function single-valued, or
by rational approximations (in the approximate fashion illustrated in the
figure) as a by-product of their near-optimality. On the other hand $S$ has
branch points, and these are approximated by the cluster points of the poles
of $r$. In this case it appears that there are five branch points of $S$ near
$\Gamma$ on the inside and five more on the outside.

Going out from $\Gamma$ beyond and around the branch points, it would make
sense to speak of a multi-valued analytic Schwarz function, and this approach
is taken in some of the theoretical literature [28] and will also turn up in
our Theorem 8, below. However, multi-valued functions are mostly not relevant
to the present work, because polynomial and rational approximations are
single-valued. Therefore, throughout this paper, our attention is restricted
to neighborhoods $U$ that are narrow enough or otherwise confined in such a
way that $S$ is analytic and single-valued.

Let $U$ be a neighborhood of $\Gamma$ of this kind, with $S$ defined in $U$
satisfying $\overline{S}\kern 0.7pt(U)=U$ and $\overline{S}\kern
0.7pt(\overline{S}\kern 0.7pt(z))=z$, so that $U$ is reflected into itself by
$\overline{S}\kern 0.7pt$. We can now establish a foundational theorem for
this paper (compare [18, sec. 4]).

Theorem 1. Analytic continuation of $f$ across $\Gamma$. Let $\Omega$,
$\Gamma$, $f$, $h$, and $d=f-h$ be defined as discussed above, and let $U$ be
a neighborhood of $\Gamma$ in which the Schwarz function $S$ of $\Gamma$ is
analytic and satisfies $\overline{S}\kern 0.7pt(U)=U$ and $\overline{S}\kern
0.7pt(\overline{S}\kern 0.7pt(z))=z$. If $h$ is analytic in the part of $U$
outside $\Gamma$, then the same is true of $f$.

Proof. Let $U_{\hbox{\scriptsize\rm in}}$ and $U_{\hbox{\scriptsize\rm out}}$
be the portions of $U$ interior and exterior to $\Gamma$, respectively. If $h$
is analytic in $U_{\hbox{\scriptsize\rm out}}$, then by (8) it is analytic in
$U_{\hbox{\scriptsize\rm in}}$. By (7) it follows that $d$ is analytic in
$U_{\hbox{\scriptsize\rm in}}$, since $f$ is analytic throughout $\Omega$. By
(9), it follows that $d$ is analytic in $U_{\hbox{\scriptsize\rm out}}$. By
(7) again, it follows that $f$ is analytic in $U_{\hbox{\scriptsize\rm out}}$.

To prove that polynomial approximation stagnates as illustrated in Figure 1,
we will need a converse of this theorem. We would like to show that when the
Schwarz function $S$ has singularities outside $\Omega$, they will usually
block the analytic continuation of the function $f$ associated with the
Laplace problem (1). More precisely, I suspect it is true that if $S$ cannot
be analytically continued to a point $z_{c}$ outside of $\Omega$, then the
same will apply to $f$ if $h$ is a nonconstant function analytic outside
$\Omega$. (The situation is different if $h$ is a constant, since then $f$
will be a constant too and thus analytically continuable to all of
${\mathbb{C}}$, regardless of the shape of $\Gamma$.)

It is worth mentioning that there are plenty of functions $h$ that are real on
$\Gamma$ and analytic in ${\mathbb{C}}\backslash\Omega$. If $\Gamma$ is the
unit circle, then $x$ and $y$ are both functions in this class, since they can
be written $x=(z+z^{-1})/2$ and $y=(z-z^{-1})/2\kern 0.4pti$. The same
therefore applies on the unit circle to real polynomials in $x$ and $y$, and
more generally, to functions defined by Laurent series convergent for
$0<|z|<\infty$ whose coefficients have the symmetry $a_{-k}=\overline{a_{k}}$.
For a general Jordan curve $\Gamma$, we may obtain an equivalent class of
functions $h(z)$ as transplants of these Laurent series under a conformal map
$\Phi$ of the exterior of $\Gamma$ to the exterior of the unit disk. (We will
make use of $\Phi$ in the next section in the context of polynomial
approximation.) Note that it follows from here that, given any continuous real
function $h_{0}$ on $\Gamma$ and any $\varepsilon>0$, we can find a function
$h$ that is real on $\Gamma$ and analytic in ${\mathbb{C}}\backslash\Omega$
with $|h-h_{0}|<\varepsilon$ on $\Gamma$.

I don’t know how to establish the singularity of $f$ in the generality
conjectured above. Instead, following [18, sec. 4], here is a statement
restricted to the familiar situation in which $S$ has a branch point as in
Figure 2 and in our later example of the inverted ellipse.

Theorem 2. Limit to analytic continuation of $f$ across $\Gamma$. Let
$\Omega$, $\Gamma$, $f$, $h$, and $d$ be defined as discussed above, and let
$z_{c}\in{\mathbb{C}}\backslash\overline{\Omega}$ be such that $S$ can be
analytically continued up to $z_{c}$ but has a branch point there. Then for
some choices of $h$ analytic in ${\mathbb{C}}\backslash\Omega$, $f$ cannot be
analytically continued to a neighborhood of $z_{c}$.

Proof. If $f$ can be analytically continued to a neighborhood of $z_{c}$, then
by (7) and the analyticity of $h$, the same is true of $d$. Let $U$ be a
neighborhood of $\Omega$ as in Theorem 1 that takes the form of an open set
containing $z_{c}$ from which has been removed a branch cut $C$ extending from
$z_{c}$ to the boundary. Then $\overline{S}\kern 0.7pt$ reflects $h$ and $d$
by (8) and (9) from the portion of $U$ outside $\Gamma$ to the portion inside.
Since $z_{c}$ is a branch point, $\overline{S}\kern 0.7pt$ must take distinct
values on the two sides of $C$. Let $b\in C$ be such a point, mapping under
$\overline{S}\kern 0.7pt$ to two distinct points $a_{1},a_{2}\in\Omega$. Since
$d$ and $h$ are analytic at $b$, and both can be reflected by
$\overline{S}\kern 0.7pt$ in $U$, we have $d(a_{2})=d(a_{1})$ and
$h(a_{2})=h(a_{1})$, which implies $f(a_{2})=f(a_{1})$ and
$u(a_{2})=u(a_{1})$. It follows from the $|h-h_{0}|$ observation above,
however, that this is not possible for all choices of $h$. We need only pick a
boundary function $h_{0}$ for which $u(a_{1})\neq u(a_{2})$, and then find an
$h$ that is sufficiently close to $h_{0}$.

##  3 Polynomial approximation

Let $E_{n}$ be the minimax error of degree $n$ polynomial approximation to $f$
on $\Omega$,

(10) $E_{n}=\inf_{p\in P_{n}}\|f-p\kern 0.7pt\|,$

where $\|\cdot\|$ is the supremum norm on $\overline{\Omega}$ and $P_{n}$
denotes the space of polynomials of degree $n$. We now consider what Theorem 2
implies about the convergence rate of $E_{n}$ to $0$ as $n\to\infty$.

Assume for simplicity that $f$ cannot be analytically continued to all of
${\mathbb{C}}$. According to standard theory going back to Walsh [37, 39] and
presented beautifully by Levin and Saff [17], the convergence rate is then
exponential, at a rate essentially $R^{-n}$ for some $R>1$. The constant $R$,
which we shall call the analyticity radius of $f$ on $\Omega$, has an
interpretation in terms of a conformal map $\Phi$ of the exterior of $\Omega$
to the exterior of the unit disk in the $w$-plane with $\Phi(\infty)=\infty$.
For any $r\geq 1$, as illustrated in Figure 3, let $\Gamma_{r}$ be the
preimage of $|w|=r$ under $\Phi$. Then $R$ is the largest $r$ for which $f$ is
analytic in the region enclosed by $\Gamma_{r}$.222If $z_{c}$ is a point on
$\Gamma_{R}$ at which $f$ is not analytic, then we can also write
$R=\exp(\kern 0.7ptg(z_{c}))$, where $g$ is the Green’s function of
$\overline{\Omega}$, that is, the harmonic function defined in
${\mathbb{C}}\backslash\overline{\Omega}$ with $g(z)=0$ on $\Gamma$ and with
$g(z)\sim\log|z|$ as $z\to\infty$ [17, Thm 3]. The relationship between $g$
and $\Phi$ is $g(z)=\log|\Phi(z)|$.

Here is Walsh’s result.

Figure 3: Illustration of the theory of polynomial approximation of an
analytic function $f$ on a domain $\Omega$ bounded by an analytic Jordan curve
$\Gamma$. The grey curves are level lines $\\{\Gamma_{r}\\}$ of the Green’s
function of $\Gamma$, $r=1.1,1.2,\dots,1.5$, which can be interpreted as
preimages of circles outside the unit disk in a conformal map $\Phi$ of the
exterior of $\Gamma$ to the exterior of the unit disk. The analyticity radius
$R$ of $f$ is the largest $r>1$ for which $f$ is analytic in the region
interior to $\Gamma_{r}$. The red dot on the left marks a point on
$\Gamma_{R}$ to which $f$ cannot be analytically continued, and the absolute
value of its image on the right is the number $R$. The convergence rate of
best polynomial approximations is given by $(\ref{rate})$.

Theorem 3. Polynomial approximation of an analytic function. Let the domain
$\Omega$, the function $f$ analytic in $\Omega$, the polynomial minimax error
$E_{n}$, and the analyticity radius $R$ of $f$ be defined as above. The
minimax approximation errors satisfy

(11) $\limsup_{n\to\infty}E_{n}^{1/n}={1\over R}.$

We can paraphrase Theorem 3 like this:

The rate of polynomial approximation of $f$ on $\Omega$
is determined by its closest singularity outside $\Omega$.

“Closest” means in the sense of the level curves $\Gamma_{r}$, and the rate in
question is that of (11). This is the “Walsh half” of the analysis of our
Laplace problem. The “Schwarz half” was presented in Theorem 2 of the last
section:

This closest singularity is normally the closest point $z_{c}$ of
nonanalyticity
of the Schwarz function $S$ (unless $h$ has a singularity even closer).

Combining Theorems 2 and 3 gives us our basic result on slow convergence of
polynomial approximations of solutions of Laplace problems. As with Theorem 2,
though this statement only mentions “some” choices of $h$, in practice it will
be almost all of them. The theorem references the analyticity radius $R$ of
$S$, a notion defined above for a function analytic throughout $\Omega$. For a
function like $S$ analytic just in a neighborhood of $\Gamma$, $R$ is the
largest $r>1$ for which $S$ is analytic in the region bounded between $\Gamma$
and $\Gamma_{r}$.

Theorem 4. Polynomial approximation of a Laplace solution. Let the Laplace
problem $(\ref{problem})$ with boundary data $h$ have solution $u(z)=\hbox{\rm
Re\kern 1.0pt}\kern-0.5ptf(z)$ as in $(\ref{Ref})$, let $R>1$ be the
analyticity radius of the Schwarz function $S$ on $\Omega$, and let $E_{n}$ be
the minimax error $(\ref{Endef})$ in degree $n$ polynomial approximation. Then
for some choices of $h$ analytic throughout
${\mathbb{C}}\backslash\overline{\Omega}$, and assuming $S$ has a branch point
on the curve $\Gamma_{R}$, these errors satisfy

(12) $\limsup_{n\to\infty}E_{n}^{1/n}={1\over R}.$

##  4 Polynomials on the inverted ellipse

Theorem 4 has an elegant application to the special case in which $\Omega$ is
the region bounded by an inverted $\rho$-ellipse, as sketched in Figure 4. For
any $\rho>1$, we define the $\rho$-ellipse $E_{\rho}$ to be the image in the
$\zeta$-plane of the circle $|w|=\rho$ in the $w$-plane under the Joukowsky
map $J(w)=(w+w^{-1})/2$. Geometrically, $E_{\rho}$ is the ellipse with foci
$\pm 1$ whose semiminor and semimajor axis lengths sum to $\rho$. The inverted
$\rho$-ellipse is the reciprocal $I_{\rho}=1/E_{\rho}$, and our variables are
related by $\zeta=z^{-1}$.

The Schwarz function for the inverted ellipse is known analytically. For
example on p. 25 of [8] we find for the ellipse $E_{\rho}$

(13) $S(z)=\textstyle{1\over 2}(\kern 1.0pt\rho^{2}+\rho^{-2})\kern
0.5ptz-\textstyle{1\over 2}(\kern 1.0pt\rho^{2}-\rho^{-2})\sqrt{z^{2}-1},$

which implies that for $I_{\rho}$ we have

(14) $S(z)=\Bigl{(}\textstyle{1\over 2}(\kern 1.0pt\rho^{2}+\rho^{-2})\kern
0.5ptz^{-1}-\textstyle{1\over 2}(\kern
1.0pt\rho^{2}-\rho^{-2})\sqrt{z^{-2}-1}\kern 2.0pt\Bigr{)}^{-1}.$

For our purposes what matters is that the only singularities of $S$ are a pair
of branch points outside $\Gamma$ at $z=\pm 1$ and a pair of simple poles
inside $\Gamma$ at $\pm\kern 0.4pti\kern 0.4pt(\kern
1.0pt\rho^{2}-\rho^{-2}\kern 0.7pt)/2$. If branch cuts are drawn along
$[1,\infty)$ and $(-\infty,-1]$, then $S$ becomes meromorphic in the remaining
slit domain ${\mathbb{C}}\backslash\\{[1,\infty)\cup(-\infty,-1]\\}$, analytic
in the portion outside $\Omega$.

Figure 4: The inverted ellipse $I_{\rho}$ with parameter $\rho=1.5$, with
level curves $\Gamma_{r}$ plotted for $r=1.02,1.04,\dots,1.10.$ The dot at
$z=1$ corresponds to the analyticity radius $r=R\approx 1.009$ at which the
Schwarz function for $\Omega$ has a branch point. This value implies that
although the boundary of the region is analytic, it will still take an
increase of the polynomial degree by about $250$ asymptotically for each
additional digit of accuracy. On the right, a close-up.

To determine the analyticity radius for $I_{\rho}$, we accordingly need to
know the image of $z=1$ under a conformal map of the exterior of $I_{\rho}$ to
the exterior of the unit disk. The conformal map of the interior of $I_{\rho}$
to the unit disk is elementary: it reduces to the map of the exterior of
$E_{\rho}$, which is essentially the Joukowsky map. The conformal map of the
exterior of $I_{\rho}$, on the other hand, reduces to the map of the interior
of $E_{\rho}$, which is not elementary. The required formula involving a
Jacobian elliptic function was derived by Schwarz in 1869 and is presented in
a number of sources including [23], [31], and Figure 3.2 of [13]. According to
equation (21) of [31], the focus $\zeta=1$ of the ellipse maps to the point

(15)
$\varphi^{-1}(1)={\rho^{-1^{2}}+\rho^{-3^{2}}+\rho^{-5^{2}}+\cdots\over{1\over
2}+\rho^{-2^{2}}+\rho^{-4^{2}}+\rho^{-6^{2}}+\cdots}.$

The analyticity radius we need follows by taking the reciprocal.

Theorem 5. Polynomial approximation on the inverted ellipse. If $\Omega$ is
the domain bounded by the inverted $\rho$-ellipse $I_{\rho}$ for some
$\rho>1$, the associated analyticity radius $R$ of Theorem $4$ is

(16) $R={{1\over
2}+\rho^{-2^{2}}+\rho^{-4^{2}}+\rho^{-6^{2}}+\cdots\over\rho^{-1^{2}}+\rho^{-3^{2}}+\rho^{-5^{2}}+\cdots}.$

Asymptotically as $\rho\to 1$, $R$ satisfies

(17) $R-1\sim 4\kern 0.4pte^{-\pi^{2}/(4\log\rho)}\sim A\kern
0.4pte^{-\pi^{2}/(4(\kern 0.7pt\rho-1))}$

with $A=4\kern 0.7pt\exp(-\pi^{2}/8)\approx 1.16485$.

Proof. The derivation of (16) was given in the discussion above, and I am
grateful to Jon Chapman of Oxford and Alex Barnett of the Flatiron Institute
for proofs of (17). The following particularly elegant argument comes from
Barnett. If we double both the numerator and the denominator of (16) by
extending the sums to $-\infty$, the quotient is unchanged in value and takes
the simple form

$R=\sum_{k=-\infty}^{\infty}\rho^{-4k^{2}}\kern-4.0pt\left/\kern-3.0pt\sum_{k=-\infty}^{\infty}\rho^{-4(k+{1\over
2})^{2}}\right.,$

or equivalently, on setting $a=4\log\rho$,

(18) $R={A\over
B}=\sum_{k=-\infty}^{\infty}\exp(-ak^{2})\kern-2.0pt\left/\kern-3.0pt\sum_{k=-\infty}^{\infty}\exp(-a(k+\textstyle{1\over
2})^{2})\right..$

This is the ratio of two infinite trapezoidal quadrature approximations to the
Gaussian, which explains why it converges exponentially to 1 as $a\to 0$. By
the Poisson summation formula applied to the Fourier transform pair
$f(x)=\exp(-ax^{2})$ and $\hat{f}(k)=c\exp(-\pi^{2}k^{2}/a)$, where $c$ is a
constant whose value does not matter, we have for a new constant $c^{\prime}$

$A=c^{\prime}\left(1+2\kern 0.5pte^{-\pi^{2}/a}+2\kern
0.5pte^{-(2\pi)^{2}/a}+\cdots\right),$

and, since the translation by $1/2$ leads to alternating signs in the Poisson
summation formula,

$B=c^{\prime}\left(1-2\kern 0.5pte^{-\pi^{2}/a}+2\kern
0.5pte^{-(2\pi)^{2}/a}-\cdots\right).$

These formulas imply $A/B-1\sim 4e^{-\pi^{2}/a}$ as $a\to 0$.

The exponential dependence of $R$ on $\log\rho$ or $\rho-1$ in Theorem 5 is
striking. Table 1 lists $R$ for various values of $\rho$ decreasing toward
$1$. The final column shows $\log(10)/\log(R)$, the increase of degree
required asymptotically for each improvement of accuracy by one digit.

Table 1: Analyticity radii and corresponding convergence rates for polynomial approximations to solutions of Laplace problems on the inverted ellipse $I_{\rho}$ for various $\rho$. All numbers are rounded to $2$ significant figures. $\rho$ | $~{}~{}~{}R$ | degree increase per digit
---|---|---
$2$ | $1.12$ | $20$
$1.9$ | $1.089$ | $27$
$1.8$ | $1.062$ | $38$
$1.7$ | $1.038$ | $60$
$1.6$ | $1.021$ | $110$
$1.5$ | $1.0091$ | $250$
$1.4$ | $1.0026$ | $880$
$1.3$ | $1.00033$ | $7000$
$1.2$ | $1.0000053$ | $430{,}000$
$1.1$ | $1.000000000023$ | $100{,}000{,}000{,}000$

##  5 Rational approximation

Polynomials are rational functions all of whose poles are constrained to lie
at $z=\infty$. When rational functions without this constraint are allowed,
the approximation power increases enormously for the kinds of domains we are
interested in. This happens because poles can now line up along branch cuts of
$f$, or, equivalently in most cases, along branch cuts of the Schwarz function
$S$. We saw this effect in Figure 1. The phenomenon of poles approximating
branch cuts is well known in rational approximation theory, associated in
particular with theorems of Stahl for Padé approximation [30], and is
illustrated, for example, in the papers [2, 5, 6, 9, 10, 16, 20, 35, 40].

An explanation of this behavior and of the approximation power of rational
functions comes again from Walsh [39]. In Walsh’s theory, key roles are played
by the $n$ poles $\\{\pi_{k}\\}$ of a rational function $r$ of degree $n$,
which can be thought of as point charges for a two-dimensional potential
$\log|z-\pi_{k}|$, and any $n$ interpolation points $\\{z_{k}\\}$ where
$f(z_{k})=r(z_{k})$, which can be thought of as point charges of opposite sign
associated with potentials $-\log|z-z_{k}|$. By considering these potentials
in the context of the Hermite integral formula representing $f(z)-r(z)$ at
other points $z\in{\mathbb{C}}$, one can derive error bounds associated with
potential theory. A few decades after Walsh, Gonchar and others took the
theory further, showing how in the limit $n\to\infty$, minimax approximation
rates are governed by the equilibrium potentials for a continuum distribution.

We will not go into the details of this theory, which are summarized in [17,
pp. 91–93] and more fully in sections 6–8 of [35]. We will, however, state its
main conclusion, which is illustrated in Figure 5. Let $f$ be analytic on
$\Omega$ and extend analytically (i.e., as a single-valued analytic function)
to some larger domain $\Omega^{\prime}\subseteq{\mathbb{C}}$ enclosing
$\overline{\Omega}$ in its interior. For simplicity we suppose that
$\Omega^{\prime}$ is also a Jordan domain, with boundary $\Gamma^{\prime}$.
Then $\Gamma$ and $\Gamma^{\prime}$ are the inner and outer boundaries of an
annular region $K$, called a condenser. Such a region can be conformally
mapped onto a circular annular region in ${\mathbb{C}}$ whose inner boundary
is the unit circle and whose outer boundary is the circle about the origin of
some radius $R^{*}>1$, the modulus of the condenser. The number $R^{*}$ is
uniquely determined, and the conformal map itself is also uniquely determined
up to a rotation. As in (10), but now for rational approximations, we define

(19) $E_{nn}=\inf_{r\in R_{n}}\|f-r_{n}\|,$

where $\|\cdot\|$ is the supremum norm on $\overline{\Omega}$ and $R_{n}$
denotes the space of rational functions of degree $n$ (i.e., with at most $n$
poles counted with multiplicity, including any poles at $\infty$). Here is
Walsh’s result:

Figure 5: A rational companion to Figure 3, illustrating the theory of
rational approximation of an analytic function $f$ on a domain $\Omega$
bounded by an analytic Jordan curve $\Gamma$. We suppose $f$ has a singularity
outside $\Gamma$, marked by the red dot, but that $f$ can be analytically
continued to a condenser region $K$ bounded between $\Gamma$ and a larger
Jordan curve $\Gamma^{\prime}$ that avoids this singularity. If $\Phi$ is a
conformal map of the condenser onto a circular annulus $1<|w|<R^{*}$, then
rational approximations to $f$ can converge at the exponential rates (20) or
(22) determined by $R^{*}$. They achieve this by placing poles approximately
along branch cuts, as suggested by the dashed line. Compare Figure 1(c). The
conformal map for this image was computed by the AAA-least squares method.

Theorem 6. Rational approximation of an analytic function. Let the domain
$\Omega$, the function $f$, the rational minimax error $E_{nn}$, the condenser
$K$, and the condenser modulus $R^{*}$ be defined as above. The minimax errors
satisfy

(20) $\limsup_{n\to\infty}E_{nn}^{1/n}\leq{1\over R^{*}}.$

Recall that Theorem 3 for polynomials involved a number $R$ that was fully
determined by $f$ and $\Omega$, defined as the largest $r>1$ for which $f$
could be extended analytically to within the Green function contour
$\Gamma_{r}$. Here with rational functions, by contrast, the number $R^{*}$ as
we have defined it depends on the choice of the condenser $K$ to which $f$ is
analytically continued. In cases where $f$ has branch points, a single-valued
continuation will need to be restricted to a domain that avoids these, and
some choices will lead to larger values of $R^{*}$ than others. An optimal
choice can be made, leading to a maximal value of $R^{*}$, but we will not go
into that here, simply accepting that Theorem 6 holds for any choice of $K$
and its associated $R^{*}$. As a consequence the next two theorems involve
inequalities, not equalities.

The crucial point is that $R^{*}$ can be much bigger than $R$, allowing
rational approximations to converge much faster than polynomials. In
particular we will see in sections 6 and 7 that this happens with domains
$\Omega$ involving inlets, where $R$ is exponentially close to $1$ whereas
$R^{*}$ may be only algebraically close.

Theorem 7. Rational approximation of a Laplace solution. Let the Laplace
problem $(\ref{problem})$ with boundary data $h$ have solution $u(z)=\hbox{\rm
Re\kern 1.0pt}\kern-0.5ptf(z)$ as in $(\ref{Ref})$. Let the Schwarz function
$S$ of $\Gamma$ be analytically continuable to a condenser $K$ about $\Omega$,
as defined above, with modulus $R^{*}$. Assume that $\overline{S}\kern 0.7pt$
reflects $K$ into a subset of $\Omega$ such that
$U=K\cup\Gamma\cup\overline{S}\kern 0.7pt(K)$, as in Theorem $1$, is a
neighborhood of $\Gamma$ in which $S$ is analytic and satisfies
$\overline{S}\kern 0.7pt(U)=U$ and $\overline{S}\kern 0.7pt(\overline{S}\kern
0.7pt(z))=z$. If $h$ is analytic in $K$, then the rational minimax errors
$E_{nn}$ of $(\ref{Endefr})$ satisfy

(21) $\limsup_{n\to\infty}E_{nn}^{1/n}\leq{1\over R^{*}}.$

Proof. By Theorem 1, $f$ is analytic in $K$, and (21) follows from Theorem 6.

The $1/R^{*}$ convergence factor of Theorems 6 and 7 is pessimistic in many
cases: the actual convergence factor is often $1/(R^{*})^{2}$. Equivalently,
we may say that $1/R^{*}$ is often an upper bound not just for
$\limsup_{n\to\infty}E_{nn}^{1/n}$ but also for
$\limsup_{n\to\infty}E_{nn}^{1/2n}$. Intuitively speaking, this factor of 2 is
associated with the fact that rational functions have twice as many parameters
as polynomials, a property not exploited in the theory leading to Theorems 6
and 7. These issues are summarized in section 7.5 of [35], whose substance is
derived from the important paper [25] by Rakhmanov. According to what
Rakhmanov calls the Gonchar–Stahl $\rho^{2}$-theorem, the factor of 2 speedup
always applies in the case of a function that can be analytically continued to
a multivalued analytic function along all curves in ${\mathbb{C}}$ that avoid
a certain fixed set $\Sigma\subseteq{\mathbb{C}}$ of capacity zero. In
particular, it applies when $f$ is analytic apart from branch points. We
summarize the improvement to Theorems 6 and 7 as follows.

Theorem 8. Factor of 2 speedup for functions with algebraic branch points. The
convergence rates of Theorems $6$ and $7$ can be doubled to

(22) $\limsup_{n\to\infty}E_{nn}^{1/n}\leq{1\over(R^{*})^{2}}.$

if $f$ can be analytically continued to a multivalued analytic function along
all curves in ${\mathbb{C}}$ that avoid a fixed set
$\Sigma\subseteq{\mathbb{C}}$ of capacity zero.

Proof. The estimate (22), which is the upper-bound half of the Gonchar–Stahl
theorem, originates in [29].

##  6 Rational functions on the inverted ellipse

We now apply Theorems 7–8 to the inverted ellipse $I_{\rho}$. This proves
surprisingly easy. We saw in section 4 that the conformal map of the exterior
of $I_{\rho}$ to the exterior of the unit disk is not elementary. For rational
approximation, however, since the Schwarz function is analytic in the slit
domain
${\mathbb{C}}\backslash\\{\overline{\Omega}\cup[1,\infty)\cup(-\infty,-1]\\}$,
the conformal map we need is of the exterior of $\overline{\Omega}$ in this
slit domain onto a circular annulus. Taking reciprocals, what is at issue is
the conformal map onto a circular annulus of the doubly-connected domain
bounded by the $\rho$-ellipse $E_{\rho}$ and slit along $[-1,1]$. This is
essentially just the Joukowsky map, as summarized in Figure 6.

Figure 6:  A summary in images of polynomial and rational convergence rates
for the inverted ellipse $I_{\rho}$ as discussed in sections $4$ and $6$. On
the left, the domain $\Omega$ bounded by $I_{\rho}$ with $\rho=1.5$. On the
right, the conformal maps of two domains bounded by the corresponding ellipse
$E_{\rho}$, first without and then with a slit along the midline $[-1,1]$.
According to the arguments leading to Theorems $5$ and $9$ and summarized in
Figures 3 and 5, these maps determine the exponential convergence rates for
polynomial and rational approximation methods, respectively, for solving
Laplace problems on $\Omega$. The polynomial rate is very slow because the
image of $z=1$ in the upper map is exponentially close to $1$ (about $0.9909$
for this choice of $\rho$, marked by a white dot). The rational rate is much
faster because the outer boundary of the annulus in the lower map is only
algebraically close to the inner one (distance $0.5$).

The gives us the following theorem.

Theorem 9. Rational approximation on the inverted ellipse. If $\Omega$ is the
domain bounded by the inverted $\rho$-ellipse $I_{\rho}$ for some $\rho>1$,
then if $h$ can be analytically continued to all of
${\mathbb{C}}\backslash\Omega$, the associated modulus $R^{*}$ of Theorem $8$
can be taken to be any value $R^{*}<\rho$. It follows that for such $h$,
minimax rational approximation errors for solutions of the Laplace problem
satisfy

(23) $\limsup_{n\to\infty}E_{nn}^{1/n}\leq{1\over\rho^{2}}.$

Figure 7:  Numerical confirmation of Theorems $5$ and $9$ for solving a
Laplace problem by polynomial and rational approximation on the domain bounded
by the inverted $\rho$-ellipse $I_{\rho}$ (Vandermonde with Arnoldi least
squares [4] and AAA-least squares [6], respectively). With $\rho=1.8$, the
indentation is so mild that exponential convergence is observed for both
methods, though at a lower rate for polynomials than rational functions. With
$\rho=1.3$ the exponential convergence rate for polynomial approximation is
essentially zero and we see subexponential convergence, as if $\Omega$ had a
corner. The rational method still converges rapidly, and the poles marked as
red dots in the inset show that this is achieved by means of poles delineating
approximate branch cuts $(-\infty-1]$ and $[1,\infty)$. Dashed lines show the
theoretically predicted slopes $(\ref{ierate})$ and $(\ref{rate4})$; their
heights are arbitrary.

Figure 7 shows a pair of numerical experiments confirming Theorems 5 and 9.
The figure has two panels, corresponding to domains $\Omega$ bounded by
inverted ellipses $I_{\rho}$ with $\rho=1.8$ and $\rho=1.3$. Each panel
compares the convergence of a polynomial approximation method (Vandermonde
with Arnoldi least squares [4]) against a rational one (AAA-least squares
[6]). The boundary data function is $h(x+iy)=(y+1)^{2}$, with the shift by $1$
introduced to break symmetry, and the boundary is discretized by $1500$
points, so that these computations involve matrices of reasonably modest size
with $1500$ rows and a few hundred columns.

For $\rho=1.8$, where $\Omega$ is barely indented at all, Figure 7 shows that
the polynomial method converges about $5$ times more slowly than the rational
method, requiring an increase of $n$ by about 38 for each digit of accuracy as
listed in Table 1.

The case $\rho=1.3$ shows the extreme behavior predicted by Theorem 5. The
rational method has slowed down by a factor of 2, whereas the polynomial
method has slowed down by a factor of 200, now needing an increase of degree
by $7000$ for each additional digit of accuracy. Note that convergence of the
polynomial method is still observed, but showing the upward-curving form
associated with subexponential convergence for a non-smooth boundary rather
than a straight line for exponential behavior. Evidently it would be
impossible in practice to get even two digits of accuracy by this method, even
though the boundary is analytic and the Schwarz function extends analytically
a nonnegligible distance $0.0346$ outside it. This distance is just
algebraically small, but its consequences are exponential.

The computations for Figure 7, about 120 numerical Laplace solutions all
together, required 9 seconds on our laptop.

##  7 Approximation on a general domain with an inlet

The exponential effect that makes polynomial approximation on nonconvex
domains problematic goes by the name of “crowding” in the literature of
numerical conformal mapping. (In elasticity theory it is called Saint-Venant’s
principle.) The observation here is that a conformal map involving a long and
narrow peninsula or finger, which hardly needs to be very long and narrow,
will involve exponential distortions. Peninsulas become inlets in our context
because approximation on a domain $\Omega$ depends on the conformal map of its
complement ${\mathbb{C}}\backslash\overline{\Omega}$.

The most systematic analysis of crowding that I know of appears in [11]. The
following definition is used there for an analytic Jordan domain $\Omega$:

We say that $\Omega$ contains a finger of length $L>0$ if there is a
rectangular channel of width $1$ defined by a pair of parallel line segments
of length $L$, disjoint from $\Omega$, such that $\Omega$ extends all the way
through the channel with parts of $\Omega$ lying outside both ends.

On the basis of this definition it is shown that the associated harmonic
measure (Theorem 2 of [11]), conformal mapping derivative (Theorem 3), radius
of univalence (Theorem 4), and approximating polynomial degrees (Theorem 5)
all scale in ways controlled by the factor $\exp(\pi L)$. Thus, for example,
peninsulas of length-to-width ratios $1$, $2$, and $3$ induce distortions of
magnitudes on the order of $23$, $540$, and $12{,}000$.

In the context of the present paper, it follows from these theorems that the
degrees of polynomial approximations to solutions of Laplace problems on any
domain $\Omega$ will have to grow by a factor at least as large as order
$\exp(\pi L)$ for each additional digit of accuracy, if $\Omega$ contains an
inlet of length-to-width ratio $L$. We do not spell out precise theorems.

It is interesting to check how closely this general result matches Theorem 5
for the case of the inverted ellipse $I_{\rho}$. Setting $\varepsilon=\rho-1$,
we find that for $I_{\rho}$ the inlet parameter $L$ scales as333Equation (24)
is derived by considering the rectangle $1\leq\hbox{\rm Re\kern 1.0pt}z\leq
2$, $-4\kern 0.4pt\varepsilon\leq\hbox{\rm Im\kern 1.0pt}z\leq 4\kern
0.4pt\varepsilon$, with aspect ratio $L=1/8\kern 0.4pt\varepsilon$. For
$\varepsilon<0.225$, the right inward-pointing finger of $I_{\rho}$ is
contained within the top and bottom sides of this rectangle while extending
outside both the left and right ends.

(24) $L\sim{1\over 8\kern 0.4pt\varepsilon},\quad\varepsilon\to 0.$

This implies by the $\exp(\pi L)$ results above that the analyticity radius
$R$ of sections 3 and 4 satisfies

(25) $R-1\leq O(\exp(-\pi/8\kern 0.4pt\varepsilon)),$

which is looser by the factor $2\pi$ than the actual result of (17),

(26) $R-1\sim O(\exp(-\pi^{2}/4\kern 0.4pt\varepsilon)).$

We have seen that polynomial approximations of Laplace solutions can be
expected almost always to be ineffective on domains with inlets. Conversely,
will rational approximations almost always be effective? Certainly not always,
for the boundary may be nonsmooth in the sense of having singularities of the
Schwarz function very close by. But as a smooth example it is interesting to
consider the inverted ellipse once more. From (24), the finger length is about
$1/8\kern 0.4pt\varepsilon$, whereas from Theorem 9, the convergence constant
is $\rho^{2}\sim 1+2\kern 0.4pt\varepsilon$. Thus in this case at least, the
convergence rate for rational approximations slows down only linearly with the
length of the finger.

##  8 Discussion

We have shown that polynomial approximations to solutions of Laplace problems
are essentially useless on non-convex domains, whereas rational approximations
are often very effective. In principle these results might have been obtained
decades ago, but in practice, everything has changed since the AAA and AAA-
least squares algorithms have made rational functions an easy tool for
numerical computation.

The Laplace equation $\Delta u=0$ is the limit of the Helmholtz equation
$\Delta u+k^{2}u=0$ as $k\to 0$, and poles of rational functions can be
regarded as the limits of point singularities of certain Hankel functions
[10]. It is known to experts in the solution of Helmholtz equation by the
method of fundamental solutions that when a region has an inlet, it is crucial
to include some Hankel singular points therein [3]. Thus the present paper
could be regarded as investigating a limiting case of an effect that is known
in the Helmholtz context, though we are not aware that theorems are to be
found in that literature analogous to what we have developed here.

## Acknowledgments

I am grateful for helpful comments (and in two cases for the derivation of
equation (17) in Theorem 5) from Alex Barnett, Jon Chapman, Peter Ebenfelt,
Astrid Herremans, Daan Huybrechs, Stefan Llewellyn Smith, Ed Saff, and Yidan
Xue.

## References

  * [1] S. Axler, Harmonic functions from a complex analysis viewpoint, Amer. Math. Monthly, 93 (1986), pp. 246–258.
  * [2] P. Baddoo, Lightning solvers for potential flows, Fluids, 5 (2020), p. 227.
  * [3] A. H. Barnett and T. Betcke, Stability and convergence of the method of fundamental solutions for Helmholtz problems on analytic domains, J. Comput. Phys., 227 (2008), pp. 7003–7026.
  * [4] P. D. Brubeck, Y. Nakatsukasa, and L. N. Trefethen, Vandermonde with Arnoldi, SIAM Rev., 63 (2021), pp. 405–415.
  * [5] S. Costa, E. Costamagna, and P. Di Barba, Modelling permanent-magnet excited uniform fields with rational approximations, manuscript submitted to ISEF 2023 (Pavia), 2023.
  * [6] S. Costa and L. N. Trefethen, AAA-least squares rational approximation and solution of Laplace problems, in A. Hujdurović et al., eds., European Congress of Mathematics, 2023, pp. 511–534.
  * [7] J. H. Curtiss, Interpolation by harmonic polynomials, J. SIAM, 10 (1962), pp. 709–736.
  * [8] P. J. Davis, The Schwarz Function and its Applications, Amer. Math. Soc., 1974.
  * [9] A. Gopal and L. N. Trefethen, Solving Laplace problems with corner singularities via rational functions, SIAM J. Numer. Anal., 56 (2019), pp. 2074–2094.
  * [10] A. Gopal and L. N. Trefethen, New Laplace and Helmholtz solvers, Proc. Nat. Acad. Sci., 116 (2019), 10223.
  * [11] A. Gopal and L. N. Trefethen, Representation of conformal maps by rational functions, Numer. Math., 142 (2019), pp. 359–382.
  * [12] N. Hale, N. J. Higham, and L. N. Trefethen, Computing $A^{\alpha}$, $\log(A)$, and related matrix functions by contour integrals, SIAM J. Numer. Anal., 46 (2008), pp. 2505–2523.
  * [13] N. Hale and L. N. Trefethen, New quadrature formulas from conformal maps, SIAM J. Numer. Anal., 46 (2008), pp. 930–948.
  * [14] P. Henrici, A survey of I. N. Vekua’s theory of elliptic partial differential equations with analytic coefficients, Z. angew. Math. Phys., 8 (1957), 169–203.
  * [15] A. Herremans, D. Huybrechs, and L. N. Trefethen, Resolution of singularities by rational functions, SIAM J. Numer. Anal., to appear.
  * [16] A. Hochman, Y. Leviatan, and J. K. White, On the use of rational-function fitting methods for the solution of 2D Laplace boundary-value problems, J. Comput. Phys., 238 (2013), pp. 337–358.
  * [17] E. Levin and E. B. Saff, Potential theoretic tools in polynomial and rational approximation, in J.-D. Fournier, et al. (eds.), Harmonic Analysis and Rational Approximation, v. 3, Springer, New York (2006), pp. 71–94.
  * [18] R. F. Millar, Singularities and the Rayleigh hypothesis for solutions to the Helmholtz equation, IMA J. Appl. Math., 37 (1986), pp. 155–171.
  * [19] C. B. Moler, Accurate bounds for the eigenvalues of the Laplacian and applications to rhombical domains, Tech. Rep. CS 121, Dept. Computer Sci., Stanford U., 1969, http://i.stanford.edu/pub/cstr/reports/cs/tr/69/121/CS-TR-69-121.pdf.
  * [20] Y. Nakatsukasa, O. Sète, and L. N. Trefethen, The AAA algorithm for rational approximation, SIAM J. Sci. Comput., 40 (2018), pp. A1494–A1522.
  * [21] Y. Nakatsukasa, O. Sète, and L. N. Trefethen, The first five years of the AAA algorithm, preprint, 2023. [Currently at people.maths.ox.ac.uk/trefethen/Papers; will soon be posted on arXiv.]
  * [22] Y. Nakatsukasa and L. N. Trefethen, An algorithm for real and complex rational minimax approximation, SIAM J. Sci. Comput., 42 (2020), pp. A3157–A3179.
  * [23] Z. Nehari, Conformal Mapping, Courier Corp., 2012.
  * [24] D. J. Newman, Rational approximation to $|x|$, Mich. Math. J., 11 (1964), pp. 11–14.
  * [25] E. A. Rakhmanov, The Gonchar–Stahl $\rho^{2}$-theorem and associated directions in the theory of rational approximations of analytic functions, Sb. Math., 207 (2016), pp. 1236–1266.
  * [26] C. Runge, Zur Theorie der eindeutigen analytischen Functionen, Acta Math., 6 (1885), pp. 229–244.
  * [27] H. A. Schwarz, Über einige Abbildungsaufgaben, J. reine angew. Math., 70 (1869), pp. 105–120.
  * [28] H. S. Shapiro, The Schwarz Function and its Generalization to Higher Dimensions, Wiley, 1992.
  * [29] H. Stahl, Orthogonal polynomials with complex-valued weight function. II, Constr. Approx., 2 (1986), pp. 241–251.
  * [30] H. Stahl, The convergence of Padé approximants to functions with branch points, J. Approx. Th., 91 (1997), pp. 139–204.
  * [31] G. Szegő, Conformal mapping of the interior of an ellipse onto a circle, Amer. Math. Monthly, 57 (1950), pp. 474–478.
  * [32] T. W. Tee and L. N. Trefethen, A rational spectral collocation method with adaptively transformed Chebyshev grid points, SIAM J. Sci. Comput., 28 (2006), pp. 1798–1811.
  * [33] L. N. Trefethen, Series solution of Laplace problems, ANZIAM J., 60 (2018), pp. 1–26.
  * [34] L. N. Trefethen, Approximation Theory and Approximation Practice, Extended Edition, SIAM, 2019.
  * [35] L. N. Trefethen, Numerical analytic continuation, Japan J. Appl. Math., 2023.
  * [36] I. N. Vekua, New Methods for Solving Elliptic Equations, North-Holland (1967).
  * [37] J. L. Walsh, Über den Grad der Approximation einer analytischen Funktion, Münchner Berichte (1926), pp. 223–229.
  * [38] J. L. Walsh, The approximation of harmonic functions by harmonic polynomials and by harmonic rational functions, Bull. Amer. Math. Soc., 35 (1929), pp. 499–544.
  * [39] J. L. Walsh, Interpolation and Approximation by Polynomials and Rational Functions in the Complex Domain, 5th ed., Amer. Math. Soc., 1969.
  * [40] Y. Xue, S. Waters, and L. N. Trefethen, Computation of 2D Stokes flows via lightning and AAA rational approximation, SIAM J. Sci. Comput., submitted.


11institutetext: KLleon Tech. 11email<EMAIL_ADDRESS>
22institutetext: Kyung Hee University
22email<EMAIL_ADDRESS>
# IntereStyle: Encoding an Interest Region for Robust StyleGAN Inversion

Seung-Jun Moon 11 Gyeong-Moon Park Corresponding Author22

###### Abstract

Recently, manipulation of real-world images has been highly elaborated along
with the development of Generative Adversarial Networks (GANs) and
corresponding encoders, which embed real-world images into the latent space.
However, designing encoders of GAN still remains a challenging task due to the
trade-off between distortion and perception. In this paper, we point out that
the existing encoders try to lower the distortion not only on the interest
region, e.g., human facial region but also on the uninterest region, e.g.,
background patterns and obstacles. However, most uninterest regions in real-
world images are located at out-of-distribution (OOD), which are infeasible to
be ideally reconstructed by generative models. Moreover, we empirically find
that the uninterest region overlapped with the interest region can mangle the
original feature of the interest region, e.g., a microphone overlapped with a
facial region is inverted into the white beard. As a result, lowering the
distortion of the whole image while maintaining the perceptual quality is very
challenging. To overcome this trade-off, we propose a simple yet effective
encoder training scheme, coined IntereStyle, which facilitates encoding by
focusing on the interest region. IntereStyle steers the encoder to disentangle
the encodings of the interest and uninterest regions. To this end, we filter
the information of the uninterest region iteratively to regulate the negative
impact of the uninterest region. We demonstrate that IntereStyle achieves both
lower distortion and higher perceptual quality compared to the existing state-
of-the-art encoders. Especially, our model robustly conserves features of the
original images, which shows the robust image editing and style mixing
results. We will release our code with the pre-trained model after the review.

###### Keywords:

StyleGAN, robust GAN inversion, interest region, interest disentanglement,
uninterest filter

##  1 Introduction

Figure 1:  Encoding of IntereStyle. Original images, interest region,
inversion, the difference between the original images and their inversions,
and the editing results (smile and Mohawk). The magnitude of the difference
between the original and inversion images is colored in red. Our model
successfully minimizes distortion on the interest region, even without the
interest region mask for the inference. Moreover, even with low distortion,
our model shows high editability.

Recently, as Generative Adversarial Networks (GANs) [15] have been remarkably
developed, real-world image editing through latent manipulation has been
prevalent [27, 28, 33, 30, 32, 25]. Especially, the strong disentangled
property of StyleGAN [18, 19] latent space, i.e., $W$, enables scrupulous
image editing [32, 22], which can change only desirable features, e.g., facial
expression, while maintaining the others, e.g., identity and hairstyle. For
editing the image precisely with StyleGAN, it is required to get the suitable
style latent, from which StyleGAN can reconstruct the image that has low
distortion, high perceptual quality, and editability without deforming the
feature of the original image.

Though StyleGAN is generally known to construct the image with high perceptual
quality, the original style space $W$ is not enough to represent every real-
world image with low distortion. Consequently, a vast majority of recent
StyleGAN encoders, including optimization-based methods, embed images into
$W+$ space [1, 24, 3]. $W$ uses the identical style vector for every layer in
StyleGAN, obtained by the mapping function. On the other hand, $W+$ space
provides a different style vector per layer and can even provide a random
style vector in $\mathbb{R}^{512}$. However, as the distribution of style
latent is far from $W$, reconstructed images show low perceptual quality and
editability [30, 25]. Consequently, lowering the distortion while keeping the
other factors is still challenging.

Figure 2:  Lowering distortion on the uninterest region. Inversion results of
$pSp$ [24], Restyle [3], and ours. An overlapped obstacle (i.e., hand) on the
facial region precludes clean inversion. Firstly, $pSp$ shows high distortion
on the eyes and generates unrealistic facial shapes on the obstacle region.
Restyle tries to reconstruct the obstacle region, but the reconstructed image
shows artifacts on the nose and chin. On the contrary, our model shows the
lowest distortion among the existing models, while maintaining high perceptual
quality as shown above.

In this paper, we claim that training to lower distortion on the entire region
of the image directly is undesirable. In most cases, images contain regions
that cannot be generated due to the inherent limitation of generators. Figure
1 shows clear examples of real-world images in the facial domain, which
contain regions that are infeasible to be generated, e.g., hats, accessories,
and noisy backgrounds. Therefore, an encoder needs to concentrate on the
generable region for inversion while ignoring the un-generable region (e.g.,
non-facial region for StyleGAN trained with FFHQ). This strategy helps the
latents inverted from the generable region to be close to $W$, which show high
perceptual quality and editability, as shown in Figure 1.

Another observation is that an attempt to reconstruct the region which is not
generable induces severe distortion even on the other generable regions. For
example, in Figure 2, a hand overlapped with the facial region is not
generable by GAN encoders. Restyle [3], which shows the lowest distortion
among all encoder-based inversion models until now, tries to lower distortion
on the hand too, which rather causes catastrophic distortions on the nose and
chin.

In the light of these observations, it is important to distinguish the region
to be reconstructed elaborately from the rest. Here we define the term
interest region, where the model focuses on the precise reconstruction with
low distortion and high perceptual quality. Practically, in most cases, the
interest region is aligned with the generable region of the image. For
example, in facial image generation, the main interests are the face and hair
parts of the output images, which are easier to generate than backgrounds. By
focusing on the interest region, we can reduce distortion without any
additional task, such as an attempt to encode latent excessively far from $W$
[8].

####  1.0.1 Contributions

We propose a simple yet effective method for training a StyleGAN encoder,
coined IntereStyle, which steers the encoder to invert given images by
focusing on the interest region. In particular, we introduce two novel
training schemes for the StyleGAN encoder: (a) Interest Disentanglement (InD)
and (b) Uninterest Filter (UnF). First, InD precludes the style latent, which
includes the information on the uninterest region, from distorting the
inversion result of the interest region. Second, UnF filters the information
of the uninterest region, which prevents our model from redundantly attending
to the uninterest region. UnF boosts the effect of InD by forcing the model
not to focus on the uninterest region overly. In addition, we propose a very
simple yet effective scheme for determining the interest region, required only
at the training stage.

We demonstrate that IntereStyle, combined with the iterative refinement [3],
effectively reduces the distortion at the interest region of CelebA-HQ-test
dataset. To the best of our knowledge, IntereStyle achieves the lowest
distortion among the existing state-of-the-art encoder-based StyleGAN
inversion models without generator tuning. Moreover, we qualitatively show
that our model robustly preserves features of the original images even with
overlapped obstacles, while other baselines fail to. Lastly, we show the
experimental results for image editing via InterFaceGAN [28], StyleCLIP [22],
and style mixing [18] results, where our model shows remarkably robust outputs
when input images contain significant noises, e.g., obstacles on the face.

##  2 Related Work

####  2.0.1 GAN Inversion

GAN inversion aims to transform given real-world images into latent vectors
from which a pre-trained GAN model can reconstruct the original image. In the
early stage of GAN inversion, the majority of models rely partially [36, 4, 5,
35] or entirely [11, 23, 1, 2, 16, 10, 12, 26] on the optimization steps per
image. Though the optimization-based models show high inversion qualities,
these models should perform numerous optimization steps per every input image
[20], which are extremely time-consuming. Thus, training encoders that map
images into the latent space has been prevalent to invert images in the real-
time domain [29, 35, 24, 30, 3, 31]. However, regardless of encoding methods,
the existing state-of-the-art GAN inversion models focus on the whole region
of images [3, 24, 30, 2], including both interest and uninterest regions. We
propose that focusing mainly on the interest region during GAN inversion
improves the perceptual quality and editability of inverted images.

(a) Variance of encoders

(b) Variance of Restyle per iteration

Figure 3:  Variance of latents from each encoder. We plot the variance of
latents, derived from 2,800 CelebA-HQ test images with each encoder-based
StyleGAN inversion model. The existing iterative refinement-based model,
Restyle, shows relatively high variance among style latents per all layers.
The variance of Restyle latents at iteration $i$, $\text{Restyle}_{i}$,
increases along with $i$. $e4e$, which engages variation minimization loss
term at the training scheme, shows relatively lower variance. We plot with a
log-scale $x$-axis for better visualization.

####  2.0.2 GAN Inversion Trade-Off

The desirable GAN inversion should consider both distortion and perceptual
quality of inverted images [6, 30, 25]. However, due to the trade-off between
two features, maintaining low distortion while enhancing the perceptual
quality remains a challenging task [30, 25]. Especially in StyleGAN, an
inverted image from the latent far from $W$ distribution achieves lower
distortion [1, 2, 24] but shows lower perceptual quality [30] than the image
from $W$ distribution. Moreover, the latent far from $W$ distribution shows
lower editability [30, 25], which makes editing the inverted image harder.
Here the variance among latents for all layers can be used as an indicator of
distance from $W$, where $W$ shows a zero variance due to the identical latent
per layer.111Technically, we should identify whether the latents are from the
mapping network of StyleGAN or not, but for simplicity, we only use the
variance. As shown in Figure 3, the existing StyleGAN inversion models that
show low distortion but suffer from low perceptual quality, e.g., $pSp$ [24]
and Restyle [3], show relatively high variance among latents for all layers of
StyleGAN. Especially, Figure 3(b) shows that Restyle gradually increases the
variance of latents as the iteration refinement progresses. In the case of
$e4e$ [30], it encodes images into latents close to $W$ but with high
distortion. In contrast to the existing methods, our model focuses on lowering
distortion at the interest region, i.e., hair and face. Since it is much
easier than lowering at the uninterest region, i.e., irregular backgrounds,
hats, and accessories, our model successfully achieves lower distortion than
the existing models while avoiding the drop of high perceptual quality.

##  3 Method

Figure 4:  Overall structure of IntereStyle. IntereStyle trained with total of
$N$-th iteration, receives $N$ images, i.e., $I_{1},I_{2},...,I_{N}$. $I_{i}$
is an original image passed through a low-pass filter with radius $r_{i}$,
which steers the model to focus on the coarse features at the early step of
iterations, and $I_{i}$ gets clearer as $i$ grows. The Encoder targets to
embed the difference of two images $I_{i}$ and $\hat{y}_{i-1}$ into the latent
space, $\Delta_{i-1}$. After the $N$-th iteration is finished, We apply
interest disentanglement. We multiply $\hat{y}_{N}$ with the $I_{mask}$, to
wipe out the uninterest region. We yield $\Delta_{b}$, by computing the
difference between $I$ and $I\cdot I_{mask}$. By adding $\Delta_{b}$ to the
obtained latent $w_{N}$, we yield the output $\hat{y}$. At the inference
stage, we yield the final output $\hat{y}_{N}$, without applying interest
disentanglement.  Figure 5:  Mask dilation. We compare the interest region
obtained by the raw mask and the dilated mask. In the raw mask, the interest
region excludes the information related to the facial boundary, which occurs
distortion of a facial shape. Consequently, we dilate the mask to force the
interest region to include the facial boundary information, as shown in
$I\cdot\text{Dilated Mask}$.

In this section, we propose a simple yet effective StyleGAN encoder training
scheme named IntereStyle. We first introduce our notation and the model
architecture. Then, we introduce how to determine the interest region in input
images. Next, we propose two novel methods: interest disentanglement and
uninterest filter in Section 3.3 and Section 3.4, respectively. Finally, we
describe the whole training scheme of IntereStyle in Section 3.5.

###  3.1 Notation and Architecture

Our architecture is shown in Figure 4, which is based on $pSp$ [24] model,
combined with the iterative refinement [3, 31]. At $i$-th iteration of the
iterative refinement, our encoder $E$ receives a latent calculated at the
previous step, $\textbf{w}_{i-1}$222When $i=1$, we utilize $\textbf{w}_{0}$ as
an average latent of StyleGAN., together with a pair of images. The pair
consists of $(\hat{y}_{i-1},I_{i})$, where $\hat{y}_{i-1}$ is a decoded result
of $\textbf{w}_{i-1}$ via generator $G$, i.e.,
$\hat{y}_{i-1}=G(\textbf{w}_{i-1})$, and $I_{i}$ is a preprocessed ground
truth image, $I$, by our proposed method in Section 3.4. $E$ targets to encode
the difference between $\hat{y}_{i-1}$ and $I_{i}$ into the latent,
$\Delta_{i}$. Consequently, $G$ can yield an image $\hat{y}_{i}$, which is
more similar to $I_{i}$ than $\hat{y}_{i-1}$, by decoding the latent
$\textbf{w}_{i}=\textbf{w}_{i-1}+\Delta_{i}$. Our model iteratively refines
the latent with a total of $N$ iterations. Finally, we utilize a loss function
$L_{image}$ for training, consisting of the weighted sum of $L_{2}$, $LPIPS$
[34], and $L_{ID}$ [24]. We explain the details of each loss in Appendix A.

###  3.2 Interest Region

To guide the model to focus on the interest region, we need to label the
interest region first. The interest region can be designated arbitrarily
according to the usage of the inversion model. For instance, facial and hair
regions for the facial domain, and the whole body for the animal domain can be
set as the interest region. For labeling this interest region, the off-the-
shelf segmentation networks are used, which is described in Section 4.
However, directly using the segmentation masks from networks causes the
distortion of facial boundaries in the generated image. To accommodate the
boundary information, we use the dilated segmentation mask containing the
interest region, as shown in Figure 5. Without dilation, the loss term on the
interest region cannot penalize the inverted face on the uninterest region.
Consequently, we dilate the mask to penalize the overflowed reconstruction of
the interest region boundary. Though the small part of the uninterest region
would be included in the interest region through the dilation, we empirically
find that our model still precisely generates the interest region without any
distortion of boundaries. We visually show the effect of mask dilation at the
ablation study in Section 4.1.1.

###  3.3 Interest Disentanglement

To enforce the model to invert the interest region into the latent space
precisely, we should train the model to concentrate on the interest region
regardless of the uninterest region. However, due to the spatial-agnostic
feature of Adaptive Instance Normalization (AdaIN) [21], inverted style
latents considering the uninterest region may deteriorate the inversion
quality of the interest region. To prevent the encoded style of the uninterest
region from deforming the inverted result of the interest region, the
inversion of each region should be disentangled.

As $E$ encodes the difference of the input pair of images in ideal, the latent
$\Delta$ obtained by encoding the pair of images that only differ on the
uninterest region does not contain the information of the interest region. In
other words, the decoding results from the latents w and $\textbf{w}+\Delta$
should be the same on the interest region. Motivated by the above, we propose
a simple method named Interest Disentanglement (InD) to distinguish the
inversions of the interest region and uninterest region. We construct the pair
of input images for InD as follows: the original image $I$, and the same $I$
but multiplied with the interest region mask. Then, as shown in Figure 4, we
can yield the pair of images which only differs in the uninterest region, and
the corresponding latent from $E$, $\Delta_{b}$. Ideally, the information in
$\Delta_{b}$ is solely related to the uninterest region, which implies
$\textbf{w}_{N}$ generates the interest region robustly even $\Delta_{b}$ is
added. Consequently, we define InD loss, $L_{InD}$ as follows;

$L_{InD}:=L_{image}(I\cdot I_{mask},\hat{y}\cdot I_{mask}),$ (1)

where $\hat{y}$ is the inversion result from the latent
$\textbf{w}=\textbf{w}_{N}+\Delta_{b}$. We apply Interest Disentanglement only
at the training stage, which enables the inference without the interest region
mask. We empirically find that IntereStyle focuses on the interest region
without any prior mask given, after the training.

###  3.4 Uninterest Filter

At the early steps of the iterative refinement, $E$ focuses on reducing the
distortion of the uninterest region [3]. Due to the spatial-agnostic feature
of AdaIN, we claim that excessively focusing on the uninterest region hinders
the inversion of the interest region. We propose a method named Uninterest
Filter (UnF), to make $E$ concentrate on the interest region at every
iteration consistently. UnF eliminates details of the uninterest region, which
is inherently infeasible to reconstruct. Thus, $E$ can reduce the redundant
attention on the uninterest region for the low distortion. In detail, UnF
eases calculating $\Delta_{i}$ by blurring the uninterest region of $I$ at
each iteration, with a low-pass Gaussian Filter with radius $r$, $LPF_{r}$. As
shown in Figure 4, UnF gradually reduces the radius of Gaussian filter of
$LPF$ as iterations progress, with the following two reasons; First, the
redundant attention on the uninterest region is considerably severe at the
early stage of the iterations [3]. Consequently, we should blur the image at
the early iterations heavily. Second, excessive blur results in the severe
texture difference between the interest and uninterest region. We claim that
$E$ is implicitly trained to encode the difference of the whole region, which
can be biased to produce the blurred region when the blurred images are
consistently given. For the realistic generation, the input at the $N$-th
iteration, $I_{N}$ is deblurred, i.e., identical to $I$. We calculate the
input image at the $i$-th iteration as below:

$I_{i}=\begin{cases}I\cdot
I_{mask}+LPF_{r_{i}}(I\cdot(1-I_{mask})),&\text{$0<i<N$}\\\
I,&\text{$i=N$}.\end{cases}$ (2)

###  3.5 Training IntereStyle

At the training stage, we jointly train the model with the off-the-shelf
encoder training loss [24] $L_{image}$ and $L_{InD}$. However, in contrast to
Restyle [3], which back-propagates $N$ times per batch, we back-propagate only
once after the $N$-th iteration is over. Thus, ours show relatively faster
training speed compared to Restyle. Our final training loss is defined as
below:

$L_{total}:=L_{image}(I\cdot I_{mask},\hat{y}_{N}\cdot I_{mask})+\lambda
L_{InD}.$ (3)

Our proposed methods, InD and UnF are synergistic at the training; While InD
disentangles the inversion of the uninterest region, UnF forces to look at the
interest region. Though applying $L_{image}$ to the images multiplied with
$I_{mask}$ inherently drives $E$ to focus on the interest region, InD is
essential for robust training. Without $L_{InD}$, we find $E$ implicitly
contains information of the uninterest region into $\Delta_{i}$, which affects
the inversion of the interest region by AdaIN.

##  4 Experiments

In this section, we briefly introduce our datasets and baselines first. The
implementation details are described in Appendix A. Then, we compare the
inversion results with baselines and ablation scenarios, both in qualitative
and quantitative ways. Next, we compare the image manipulation of our model,
together with baselines. Finally, we look into the iterative scheme of our
model with Restyle. Though we mainly show the results on the facial domain, we
note that our method shows remarkable results in various domains. We show the
experimental results on the animal domain in Figure 6 briefly and the plenty
experimental results in Appendix D.

####  4.0.1 Datasets

For the facial domain, we trained the encoder using the FFHQ dataset,
consisting of 70,000 human facial images. For the validation, we used the
CelebA-HQ test set, consisting of 2,800 human facial images. We did not add or
change any alignment or augmentation procedures compared to the existing
encoder training methods [24, 3, 30] for a fair comparison. To generate the
interest and uninterest region masks, we used the pre-trained Graphonomy [14]
model. For the animal domain, we used AFHQ wild dataset [9] for training and
validation, which consists of 4,730 and 500 images, respectively. We used the
pre-trained DEtection TRansformer (DE-TR; [7]) for obtaining the interest
region.

####  4.0.2 Baselines

We compared our model with the several well-known StyleGAN encoders: IDGI
[35], $pSp$ [24], $e4e$ [30], and Restyle [3]. Moreover, in the case of the
qualitative comparison of inversion, we additionally compared it with the
optimization-based model [1, 2], which is well-known for its outstanding
performance. For the baseline models, we used the pre-trained weights that are
publicly available for evaluation. Please refer to Appendix C for more
detailed information of each baseline.

###  4.1 Inversion Evaluation

####  4.1.1 Qualitative Evaluation

Figure 6:  Qualitative comparison. Comparison of various StyleGAN inversion
methods. IntereStyle effectively disentangled the uninterest regions (e.g.,
mic, letter, fingers and wood) from the interest region, which enabled robust
handling of artifacts. However, the baseline models suffered from artifacts,
which significantly deformed the feature of original images. Best viewed in
zoom-in.

Model | IDGI | pSp | e4e | $\text{Restyle}_{pSp}$ | $\text{Restyle}_{e4e}$ | IntereStyle
---|---|---|---|---|---|---
Region | Interest | Face | Interest | Face | Interest | Face | Interest | Face | Interest | Face | Interest | Face
$L_{2}$ | 0.030 | 0.010 | 0.018 | 0.006 | 0.023 | 0.007 | 0.015 | 0.004 | 0.021 | 0.007 | 0.013 | 0.003
LPIPS | 0.116 | 0.053 | 0.095 | 0.046 | 0.111 | 0.051 | 0.088 | 0.040 | 0.109 | 0.054 | 0.075 | 0.036
ID Similarity | 0.18 | 0.56 | 0.47 | 0.65 | 0.51 | 0.68

Table 1: Quantitative comparison. We calculated each result by multiplying the
mask, i.e., interest and facial masks, for the exact comparison of inversion
quality of each region. IntereStyle showed the lowest $L_{2}$ and LPIPS on
both the interest and facial regions among the state-of-the-art StyleGAN
inversion models. Moreover, IntereStyle showed the best ID similarity among
the baselines.

Figure 6 shows the inverted images of IntereStyle and two StyleGAN inversion
baselines, Image2StyleGAN [1] and Restyle [3]. In this figure, we show the
entire inversion results along with the cropped images, which correspond to
the areas of overlapping of the interest and uninterest regions. Without our
robust inversion schemes, mere attempts to lower distortion over the entire
region often occurred severe artifacts or feature deformations. Indeed, the
baselines produced artifacts, which severely lower the perceptual quality. In
addition, they mangled features of original images in some cases. For
instance, $\text{Restyle}_{pSp}$ turned the microphone into a white beard,
which does not exist in the original image. The optimization-based inversion
relatively mitigated artifacts among the baselines, but still suffered from
them. Moreover, it required more than 200 times longer inference time compared
to the one of IntereStyle. In contrast, IntereStyle showed the most robust
outputs compared to all baselines, which best preserved the features of
original images without artifacts.

In Figure 7, we qualitatively showed the effectiveness of the mask dilation.
Without dilation, the model could not precisely reconstruct the original
boundary of the interest region, which was denoted as the red region. In
contrast, with the mask dilation, our model minimized the boundary
deformation.

Figure 7:  Ablation study on dilated mask. Comparison of the results in the
cases of using raw mask and dilated mask. For measuring the equivalence of the
facial boundaries between the original and inverted images, we used Graphonomy
to obtain the facial region of each image. We then calculated the difference
of each facial region from the original one, denoted by red on the right side.
While the model without the dilated mask could not reconstruct the exact
boundary, our model minimized this error effectively.

Method | $L_{2}$ | LPIPS
---|---|---
| Interest | Face | Interest | Face
Baseline Restyle [3] | 0.015 | 0.004 | 0.088 | 0.040
\+ $L_{image}$ on the interest region | 0.013 | 0.005 | 0.084 | 0.038
\+ Interest Disentanglement (InD) | 0.012 | 0.003 | 0.078 | 0.037
\+ Uninterest Filter (UnF) | 0.013 | 0.003 | 0.075 | 0.036

Table 2:  Ablation study. Performance comparison by adding each component of
IntereStyle. InD and UnF contributed to the improvement of the model, which
showed better results than naïvely applying $L_{image}$ on the interest
region. Especially, InD is advantageous for reducing $L_{2}$, and UnF mainly
reduces LPIPS.

####  4.1.2 Quantitative Evaluation

We used $L_{2}$ and LPIPS [34] losses and measured ID similarity [24] by
utilizing the pre-trained Curricularface [17], which shows the state-of-the-
art performance on facial recognition. We measured the quality on the interest
region, the facial and hair regions in this paper, which need to be inverted
precisely. To this end, we multiplied the interest region mask at the
calculation of ID similarity to preclude the facial recognition model from
being affected by the non-facial region. Since the facial recognition
performance is dependent on the features of the non-facial region [13], the
inverted images are prone to be identified as similar faces with the original
images due to the resemblance of non-facial regions. To compare the models
solely on the facial region, we should wipe out the uninterest region.

As shown in Table 1, IntereStyle showed low distortion on both the interest
and facial regions and preserved the identity well simultaneously. We conclude
that focusing on the interest region is indeed helpful for robust inversion.
Table 2 shows the ablation study by sequentially applying each component of
our method to measure the effectiveness of the model performance. InD reduced
the negative effect of the uninterest region, which indeed lowered distortion,
compared to naïvely applying $L_{image}$ on the interest region. UnF lowered
LPIPS by forcing the model to preserve features of the interest region. Please
refer to Appendix D for more detailed results of each ablation model.

(a) Editing through InterFaceGAN

(b) Editing through StyleCLIP

Figure 8:  Editing comparison. Edited images via (a) InterFaceGAN and (b)
StyleCLIP. Our model showed robust inversion results together with high
editability consistently, while the baselines failed in various cases. First
of all, $pSp$ and $e4e$ failed to invert robustly, which ignored makeups and
the detailed appearance of each image. In the cases of $\text{Restyle}_{pSp}$
and $\text{Restyle}_{e4e}$, both were vulnerable with the overlapped
obstacles. In the right image of (a), $\text{Restyle}_{pSp}$ generated severe
artifacts, while $\text{Restyle}_{e4e}$ distorted the shape of mouth
significantly. Moreover, the Restyle-based models showed poor editability. In
(b), $\text{Restyle}_{pSp}$ and $\text{Restyle}_{e4e}$ failed to change the
hairstyle in the Mohawk case.

###  4.2 Editing via Latent Manipulation

Inversion of GAN is deeply related to the image manipulation on the latent
space. In this section, we compare the quality of edited images produced by
various StyleGAN inversion models [24, 30, 3], manipulated via InterFaceGAN
[28] and StyleCLIP [22] methods, and style mixing [18, 19]. Figure 8 shows the
results of editing real-world images via InterFaceGAN and StyleCLIP, together
with the inversion results. We changed three attributes for each method;
smile, age, and pose for InterFaceGAN, and “smile”, “lipstick”, and “Mohawk
hairstyle” for StyleCLIP. Our model showed high inversion and perceptual
qualities consistently among various editing scenarios, even with strong
makeups or obstacles. However, $pSp$ and $e4e$ missed important features of
images, such as makeups or eye shapes. Moreover, $pSp$ produced artifacts in
several editing scenarios. In the cases of $\text{Restyle}_{pSp}$ and
$\text{Restyle}_{e4e}$, they failed to robustly handle obstacles. In the right
side of Figure 8(a), $\text{Restyle}_{pSp}$ produced severe artifacts around
the mouth, while $\text{Restyle}_{e4e}$ totally changed the shape. Moreover,
the Restyle-based models showed low editability in specific cases, such as
“Mohawk”.

Figure 9:  Style mixing results. We interpolated latents from Source A to
Source B. We took styles corresponding to either coarse ($4^{2}-8^{2}$),
middle ($16^{2}-32^{2}$), or fine ($64^{2}-1024^{2}$) resolution from source B
and took the rest from source A. IntereStyle showed the robust results on the
interpolation, even with obstacles on the original source images, while
$\text{Restyle}_{pSp}$ suffered from severe artifacts.

To attribute to the superior disentanglement feature of StyleGAN latent space
[28], we can separately manipulate the coarse and fine features of images.
Following the settings from the StyleGAN [18] experiment, we took styles
corresponding to either coarse, middle, or fine spatial resolution,
respectively, from the latent of source B, and the others were taken from the
latent of source A. Moreover, we mixed more than one hard case, e.g.,
obstacles on faces and extreme poses, to evaluate the robustness of our model.
As shown in Figure 9, our model showed higher perceptual quality on the
interpolated images compared to $\text{Restyle}_{pSp}$. $\text{Restyle}_{pSp}$
produced images with texture shift, i.e., images with cartoon-like texture,
distorted facial shape, and undesirable artifacts during the style mixing. In
contrast, our model generated stable facial outputs. Additional qualitative
results are shown in Appendix D.2.

(a) Iterative outputs

(b) Variance of latents

Figure 10:  Outputs and variance at each iteration. We compared intermediate
outputs $\hat{y}_{i}$ of an example from CelebA-HQ test dataset, and the
average of variances of latents among all test images at each iteration.
Restyle showed severe artifacts on the interest region and a steep variance
increment at each iteration, while IntereStyle showed robust inversion and
maintained low variances.

###  4.3 Iterative Refinement of IntereStyle

We compared the progress of iterative refinement between Restyle [3] and
IntereStyle in Figure 10. Restyle reconstructed most of the coarse features
within a few steps, while the variance of Restyle increased consistently as
iteration progressed. In other words, the reduction of distortion is marginal,
though Restyle excessively focuses on this. Consequently, the latent from
Restyle was located far from $W$, which yields an image with low perceptual
quality. In contrast, IntereStyle concentrated on the interest region that
could be generated without a broad extension from $W$. Consequently,
IntereStyle effectively reduced distortion on the interest region by iteration
while maintaining high perceptual quality.

##  5 Conclusions

For StyleGAN inversion, focusing on the interest region is essential but
under-explored yet. We found excessive attention on the uninterest region
occurs the drop of perceptual quality and high distortion on the interest
region. We proposed a simple yet effective StyleGAN encoder training scheme,
coined IntereStyle, composed of Interest Disentanglement and Uninterest
Filter. We demonstrated that IntereStyle showed both low distortion and high
perceptual inversion quality, and enabled various latent manipulations
robustly for image editing. We look forward to our work to be widely used in
future research or the industry field, which needs a delicate inversion of the
interest region for image editing.

##  6 Acknowledgement

This work was supported by the National Research Foundation of Korea(NRF)
grant funded by the Korea government(MSIT) (No. 2021R1G1A1094379), and in part
by the Institute of Information and Communications Technology Planning and
Evaluation (IITP) grant funded by the Korea Government (MSIT) (Artificial
Intelligence Innovation Hub) under Grant 2021-0-02068.

## References

  * [1] Abdal, R., Qin, Y., Wonka, P.: Image2stylegan: How to embed images into the stylegan latent space? In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 4432–4441 (2019)
  * [2] Abdal, R., Qin, Y., Wonka, P.: Image2stylegan++: How to edit the embedded images? In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 8296–8305 (2020)
  * [3] Alaluf, Y., Patashnik, O., Cohen-Or, D.: Restyle: A residual-based stylegan encoder via iterative refinement. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 6711–6720 (2021)
  * [4] Bau, D., Strobelt, H., Peebles, W., Wulff, J., Zhou, B., Zhu, J.Y., Torralba, A.: Semantic photo manipulation with a generative image prior. arXiv preprint arXiv:2005.07727 (2020)
  * [5] Bau, D., Zhu, J.Y., Wulff, J., Peebles, W., Strobelt, H., Zhou, B., Torralba, A.: Seeing what a gan cannot generate. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 4502–4511 (2019)
  * [6] Blau, Y., Michaeli, T.: The perception-distortion tradeoff. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 6228–6237 (2018)
  * [7] Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., Zagoruyko, S.: End-to-end object detection with transformers. In: European Conference on Computer Vision. pp. 213–229. Springer (2020)
  * [8] Chen, L.C., Zhu, Y., Papandreou, G., Schroff, F., Adam, H.: Encoder-decoder with atrous separable convolution for semantic image segmentation. In: Proceedings of the European conference on computer vision (ECCV). pp. 801–818 (2018)
  * [9] Choi, Y., Uh, Y., Yoo, J., Ha, J.W.: Stargan v2: Diverse image synthesis for multiple domains. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 8188–8197 (2020)
  * [10] Collins, E., Bala, R., Price, B., Susstrunk, S.: Editing in style: Uncovering the local semantics of gans. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 5771–5780 (2020)
  * [11] Creswell, A., Bharath, A.A.: Inverting the generator of a generative adversarial network. IEEE transactions on neural networks and learning systems 30(7), 1967–1974 (2018)
  * [12] Daras, G., Odena, A., Zhang, H., Dimakis, A.G.: Your local gan: Designing two dimensional local attention mechanisms for generative models. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 14531–14539 (2020)
  * [13] Deng, J., Guo, J., Xue, N., Zafeiriou, S.: Arcface: Additive angular margin loss for deep face recognition. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 4690–4699 (2019)
  * [14] Gong, K., Gao, Y., Liang, X., Shen, X., Wang, M., Lin, L.: Graphonomy: Universal human parsing via graph transfer learning. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7450–7459 (2019)
  * [15] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial nets. Advances in neural information processing systems 27 (2014)
  * [16] Gu, J., Shen, Y., Zhou, B.: Image processing using multi-code gan prior. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 3012–3021 (2020)
  * [17] Huang, Y., Wang, Y., Tai, Y., Liu, X., Shen, P., Li, S., Li, J., Huang, F.: Curricularface: adaptive curriculum learning loss for deep face recognition. In: proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pp. 5901–5910 (2020)
  * [18] Karras, T., Laine, S., Aila, T.: A style-based generator architecture for generative adversarial networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 4401–4410 (2019)
  * [19] Karras, T., Laine, S., Aittala, M., Hellsten, J., Lehtinen, J., Aila, T.: Analyzing and improving the image quality of stylegan. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 8110–8119 (2020)
  * [20] Kim, H., Choi, Y., Kim, J., Yoo, S., Uh, Y.: Stylemapgan: Exploiting spatial dimensions of latent in gan for real-time image editing. arXiv preprint arXiv:2104.14754 (2021)
  * [21] Park, T., Liu, M.Y., Wang, T.C., Zhu, J.Y.: Semantic image synthesis with spatially-adaptive normalization. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2337–2346 (2019)
  * [22] Patashnik, O., Wu, Z., Shechtman, E., Cohen-Or, D., Lischinski, D.: Styleclip: Text-driven manipulation of stylegan imagery. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 2085–2094 (2021)
  * [23] Raj, A., Li, Y., Bresler, Y.: Gan-based projector for faster recovery with convergence guarantees in linear inverse problems. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 5602–5611 (2019)
  * [24] Richardson, E., Alaluf, Y., Patashnik, O., Nitzan, Y., Azar, Y., Shapiro, S., Cohen-Or, D.: Encoding in style: a stylegan encoder for image-to-image translation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2287–2296 (2021)
  * [25] Roich, D., Mokady, R., Bermano, A.H., Cohen-Or, D.: Pivotal tuning for latent-based editing of real images. arXiv preprint arXiv:2106.05744 (2021)
  * [26] Saha, R., Duke, B., Shkurti, F., Taylor, G.W., Aarabi, P.: Loho: Latent optimization of hairstyles via orthogonalization. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 1984–1993 (2021)
  * [27] Shen, Y., Gu, J., Tang, X., Zhou, B.: Interpreting the latent space of gans for semantic face editing. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 9243–9252 (2020)
  * [28] Shen, Y., Yang, C., Tang, X., Zhou, B.: Interfacegan: Interpreting the disentangled face representation learned by gans. IEEE transactions on pattern analysis and machine intelligence (2020)
  * [29] Tewari, A., Elgharib, M., Bharaj, G., Bernard, F., Seidel, H.P., Pérez, P., Zollhofer, M., Theobalt, C.: Stylerig: Rigging stylegan for 3d control over portrait images. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 6142–6151 (2020)
  * [30] Tov, O., Alaluf, Y., Nitzan, Y., Patashnik, O., Cohen-Or, D.: Designing an encoder for stylegan image manipulation. ACM Transactions on Graphics (TOG) 40(4), 1–14 (2021)
  * [31] Wei, T., Chen, D., Zhou, W., Liao, J., Zhang, W., Yuan, L., Hua, G., Yu, N.: A simple baseline for stylegan inversion. arXiv preprint arXiv:2104.07661 (2021)
  * [32] Wu, Z., Lischinski, D., Shechtman, E.: Stylespace analysis: Disentangled controls for stylegan image generation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 12863–12872 (2021)
  * [33] Yang, G., Fei, N., Ding, M., Liu, G., Lu, Z., Xiang, T.: L2m-gan: Learning to manipulate latent space semantics for facial attribute editing. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2951–2960 (2021)
  * [34] Zhang, R., Isola, P., Efros, A.A., Shechtman, E., Wang, O.: The unreasonable effectiveness of deep features as a perceptual metric. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 586–595 (2018)
  * [35] Zhu, J., Shen, Y., Zhao, D., Zhou, B.: In-domain gan inversion for real image editing. In: European conference on computer vision. pp. 592–608. Springer (2020)
  * [36] Zhu, J.Y., Krähenbühl, P., Shechtman, E., Efros, A.A.: Generative visual manipulation on the natural image manifold. In: European conference on computer vision. pp. 597–613. Springer (2016)