# Error Estimates for Adaptive Spectral Decompositions

Daniel H. Baffet 111Department of Mathematics and Computer Science, University
of Basel, Basel, Switzerland<EMAIL_ADDRESS>Yannik G. Gleichmann
11footnotemark: 1<EMAIL_ADDRESS>Marcus J. Grote
11footnotemark: 1<EMAIL_ADDRESS>
###### Abstract

Adaptive spectral (AS) decompositions associated with a piecewise constant
function, $u$, yield small subspaces where the characteristic functions
comprising $u$ are well approximated. When combined with Newton-like
optimization methods for the solution of inverse medium problems, AS
decompositions have proved remarkably efficient in providing at each nonlinear
iteration a low-dimensional search space. Here, we derive $L^{2}$-error
estimates for the AS decomposition of $u$, truncated after $K$ terms, when $u$
is piecewise constant and consists of $K$ characteristic functions over
Lipschitz domains and a background. Our estimates apply both to the continuous
and the discrete Galerkin finite element setting. Numerical examples
illustrate the accuracy of the AS decomposition for media that either do, or
do not, satisfy the assumptions of the theory.

Keywords: Inverse medium problem, scattering problem, adaptive eigenspace
inversion, adaptive spectral decomposition, image segmentation

##  1 Introduction

Adaptive spectral (AS) decompositions have been proposed as low-dimensional
search spaces during the iterative solution of inverse medium problems [1, 2,
3, 4, 5]. For piecewise constant media, in particular, AS decompositions have
proved remarkably efficient and accurate. So far, however, their remarkable
approximation properties are only supported by numerical evidence. Here,
starting from [5], we derive $L^{2}$-error estimates for AS approximations of
piecewise constant functions.

In [1], De Buhan and Osses proposed to restrict the search space of an inverse
medium problem to the span of a small basis of eigenfunctions of a judicious
elliptic operator, repeatedly adapted during the nonlinear iteration. Their
adaptive inversion approach relies on a decomposition

$v=\sum_{k=1}^{\infty}\beta_{k}\varphi_{k},$ (1.1)

for $v\in W^{1,\infty}_{0}(\Omega)$, with $\Omega\subset\mathbb{R}^{d}$. Here
each $\varphi_{k}$ is an eigenfunction of a $v$-dependent, linear, symmetric,
and elliptic operator $L_{\varepsilon}[v]$, i.e.,

$L_{\varepsilon}[v]\varphi_{k}=\lambda_{k}\varphi_{k}\quad\text{in
$\Omega$,}\qquad\varphi_{k}=0\quad\text{on $\partial\Omega$,}$ (1.2)

for an eigenvalue $\lambda_{k}\in\mathbb{R}$. In the sequel we shall in fact
apply the AS decomposition to more general functions in $W^{1,\infty}(\Omega)$
by extending their boundary data appropriately into the interior of $\Omega$;
here, for simplicity, we suppose $v\in W^{1,\infty}_{0}(\Omega)$.

Clearly, the choice of $L_{\varepsilon}[v]$ is crucial for obtaining an
efficient approximation of $v$ with as few basis functions as possible.
Typically, we use

$L_{\varepsilon}[v]w=-\operatorname{\nabla\cdot}\left(\mu_{\varepsilon}[v]\nabla
w\right),\qquad\mu_{\varepsilon}[v](x)=\frac{1}{\sqrt{|\nabla
v(x)|^{2}+\varepsilon^{2}}}\,,$ (1.3)

where $\varepsilon>0$ is a small parameter to avoid division by zero, but
other forms have also been used in the past and are treated by our analysis.

Note that we cannot apply the above AS decomposition directly to piecewise
constant $u$, because $\mu_{\varepsilon}[u]$ is not in $L^{\infty}$ and thus
$L_{\varepsilon}[u]$ not well-defined. Nevertheless, we may still decompose
$u$ at the cost of an additional step. We first approximate $u$ by a more
regular approximation, which we denote generically by $u_{\delta}$, where
$\delta>0$ is a parameter that controls the error and is proportional to the
width of the support of $\nabla u_{\delta}$ near the jump discontinuities of
$u$. Then we may expand $u$ (or $u_{\delta}$) in the spectral basis of
$L_{\varepsilon}[u_{\delta}]$ and obtain an approximate decomposition of $u$
(or $u_{\delta}$) by truncating the expansion. Typically, $u_{\delta}$
corresponds to the standard, continuous, piecewise polynomial FE interpolant
of $u$ on a regular triangulation with mesh size $\delta=h$. Then, the
eigenfunctions $\varphi_{k}$ may correspond either to the (true continuous)
eigenfunctions of $L_{\varepsilon}[u_{\delta}]$ or to their (discrete
approximate) Galerkin FE counterparts, as our analysis encompasses both the
continuous and the discrete setting.

Insight about the AS decomposition approach may be obtained from its
connection to the total variation (TV) functional, which is commonly used for
image denoising while preserving edges. In fact, $L_{\varepsilon}[v]v$, with
$L_{\varepsilon}[v]$ given by (1.3), is the Fréchet derivative of the
penalized TV functional – see [3, Remark 1]. The eigenvalue problem for
$L_{\varepsilon}[v]$ also bears a striking resemblance to nonlinear eigenvalue
problems for the TV functional, which have been studied in the more general
context of 1-homogeneous functionals for image processing – see [6, 7, 8] and
the references therein.

The AS decomposition has been used as follows in various iterative Newton-like
algorithms for the solution of inverse medium problems [2, 3, 4]: Given an
approximation of the medium, $u^{(m-1)}$, from the previous iteration, the
approximation $u^{(m)}$ at the current iteration is set as the minimizer of
the misfit in the space $\operatorname{span}(\varphi_{k})_{k=1}^{K}$, where
$\varphi_{k}$, $k=1,\ldots,K$, satisfy (1.2) with $v=u^{(m-1)}$. As the
approximation $u^{(m)}$ changes from one iteration to the next, so does the
search space used for the subsequent minimization.

By combining the adaptive inversion process with the TRAC (time reversed
absorbing condition) approach, de Buhan and Kray [2] developed an effective
solution strategy for time-dependent inverse scattering problems. In [3],
Grote, Kray and Nahum proposed the AEI (adaptive eigenspace inversion)
algorithm for inverse scattering problems in the frequency domain. In [4], the
AEI algorithm was extended to multi-parameter inverse medium problems.
Recently, it was extended to electromagnetic inverse scattering problems at
fixed frequency [9] and also to time-dependent inverse scattering problems
when the illuminating source is unknown [10]. In [11], AS decompositions were
used for solving 2-D and 3-D seismic inverse problems for the Helmholtz
equation. First theoretical estimates for AS decompositions together with an
approach for adapting the dimension of the search space were derived in [5].

When $u$ consists of a sum of $K$ characteristic functions $\chi_{A^{k}}$ of
sets $A^{k}$, each compactly contained in $\Omega$, the expansion (1.1) in the
spectral basis of $L_{\varepsilon}[u_{\delta}]$ truncated after $K$ terms has
proved remarkably accurate, as it essentially recovers $u$ and in fact
decomposes $u$ into the characteristic functions comprising it. In [5], it is
shown that the gradients of the first $K$ eigenfunctions of
$L_{\varepsilon}[u_{\delta}]$ are small away from the discontinuities of $u$.
Thus, in regions where $u$ is constant, $\varphi_{1},\ldots,\varphi_{K}$ are
also nearly constant and we expect that in their span,
$\Phi_{K}^{\varepsilon,\delta}=\operatorname{span}\\{\varphi_{k}\\}_{k=1}^{K}$,
$u$ together with each of the characteristic functions comprising it can be
well approximated. Here, our goal is to rigorously prove this proposition,
even in the more general situation where $u$ is not necessarily constant near
the boundary $\partial\Omega$.

Starting from [5], we derive $L^{2}$ error estimates for the projection of any
$v\in u+\operatorname{span}\\{\chi_{A^{k}}\\}$ onto the appropriate affine
subspace. In our main result, given by Theorem 3.6, we prove that the
$L^{2}$-projection error of $v$ (in particular of $u$ itself) is bounded by
$\mathcal{O}(\sqrt{\varepsilon+\delta})$. Similarly, we show that any of the
$K$ characteristic functions $\chi_{A^{k}}$ is approximated by its
$L^{2}$-projection on $\Phi_{K}^{\varepsilon,\delta}$ up to
$\mathcal{O}(\sqrt{\varepsilon+\delta})$. Our analysis treats both continuous
AS formulations and their discrete Galerkin approximations. The proof requires
a technical result about the level sets of distance functions for Lipschitz
domains, which is provided in Appendix A. In Corollary 3.8, we particularize
our estimates for two standard methods for obtaining $u_{\delta}$. In
particular, our results apply when $u_{\delta}$ is a continuous, piecewise
polynomial interpolant of $u$ in a FE space $V_{h}$ with mesh size $h=\delta$,
and the eigenfunctions $\varphi_{k}$ are computed numerically by a Galerkin FE
approximation in the same subspace.

The remainder of the paper is organized as follows. In Section 2, we describe
the class of piecewise constant functions considered, provide definitions and
introduce notation. Section 3 contains the analysis and the main results of
the paper. Finally, we present in Section 4 various numerical examples which
illustrate the accuracy of the AS decomposition for functions that either do,
or do not, satisfy the assumptions of our theory. There we also illustrate the
usefulness of the AS decomposition for the solution of a standard linear
inverse problem from image deconvolution.

##  2 Notation and definitions

The adaptive spectral (AS) decomposition (1.1) of a function $v$ is based on
the spectral decomposition of the $v$-dependent elliptic operator
$L_{\varepsilon}[v]$ given by

$L_{\varepsilon}[v]w=-\operatorname{\nabla\cdot}\left(\mu_{\varepsilon}[v]\nabla
w\right).$ (2.1)

Typically, the weight function $\mu_{\varepsilon}[v]$ has the form of either

$\mu_{\varepsilon}[v](x)=\ \frac{1}{(|\nabla
v(x)|^{q}+\varepsilon^{q})^{1/q}}\,,$ (2.2)

for some $q\in[1,\infty)$, or

$\mu_{\varepsilon}[v](x)=\ \frac{1}{\max\\{|\nabla v(x)|,\,\varepsilon\\}}\,.$
(2.3)

For the analysis below, however, we allow for more general
$\mu_{\varepsilon}[v]$.

Here our goal is to study the application of AS decompositions to regular
approximations of piecewise constant functions. Indeed, for a piecewise
constant function $u$, $\mu_{\varepsilon}[u]$ is not in $L^{\infty}$, and so
$L_{\varepsilon}[u]$ is not well defined. Nevertheless, we may still decompose
$u$ at the cost of an additional step. We first approximate $u$ by a more
regular approximation, which we denote generically by $u_{\delta}$, where
$\delta$ is a parameter that controls the error and is proportional to the
width of the support of $\nabla u_{\delta}$ near the jump discontinuities of
$u$. Then we may expand $u$ (or $u_{\delta}$) in the spectral basis of
$L_{\varepsilon}[u_{\delta}]$, be it finite- or infinite-dimensional, and
obtain an approximation by truncating the expansion. One important example of
a method for obtaining $u_{\delta}$ is the standard, continuous, piecewise
polynomial interpolant of $u$ in an $H^{1}$-conforming finite element (FE)
space with underlying mesh size $\delta=h$.

To include FE approximations in the analysis, we formulate boundary value
problems in closed subspaces $\mathcal{V}^{\delta}\subset H^{1}(\Omega)$ and
$\mathcal{V}^{\delta}_{0}=\mathcal{V}^{\delta}\cap H^{1}_{0}(\Omega)$. Hence,
in the continuous setting $\mathcal{V}^{\delta}=H^{1}(\Omega)$, independently
of $\delta$, whereas in the discrete FE setting
$\mathcal{V}^{\delta}\subsetneq H^{1}(\Omega)$ corresponds to the finite-
dimensional FE space with underlying mesh size $\delta=h$. As a consequence,
all our results below are valid both for the continuous and the discrete
setting and, in particular, for $H^{1}$-conforming FE approximations. We let
$\left\langle\cdot,\cdot\right\rangle$ and $\|\cdot\|_{L^{2}(\Omega)}$ denote
the standard inner product and norm of $L^{2}(\Omega)$, and $|\cdot|$ denote
the $\ell^{2}$-norm. We use $C$, $C_{1},C_{2}$, etc. to denote generic
constants which may depend on $u$, but are independent of $\delta$ and
$\varepsilon$; their values may also vary depending on the context. We
sometimes use the term “medium” to refer to functions on the domain of
interest $\Omega\subset\mathbb{R}^{d}$.

In the remainder of this section, we introduce notation, assumptions and
definitions needed for our approximation theory in Section 3. Section 2.1
precisely defines the class of piecewise constant functions $u$ to be
decomposed. In Section 2.2, we introduce admissible approximation methods for
obtaining $u_{\delta}$ and provide examples of two standard methods which are
admissible. In Section 2.3, we state our assumptions on the medium-dependent
weight function $\mu_{\varepsilon}[\cdot]$, and in Section 2.4 we state the
boundary-value problems defining the spectral basis of
$L_{\varepsilon}[u_{\delta}]$ and the $L_{\varepsilon}[u_{\delta}]$-lifting,
$\varphi_{0}$, of the boundary data of $u_{\delta}$ into $\Omega$.

Figure 1: Typical configuration in two dimensions. In this example $K=3$ and
$M=4$. The frame on the left shows the sets $A^{1}$, $A^{2}$ and $A^{3}$, and
the frame on the right shows $B^{1}=A^{1}$, $B^{2}=A^{2}\setminus A^{3}$, and
$B^{3}=A^{3}$.

###  2.1 Piecewise constant medium

Consider $u:\Omega\to\mathbb{R}$ piecewise constant, where
$\Omega\subset\mathbb{R}^{d}$, with $d\geq 2$, is a bounded Lipschitz domain.
We assume $u$ has the form

$u(x)=u^{0}(x)+\widetilde{u}(x),\qquad x\in\Omega,$ (2.4)

where the background $u^{0}$ and the interior inclusions $\widetilde{u}$ are
given by

$u^{0}=\sum_{m=1}^{M}\omega_{m}\chi_{\Omega^{m}}\,,\quad\omega_{m}\in\mathbb{R},\qquad\widetilde{u}=\sum_{k=1}^{K}\alpha_{k}\chi_{A^{k}}\,,\quad\alpha_{k}\in\mathbb{R}\setminus\\{0\\},$
(2.5)

with $\chi_{A}$ denoting the characteristic function of a set
$A\subset\mathbb{R}^{d}$. In the decomposition (2.4) we distinguish the sets
$\Omega^{m}$ connected to the boundary $\partial\Omega$ from those that are
not. We suppose the sets $\Omega^{1},\ldots,\Omega^{M}$ characterizing the
background $u^{0}$ are disjoint Lipschitz domains covering $\Omega$,

$\overline{\Omega}=\bigcup_{m=1}^{M}\overline{\Omega^{m}},$

and for each $m$, $\partial\Omega^{m}\cap\partial\Omega$ is open in (the
relative topology of) $\partial\Omega$, i.e,

$\Omega^{m}=\Omega\cap\widetilde{\Omega}^{m},\qquad\partial\Omega\cap\widetilde{\Omega}^{m}\neq\emptyset,$

for some bounded disjoint Lipschitz domain
$\widetilde{\Omega}^{m}\subset\mathbb{R}^{d}$. Moreover, we suppose
$A^{1},\ldots,A^{K}$ are Lipschitz domains with mutually disjoint boundaries
such that for each $k$, the boundary $\partial A^{k}$ of $A^{k}$ is connected,
and $A^{k}\subset\subset\Omega^{m}$ for some $m=1,\ldots,M$. Hence $\Omega$ is
partitioned into finitely many subdomains $\Omega^{m}$ adjacent to its
boundary $\partial\Omega$, while each $\Omega^{m}$ may contain one or several
inclusions $A^{k}$ isolated from $\partial\Omega$; Figure 1 illustrates a
possible configuration in two dimensions.

Note that $u$ given by (2.4) is defined only a.e. in $\Omega$. This will be
significant only in Section 2.2, where we discuss admissible approximations of
$u$; in the rest of the paper this will not cause ambiguity since there we
always consider $u$ as an element of $L^{2}(\Omega)$.

###  2.2 Admissible approximation

To employ the estimates derived in [5], we assume $u_{\delta}$ is obtained by
an _admissible_ method, i.e., by a method satisfying the following.

######  Definition 2.1.

Consider a family of transformations
$\mathcal{I}_{\delta}:L^{2}(\Omega)\to\mathcal{V}^{\delta}\subset
H^{1}(\Omega)$, with $\delta>0$ in some set of indices. We say that
$\\{\mathcal{I}_{\delta}\\}_{\delta}$ is an _admissible method_ , if for every
Lipschitz domain $A\subset\Omega$, the following conditions are satisfied:

  1. 1.

$\lim_{\delta\to
0}\|\mathcal{I}_{\delta}\chi_{A}-\chi_{A}\|_{L^{2}(\Omega)}=0.$ (2.6)

  2. 2.

$\nabla(\mathcal{I}_{\delta}\chi_{A})\in
L^{\infty}(\Omega),\quad\operatorname{supp}\\!\big{(}\nabla(\mathcal{I}_{\delta}\chi_{A})\big{)}\subset\overline{U_{\delta}},$
(2.7)

where

$U_{\delta}=\big{\\{}x\in\Omega\,|\
\operatorname{dist}(x,\partial\Omega^{m}\cap\Omega)<\delta\big{\\}},$

with $\operatorname{dist}(x,W)$ denoting the distance of $x\in\mathbb{R}^{d}$
to the set $W\subset\mathbb{R}^{d}$.

  3. 3.

There exists a constant $C$, such that for every $\delta>0$ sufficiently
small,

$\delta\|\nabla\mathcal{I}_{\delta}\chi_{A}\|_{L^{\infty}(\Omega)}\ \leq\ C.$
(2.8)

  4. 4.

If $\Gamma\subset\partial\Omega\setminus\partial U_{\delta}$ with positive
$(d-1)$-dimensional Hausdorff measure, $\mathcal{H}^{d-1}(\Gamma)>0$, then the
trace of $\chi_{A}$ on $\Gamma$ coincides with that of
$\mathcal{I}_{\delta}\chi_{A}$.

Hence, for convenience, we shall say that $u_{\delta}$ obtained by an
admissible method is an admissible approximation of $u$. By Definition 2.1, we
have

$u_{\delta}\ =\ u^{0}_{\delta}+\widetilde{u}_{\delta},\qquad
u^{0}_{\delta}=\mathcal{I}_{\delta}u^{0}\in\mathcal{V}^{\delta},\quad\widetilde{u}_{\delta}=\mathcal{I}_{\delta}\widetilde{u}\in\mathcal{V}^{\delta}_{0}.$
(2.9)

In addition, by (2.7), we have $\nabla u_{\delta}=0$ in the open complement

$D_{\delta}=\Omega\setminus\overline{\mathcal{M}_{\delta}},$ (2.10)

of the $\delta$-wide neighborhood $\mathcal{M}_{\delta}$ of all interfaces,

$\mathcal{M}_{\delta}=\bigcup_{k=1}^{K}\big{\\{}x\in\Omega:\
\operatorname{dist}(x,\partial
A^{k})<\delta\big{\\}}\cup\bigcup_{m=1}^{M}\big{\\{}x\in\Omega:\
\operatorname{dist}(x,\partial\Omega^{m}\cap\Omega)<\delta\big{\\}}.$ (2.11)

By (2.8), there exists a constant $C$ (which depends on $u$), such that for
every $\delta>0$ sufficiently small, $u_{\delta}$ satisfies

$\delta\|\nabla u_{\delta}\|_{L^{\infty}(\Omega)}\leq C.$ (2.12)

Next we provide two examples [5, Corollary 6] of standard methods which are
admissible.

Figure 2: The continuous, piecewise linear ${P}^{1}$-FE interpolant $u_{h}$ of
the characteristic function $u$ for a disk.

######  Proposition 2.2.

Let $u$ be extended to $\overline{\Omega}$ either by assigning to $u$ at any
$x$ on the interfaces in $\overline{\Omega}$ one of its values in a
neighboring domain $A^{k}$ or $\Omega^{m}$, or by replacing $A^{k}$ and
$\Omega^{m}$ in (2.5) by $\overline{A^{k}}$ and $\overline{\Omega^{m}}$. For
$h>0$, let $V_{h}$ denote an $H^{1}$-conforming $\mathcal{P}^{r}$-FE space
associated with a simplicial mesh $\mathcal{T}_{h}$ with mesh size $h$. If the
family of meshes $\\{\mathcal{T}_{h}\\}_{h}$ is regular and quasi-uniform
(see, e.g., [12]), then the FE-interpolant $u_{h}$ of $u$ in $V_{h}$ is
admissible.

###### Proof.

To prove the proposition, we have to verify the conditions of Definition 2.1.
Most of the conditions, i.e., linearity, and conditions 1,2 and 4 are clearly
satisfied. The only condition which requires careful attention is 3, i.e.,
(2.8). The argument of the proof is similar to that of standard inverse
inequalities.

Let $u_{h}$ be the FE-interpolant of the characteristic function $u=\chi_{A}$
of some set $A\subset\Omega$. In every element
$\mathcal{K}\in\mathcal{T}_{h}$, $u_{h}$ is the unique polynomial in
$\mathcal{P}^{r}$ which interpolates the values of $u$ ($0$ or $1$) at the
nodes of $\mathcal{K}$. By transforming $\mathcal{K}$ to the (mesh
independent) reference element $\hat{\mathcal{K}}$, we have

$\nabla u_{h}(x)=J_{\mathcal{K}}^{-T}\nabla
P_{\mathcal{K}}(F_{\mathcal{K}}^{-1}(x))\qquad x\in\mathcal{K},$

where $F_{\mathcal{K}}^{-1}:\mathcal{K}\to\hat{\mathcal{K}}$ is the inverse of
the affine mapping $F_{\mathcal{K}}$ which transforms $\hat{\mathcal{K}}$ to
$\mathcal{K}$, $J_{\mathcal{K}}\in\mathbb{R}^{d\times d}$ is the Jacobian
matrix of $F_{\mathcal{K}}$ and $P_{\mathcal{K}}\in\mathcal{P}^{r}$ is a
polynomial taking values of either $0$ or $1$ at the nodes of
$\hat{\mathcal{K}}$. Since there is only a finite number of polynomials in
$\mathcal{P}^{r}$ whose image on the nodes of $\hat{\mathcal{K}}$ is a subset
of $\\{0,1\\}$, we can estimate all their gradients in $\hat{\mathcal{K}}$ by
a single constant independently of the element $\mathcal{K}$ and mesh size
$h$. In addition, by [12, Lemma 4.3] and the assumption that the family of
meshes $\\{\mathcal{T}_{h}\\}$ is regular and quasi-uniform, we have
$\big{|}J_{\mathcal{K}}^{-1}\big{|}\leq Ch^{-1}$, where $|\cdot|$ denotes the
matrix norm induced on $\mathbb{R}^{d\times d}$ by the $\ell^{2}$ norm of
$\mathbb{R}^{d}$. Note that while Lemma 4.3 in [12] is stated and proved in
2-D, its proof extends easily to any dimension. Hence we obtain (2.8) with
$\delta=h$ which yields that interpolation in $V_{h}$ is an admissible
approximation. ∎

The main effort in the proof of Proposition 2.2 is to show (2.8) with
$u=\chi_{A}$ a characteristic function. Figure 2 illustrates this situation
for the standard interpolant $u_{h}$ in a $\mathcal{P}^{1}$-FE space of the
characteristic function $u$ for a disk $A$. The right frame shows a part of
the mesh where the solid black line marks the discontinuity of $u$ along
$\partial A$. Outside the dark gray elements, $u$ is constant and therefore so
is $u_{h}$. In particular, $\nabla u_{h}=0$ outside the neighborhood of width
$\delta=h$ (light gray) around $\partial A$.

######  Proposition 2.3.

If $u$ is extended to a.e. $x\in\mathbb{R}^{d}$ by

$u=\sum_{m=1}^{M}\omega_{m}\chi_{\widetilde{\Omega}^{m}}+\sum_{k=1}^{K}\alpha_{k}\chi_{A^{k}}$
(2.13)

(compare with (2.4), (2.5)), and $u_{\delta}$ is the convolution

$u_{\delta}(x)=\zeta_{\delta}*u=\int_{\mathbb{R}^{d}}\zeta_{\delta}(x-y)u(y)\,dy,\qquad\zeta_{\delta}(x)=\delta^{-d}\zeta(x/\delta)$
(2.14)

with $\zeta$ a standard mollifier (e.g., [13]), then $u_{\delta}$ is
admissible.

###### Proof.

See Corollary 6 of [5]. ∎

For the analysis below it is convenient to partition $D_{\delta}$, given by
(2.10), into its connected components. Hence, we let the sets
$A^{1},\ldots,A^{K}$ be indexed so that if $i>k$, then either $A^{i}\subset
A^{k}$ or $A^{i}\cap A^{k}=\emptyset$, and let $B^{k}_{\delta}$ be the
connected components of $D_{\delta}$,

$B^{k}_{\delta}=B^{k}\cap D_{\delta},\qquad
B^{k}=A^{k}\setminus\bigcup_{i>k}\overline{A^{i}},\qquad k=1,\ldots,K;$ (2.15)

see Figure 1. Similarly, we define outside the inclusions

$E^{m}_{\delta}=E^{m}\cap D_{\delta},\qquad
E^{m}=\Omega^{m}\setminus\bigcup_{k=1}^{K}\overline{A^{k}},\qquad
m=1,\ldots,M.$ (2.16)

Here, we assume $\delta>0$ sufficiently small so that $B^{k}_{\delta}$ and
$E^{m}_{\delta}$ are indeed connected and that the $(d-1)$-dimensional
Hausdorff measure of $\partial E^{m}_{\delta}\cap\partial\Omega$ is positive.
Thus, for each $k$ and $\delta>0$ small, $B^{k}$ and $B^{k}_{\delta}$ are open
and connected, and $D_{\delta}$ is given by the disjoint union

$D_{\delta}=E_{\delta}\cup\bigcup_{k=1}^{K}B^{k}_{\delta},$

where $E_{\delta}$ denotes the “$\delta$-exterior”,

$E_{\delta}=\bigcup_{m=1}^{M}E^{m}_{\delta}.$ (2.17)

Now we may deduce from condition 4 of Definition 2.1 that

$u=u_{\delta}=u^{0}_{\delta},\qquad\widetilde{u}=\widetilde{u}_{\delta}=0\qquad\text{a.e.\
in $E_{\delta}$.}$ (2.18)

Since we have a finite number of Lipschitz domains, $B^{k}$ ($k=1,\ldots,K$)
and $E^{m}$ ($m=1,\ldots,M$), we may find a single constant $\Lambda>0$
sufficiently large so that each of the sets, near its boundary, locally
coincides with the epigraph of a $\Lambda$-Lipschitz function. While the
optimal Lipschitz constant for a domain may depend on the scale of the open
sets used for covering its boundary, when reducing the scale, the optimal
constant cannot increase. Therefore, if for some scale the Lipschitz constant
$\Lambda$ is suitable for a domain, for simplicity, we shall say that it is a
$\Lambda$-Lipschitz domain.

By Theorem A.1, for every sufficiently small $\delta$, each $B^{k}_{\delta}$
is also a $\Lambda$-Lipschitz domain. Note, however, that since a portion of
the boundary of $E^{m}_{\delta}$ coincides with the boundary of $E^{m}$ for
every $\delta$, it does not have the form assumed in Theorem A.1. As a result,
we cannot rely on the same theorem to deduce that $E^{m}_{\delta}$ is a
$\Lambda$-Lipschitz domain. Nevertheless, outside a neighborhood of
$\partial\Omega\cap\partial E^{m}$, the boundary of $E^{m}_{\delta}$ is a
$\Lambda$-Lipschitz surface with $E^{m}_{\delta}$ lying to one of its sides,
by Theorem A.6. It is therefore possible to modify the definition of
$\mathcal{M}_{\delta}$ so that for every $\delta$ sufficiently small,
$E^{m}_{\delta}$ given by (2.16), is a $\widetilde{\Lambda}$-Lipschitz domain,
for some $\widetilde{\Lambda}$ independent of $\delta$. Here, for simplicity,
we assume the latter to be true and denote the uniform constant
$\max(\Lambda,\widetilde{\Lambda})$ again by $\Lambda$.

###  2.3 Medium dependent weight function

For $\varepsilon>0$ and $v\in H^{1}(\Omega)$, with $\nabla v\in
L^{\infty}(\Omega)$, we assume the $v$-dependent weight function
$\mu_{\varepsilon}[v]$ has the form

$\mu_{\varepsilon}[v](x)=\hat{\mu}_{\varepsilon}(|\nabla v(x)|),\qquad
x\in\Omega,$ (2.19)

where $\hat{\mu}_{\varepsilon}:[0,\infty)\to\mathbb{R}$ is a non-increasing
function that satisfies

$\hat{\mu}_{\varepsilon}(0)=\varepsilon^{-1},\qquad
0<\hat{\mu}_{\varepsilon}(t),\quad t\hat{\mu}_{\varepsilon}(t)\leq 1,\quad
t\geq 0,$ (2.20)

and

$\exists C>0$, s.t. for every sufficiently large $t$, $C\leq
t\hat{\mu}_{\varepsilon}(t)$. (2.21)

In particular, for
$\hat{\mu}_{\varepsilon}(t)=1/(t^{q}+\varepsilon^{q})^{1/q}$ and
$\hat{\mu}_{\varepsilon}(t)=1/\max(t,\varepsilon)$, as in (2.2) and (2.3),
respectively, (2.20)-(2.21) hold for any $C<1$. From (2.20), we immediately
conclude that

$\mu_{\varepsilon}[v](x)|\nabla v(x)|\leq 1,\qquad\text{a.e. $x\in\Omega$,}$
(2.22)

and

$0<\hat{\mu}_{\varepsilon}(\|\nabla
v\|_{L^{\infty}(\Omega)})\leq\mu_{\varepsilon}[v](x)\qquad\text{a.e.
$x\in\Omega$.}$ (2.23)

###  2.4 Boundary value problems

Let $\mathcal{V}^{\delta}$ be a closed subspace of $H^{1}(\Omega)$, possibly
equal to $H^{1}(\Omega)$, and
$\mathcal{V}^{\delta}_{0}=\mathcal{V}^{\delta}\cap H^{1}_{0}(\Omega)$. For
sufficiently small and fixed $\delta,\varepsilon>0$, the operator
$L_{\varepsilon}[u_{\delta}]$ in (2.1) is uniformly elliptic in $\Omega$ [5].
Thus, it admits in $\mathcal{V}^{\delta}_{0}$ a (possibly finite) non-
decreasing sequence $\\{\lambda_{k}\\}_{k\geq 1}$ of positive eigenvalues with
each repeated according to its multiplicity with corresponding eigenfunctions
$\\{\varphi_{k}\\}_{k\geq 1}$ which form an $L^{2}$-orthonormal basis of
$\mathcal{V}^{\delta}_{0}$. In addition, we denote by
$\varphi_{0}\in\mathcal{V}^{\delta}$ the $L_{\varepsilon}[u_{\delta}]$-lifting
of the boundary data of $u_{\delta}$ into $\Omega$. More precisely, we let
$\varphi_{0}\in\mathcal{V}^{\delta}$ satisfy

$L_{\varepsilon}[u_{\delta}]\varphi_{0}=0\quad\text{in
$\Omega$,}\qquad\varphi_{0}=u_{\delta}\quad\text{on $\partial\Omega$}$ (2.24)

in $\mathcal{V}^{\delta}_{0}$, and for $k\geq 1$ we let
$\varphi_{k}\in\mathcal{V}^{\delta}_{0}$, $\varphi_{k}\neq 0$ satisfy

$L_{\varepsilon}[u_{\delta}]\varphi_{k}=\lambda_{k}\varphi_{k}\quad\text{in
$\Omega$,}\qquad\varphi_{k}=0\quad\text{on $\partial\Omega$,}$ (2.25)

in $\mathcal{V}^{\delta}_{0}$. Clearly both (2.24) and (2.25) should be
understood in a weak sense with respect to the bilinear form

$B_{\varepsilon,\delta}[w,v]=\left\langle\mu_{\varepsilon}[u_{\delta}]\nabla
w,\nabla v\right\rangle.$ (2.26)

For instance, if $\mathcal{V}^{\delta}$ is a (finite-dimensional,
$H^{1}$-conforming) FE space, the eigenvalue problem (2.25) is understood as
the Galerkin FE formulation: find $\varphi_{k}\in\mathcal{V}_{0}^{\delta}$ and
$\lambda_{k}\in\mathbb{R}$ such that

$B_{\varepsilon,\delta}[\varphi_{k},\varphi]=\lambda_{k}\left\langle\varphi_{k},\varphi\right\rangle\qquad\forall\,\varphi\in\mathcal{V}_{0}^{\delta}.$
(2.27)

Thus, the framework above treats both continuous and discrete formulations.

######  Remark 2.4.

Note that $\varphi_{k}$ ($k\geq 0$) and $\lambda_{k}$ ($k\geq 1$) always
depend on $\varepsilon$ and $u_{\delta}$, and thus on $u$ and $\delta$,
regardless of any particular finite- or infinite-dimensional choice for
$\mathcal{V}^{\delta}$. For simplicity of notation, we do not indicate this
dependency explicitly.

##  3 Error estimates

Given a piecewise constant $u$, we shall now derive our estimates for the AS
decomposition of $u_{\delta}$ based on the assumptions and definitions
introduced in Section 2. Since $u_{\delta}$ is an admissible approximation of
$u$, as defined in Section 2.2, for every $\varepsilon>0$ and every
sufficiently small $\delta>0$, we have [5]

$B_{\varepsilon,\delta}[v,v]\leq C,\qquad
v\in\left\\{u_{\delta},\,u^{0}_{\delta},\,\widetilde{u}_{\delta},\,\varphi_{0},\ldots,\,\varphi_{K}\right\\}.$
(3.1)

Here, and in the rest of the paper, the constants $C,C_{1},C_{2},\ldots$ may
depend on $u$ (i.e., on its values and on the sets $B^{k}$ and $\Omega^{m}$),
but not on $\varepsilon,\delta$. As a consequence of (3.1), the gradients of
$\varphi_{k}$, with $k=0,\ldots,K$, are small in $D_{\delta}$ [5, Theorem 5].
Heuristically, this implies that each $\varphi_{k}$ is almost constant in
regions where $u$ is constant and thus we expect that $u$ be well approximated
in $\varphi_{0}+\Phi_{K}^{\varepsilon,\delta}$, where

$\Phi_{K}^{\varepsilon,\delta}=\operatorname{span}\\{\varphi_{k}\\}_{k=1}^{K}.$
(3.2)

Here, our goal is to rigorously prove this proposition.

More precisely, let $\Pi_{K}^{\varepsilon}[u_{\delta}]$ denote the standard
orthogonal projection on $\Phi_{K}^{\varepsilon,\delta}$:

$\Pi_{K}^{\varepsilon}[u_{\delta}]:L^{2}(\Omega)\to\Phi_{K}^{\varepsilon,\delta},\qquad\left\langle
v-\Pi_{K}^{\varepsilon}[u_{\delta}]v,\varphi\right\rangle=0,\quad\forall\,\varphi\in\Phi_{K}^{\varepsilon,\delta},$
(3.3)

and let $X_{K}$ be given by

$X_{K}=\operatorname{span}\\{\chi_{A^{k}}\\}_{k=1}^{K}=\operatorname{span}\\{\chi_{B^{k}}\\}_{k=1}^{K}.$
(3.4)

We shall show that every function $v\in u+X_{K}$ is well approximated in
$\varphi_{0}+\Phi_{K}^{\varepsilon,\delta}$ by its $L^{2}$-orthogonal
projection

$Q_{K}^{\varepsilon}[u_{\delta}](v)=\varphi_{0}+\Pi_{K}^{\varepsilon}[u_{\delta}](v-\varphi_{0}).$
(3.5)

Similarly, we shall show that every $v\in X_{K}$ is well approximated by its
orthogonal projection $\Pi_{K}^{\varepsilon}[u_{\delta}]v$ on
$\Phi_{K}^{\varepsilon,\delta}$. The main result, given by Theorem 3.6,
provides estimates of the $L^{2}$ errors in terms of $\varepsilon$ and
$\delta$.

###  3.1 Preliminary results

From (2.23) with $v=u_{\delta}$, the monotonicity of $\hat{\mu}$, (2.12) and
(2.21) we get

$0<C\delta\leq\mu_{\varepsilon}[u_{\delta}](x)\qquad\text{a.e.\ $x\in\Omega$}$
(3.6)

for every sufficiently small $\delta$, where the constant $C$ may depend on
$u$, but is independent of $\delta$ and $\varepsilon$. Since $\nabla
u_{\delta}$ vanishes in $D_{\delta}$ by (2.7), assumptions (2.19) and (2.20)
on $\hat{\mu}_{\varepsilon}$ yield

$\mu_{\varepsilon}[u_{\delta}](x)=\varepsilon^{-1}\qquad\text{a.e.\ $x\in
D_{\delta}$.}$ (3.7)

Together with the definition of $B_{\varepsilon,\delta}[\cdot,\cdot]$ in
(2.26), and (3.6) we obtain

$\varepsilon^{-1}\|\nabla v\|_{L^{2}(D_{\delta})}^{2}+C_{1}\delta\|\nabla
v\|_{L^{2}(\mathcal{M}_{\delta})}^{2}\leq B_{\varepsilon,\delta}[v,v]$ (3.8)

for every $\delta>0$ sufficiently small and every $v\in H^{1}(\Omega)$. By
substituting $v=\varphi_{k}$ in the above and using (3.1) we get

$\varepsilon^{-1}\|\nabla\varphi_{k}\|_{L^{2}(D_{\delta})}^{2}+C_{1}\delta\|\nabla\varphi_{k}\|_{L^{2}(\mathcal{M}_{\delta})}^{2}\leq
B_{\varepsilon,\delta}[\varphi_{k},\varphi_{k}]\leq C.$ (3.9)

Next we employ (3.9) and Poincaré-type inequalities to obtain $L^{2}$
estimates for $\varphi_{k}$ in $D_{\delta}$. To do that we require
inequalities with constants independent of $\delta$ for the connected
components of $D_{\delta}$. We use Theorems 1 and 2 of [14] which yield the
following: Let $p\geq 1$ and $\Lambda>0$. There exists a constant $C>0$ such
that for every $\Lambda$-Lipschitz domain $W\subset\Omega$ and $v\in
W^{1,p}(W)$,

$\|v-\langle v\rangle_{W}\|_{L^{p}(W)}\leq C\|\nabla
v\|_{L^{p}(W)},\qquad\forall v\in W^{1,p}(W),$ (3.10)

where $\langle f\rangle_{W}$ denotes the average of $f$ over $W$,

$\langle f\rangle_{W}=\frac{1}{\mathcal{L}(W)}\int_{W}f(x)dx,$ (3.11)

with $\mathcal{L}(W)$ the Lebesgue measure of $W$. Moreover, if
$\Gamma\subset\overline{\Omega}$ has positive $(d-1)$-dimensional Hausdorff
measure, then for every $\Lambda$-Lipschitz domain $W\subset\Omega$, with
$\Gamma\subset\partial W$, and $v\in W^{1,p}(W)$ satisfying $v=0$ on $\Gamma$,

$\|v\|_{L^{p}(W)}\leq C\|\nabla v\|_{L^{p}(W)}.$ (3.12)

######  Corollary 3.1.

There exists a constant $C>0$ such that for every $\varepsilon>0$, $\delta>0$
sufficiently small and $1\leq j\leq K$,

$\|\varphi_{0}-u^{0}\|_{L^{2}(E_{\delta})}^{2}\leq
C\varepsilon,\qquad\|\varphi_{0}-\langle\varphi_{0}\rangle_{B^{j}_{\delta}}\|_{L^{2}(B^{j}_{\delta})}^{2}\leq
C\varepsilon$ (3.13)

and

$\|\varphi_{k}\|_{L^{2}(E_{\delta})}^{2}\leq
C\varepsilon,\qquad\|\varphi_{k}-\langle\varphi_{k}\rangle_{B^{j}_{\delta}}\|_{L^{2}(B^{j}_{\delta})}^{2}\leq
C\varepsilon,\qquad k=1,\ldots,K.$ (3.14)

###### Proof.

We show (3.13); the proof of (3.14) is similar. Fix $1\leq m\leq M$. Then, for
every sufficiently small $\delta$, we have $\eta=\varphi_{0}-u^{0}\in
H^{1}(E^{m}_{\delta})$ with $\eta=0$ on

$\Gamma^{m}=\partial\Omega\cap\partial E^{m}_{\delta},$

by (2.18). As $\Gamma^{m}$ contains an open set in the topology of
$\partial\Omega$, its $(d-1)$-dimensional Hausdorff measure is positive. Since
$E^{m}_{\delta}$ is $\Lambda$-Lipschitz, with $\Lambda$ independent of
$\delta$, by Poincaré (3.12), there exists $C_{1}>0$ such that

$\|\eta\|_{L^{2}(E^{m}_{\delta})}\leq
C_{1}\|\nabla\eta\|_{L^{2}(E^{m}_{\delta})}.$ (3.15)

Now, we use the above combined with (3.9) and $\nabla u^{0}=0$ in
$E^{m}_{\delta}$, to obtain

$\|\varphi_{0}-u^{0}\|_{L^{2}(E^{m}_{\delta})}=\|\eta\|_{L^{2}(E^{m}_{\delta})}\leq
C_{1}\|\nabla\varphi_{0}\|_{L^{2}(E^{m}_{\delta})}\leq
C_{2}\sqrt{\varepsilon},$ (3.16)

which proves the first estimate in (3.13), since $E_{\delta}$ is the disjoint
(finite) union of $E^{m}_{\delta}$. The proof of the second estimate in (3.13)
is similar, but relies on (3.10) instead of (3.12); therefore, it is omitted
here. ∎

While Corollary 3.1 provides $L^{2}$ estimates for $\varphi_{k}$ in the
connected components of $D_{\delta}$, the following lemma provides $L^{2}$
estimates in the neighborhood $\mathcal{M}_{\delta}$ of the discontinuities of
$u$. Especially, it yields that the contribution over $\mathcal{M}_{\delta}$
to the norm of $\varphi_{k}$ is small. Note that to deduce this conclusion it
is not enough to observe that the volume of $\mathcal{M}_{\delta}$ is small,
since the functions $\varphi_{k}$ themselves depend on $\delta$.

######  Lemma 3.2.

There exists a positive constant $C$ such that for every sufficiently small
$\varepsilon,\delta>0$,

$\displaystyle\|\varphi_{0}-u^{0}\|_{L^{2}(\mathcal{M}_{\delta})}^{2}$
$\displaystyle\leq C\delta$ (3.17)
$\displaystyle\|\varphi_{k}\|_{L^{2}(\mathcal{M}_{\delta})}^{2}$
$\displaystyle\leq C\delta\qquad k=1,\ldots,K.$ (3.18)

###### Proof.

Here we show only (3.18). We include estimate (3.17) here only for brevity;
its proof is similar, though it requires Lemma 3.5. Thus, the correct order of
our argument is (3.18), Lemma 3.3, Theorem 3.4, Lemma 3.5, and then (3.17).
Note that by (3.17) we have that $\varphi_{0}$ also satisfies (3.18).

Fix $1\leq k\leq K$, let $W=B^{j}$ for some $j=1,\ldots,K$ or $W=\Omega^{m}$
for some $m=1,\ldots,M$, and let

$U_{\delta}=\left\\{x\in W:\ \operatorname{dist}(x,\partial
W)<\delta\right\\}.$ (3.19)

By Theorem B.1 we have

$\|\varphi_{k}\|_{L^{2}(U_{\delta})}^{2}\leq
C\left(\delta^{2}\|\nabla\varphi_{k}\|_{L^{2}(U_{\delta})}^{2}+\delta\|\varphi_{k}\|_{H^{1}(D_{\delta})}^{2}\right).$
(3.20)

By using $\|\varphi_{k}\|_{L^{2}(\Omega)}=1$ and (3.9), we estimate the right
hand side of (3.20) and thus for $\delta,\varepsilon$ sufficiently small
obtain

$\|\varphi_{k}\|_{L^{2}(U_{\delta})}^{2}\leq
C_{1}\delta\left(1+\varepsilon\right)\leq C\delta.$ (3.21)

Since $\mathcal{M}_{\delta}$ is a subset of the finite union of all
$\overline{U_{\delta}}$, we obtain (3.18) which completes the proof. ∎

Following Corollary 3.1 and Lemma 3.2 we know that
$\varphi_{1},\ldots,\varphi_{K}$ are approximately piecewise constant, and
that the contributions over $\mathcal{M}_{\delta}$ to their $L^{2}$-norms are
small. This implies that each $\varphi_{k}$ is close to some function in
$X_{K}$. As we shall see in Theorem 3.6, the converse is also true; i.e.,
every function in $X_{K}$ can be well approximated in
$\Phi_{K}^{\varepsilon,\delta}$. Here – because in each $B^{k}_{\delta}$,
$\varphi_{1},\ldots,\varphi_{K}$ are close to their averages – this
proposition reduces to the invertibility of the matrix of the averages
$\langle\varphi_{j}\rangle_{B^{k}_{\delta}}$.

######  Lemma 3.3.

Let the matrix $\Sigma\in\mathbb{R}^{K\times K}$ be given by

$\Sigma=(\sigma_{kj}),\qquad\sigma_{kj}=\langle\varphi_{j}\rangle_{B^{k}_{\delta}},\quad
k,j=1,\ldots,K.$ (3.22)

There exist constants $0<C_{1}\leq C_{2}$ such that for every sufficiently
small $\delta$ and $\varepsilon$,

$C_{1}|\beta|\leq|\Sigma\beta|\leq C_{2}|\beta|,\qquad\beta\in\mathbb{R}^{K}.$
(3.23)

###### Proof.

Since the upper estimate in (3.23) is simple, here we only show the lower
estimate $C_{1}|\beta|\leq|\Sigma\beta|$, for some positive constant $C_{1}$
independent of $\beta$, $\varepsilon$, and $\delta$. Let
$\beta\in\mathbb{R}^{K}$ with $|\beta|=1$ and
$\varphi\in\Phi_{K}^{\varepsilon,\delta}$ be given by

$\varphi=\sum_{j=1}^{K}\beta_{j}\varphi_{j}.$ (3.24)

Then, we have

$(\Sigma\beta)_{k}=\langle\varphi\rangle_{B^{k}_{\delta}},\qquad
k=1,\ldots,K,$ (3.25)

where $(\Sigma\beta)_{k}$ denotes the $k$-th entry of $\Sigma\beta$. Since
$\varphi_{1},\ldots,\varphi_{K}$ are orthonormal and $|\beta|=1$, we get

$1=\|\varphi\|_{L^{2}(\Omega)}^{2}=\|\varphi\|_{L^{2}(E_{\delta})}^{2}+\|\varphi\|_{L^{2}(\mathcal{M}_{\delta})}^{2}+\sum_{k=1}^{K}\|\varphi\|_{L^{2}(B^{k}_{\delta})}^{2}.$
(3.26)

Due to (3.25), the function $\varphi-(\Sigma\beta)_{k}$ has zero average over
$B^{k}_{\delta}$ and is, therefore, orthogonal to the constant in
$L^{2}(B^{k}_{\delta})$. Thus,

$\|\varphi\|_{L^{2}(B^{k}_{\delta})}^{2}=\|\varphi-(\Sigma\beta)_{k}\|_{L^{2}(B^{k}_{\delta})}^{2}+\mathcal{L}(B^{k}_{\delta})(\Sigma\beta)_{k}^{2},\qquad
k=1,\ldots,K.$ (3.27)

By Poincaré’s inequality (3.10),

$\|\varphi-(\Sigma\beta)_{k}\|_{L^{2}(B^{k}_{\delta})}^{2}\leq
C\|\nabla\varphi\|_{L^{2}(B^{k}_{\delta})}^{2}$ (3.28)

and by the triangle inequality and (3.9), we have

$\|\nabla\varphi\|_{L^{2}(B^{k}_{\delta})}\leq\sum_{j=1}^{K}|\beta_{j}|\|\nabla\varphi_{j}\|_{L^{2}(B^{k}_{\delta})}\leq
C\sqrt{\varepsilon}.$ (3.29)

We further estimate $\|\varphi\|_{L^{2}(E_{\delta})}$ and
$\|\varphi\|_{L^{2}(\mathcal{M}_{\delta})}$ in (3.26) using (3.14) and (3.18),
and use that $B^{k}_{\delta}\subset B^{k}$, to obtain

$1\leq
C(\varepsilon+\delta)+\sum_{k=1}^{K}\mathcal{L}(B^{k}_{\delta})(\Sigma\beta)_{k}^{2}\leq
C(\varepsilon+\delta)+\max_{k}\mathcal{L}(B^{k})\,|\Sigma\beta|^{2}.$ (3.30)

Thus, for every $\delta$ and $\varepsilon$ sufficiently small,

$\widetilde{C}\leq\max_{k}\mathcal{L}(B^{k})\,|\Sigma\beta|^{2}$ (3.31)

which completes the proof. ∎

###  3.2 Main results

Next we show that if $\varepsilon,\delta>0$ are sufficiently small, then the
first eigenvalue of $L_{\varepsilon}[u_{\delta}]$ is bounded from below by a
constant independent of $\varepsilon,\delta$.

######  Theorem 3.4.

There exists a positive constant $C$ such that for every
$\varepsilon,\delta>0$ sufficiently small and for every $v\in
H^{1}_{0}(\Omega)$,

$C\|\nabla v\|_{L^{1}(\Omega)}\leq\sqrt{B_{\varepsilon,\delta}[v,v]},\qquad
C\|v\|_{L^{2}(\Omega)}^{2}\leq B_{\varepsilon,\delta}[v,v].$ (3.32)

In particular, the second estimate yields $\lambda_{1}\geq C>0$.

###### Proof.

We begin by showing the first estimate of (3.32). Let $v\in
H^{1}_{0}(\Omega)$. Hölder’s inequality and Lemma 4 of [5] yield

$\delta\|\nabla
v\|_{L^{2}(\mathcal{M}_{\delta})}^{2}\geq\frac{\delta}{\mathcal{L}(\mathcal{M}_{\delta})}\|\nabla
v\|_{L^{1}(\mathcal{M}_{\delta})}^{2}\geq C\|\nabla
v\|_{L^{1}(\mathcal{M}_{\delta})}^{2}.$ (3.33)

Similarly we use Hölder’s inequality to estimate $\|\nabla
v\|_{L^{2}(D_{\delta})}^{2}$ from below by $C\|\nabla
v\|_{L^{1}(D_{\delta})}^{2}$ and thus, by (3.8), for $\varepsilon>0$
sufficiently small we get

$C_{1}\|\nabla v\|_{L^{1}(\Omega)}^{2}\leq B_{\varepsilon,\delta}[v,v],$
(3.34)

which is equivalent to the first estimate of (3.32).

To verify the second estimate of (3.32), we only need to show that the
smallest eigenvalue $\lambda_{1}$ of $L_{\varepsilon}[u_{\delta}]$ in
$H^{1}_{0}(\Omega)$ is bounded from below by a constant $C$ independent of
$\varepsilon$ and $\delta$. Thus, for the proof we may set
$\mathcal{V}^{\delta}_{0}=H^{1}_{0}(\Omega)$ and show that for every
$\varepsilon,\delta>0$ sufficiently small,

$\lambda_{1}=B_{\varepsilon,\delta}[\varphi_{1},\varphi_{1}]\geq C.$

Substituting $v=\varphi_{1}$ into (3.34) yields

$\lambda_{1}=B_{\varepsilon,\delta}[\varphi_{1},\varphi_{1}]\geq
C_{1}\|\nabla\varphi_{1}\|_{L^{1}(\Omega)}^{2}.$ (3.35)

Thus for $\varepsilon,\delta>0$ sufficiently small, by Poincaré’s inequality
(3.12) we get

$\lambda_{1}\geq C_{1}\|\nabla\varphi_{1}\|_{L^{1}(\Omega)}^{2}\geq
C_{2}\|\varphi_{1}\|_{L^{1}(\Omega)}^{2}.$ (3.36)

Therefore,

$\sqrt{\lambda_{1}}\geq\sqrt{C_{2}}\,\sum_{k=1}^{K}\mathcal{L}(B^{k}_{\delta})|\langle\varphi_{1}\rangle_{B^{k}_{\delta}}|.$
(3.37)

As a consequence, for every $0<\delta\leq\delta_{0}$, with $\delta_{0}$
sufficiently small, we have

$\sqrt{\lambda_{1}}\geq
C_{3}\min_{k}\mathcal{L}(B^{k}_{\delta_{0}})\sum_{k=1}^{K}|\langle\varphi_{1}\rangle_{B^{k}_{\delta}}|,$
(3.38)

where we have used that $B^{k}_{\delta}\supset B^{k}_{\delta_{0}}$. Finally,
Lemma 3.3 yields

$\sum_{k=1}^{K}|\langle\varphi_{1}\rangle_{B^{k}_{\delta}}|=|\Sigma
e_{1}|_{\ell^{1}}\geq|\Sigma e_{1}|\geq C>0,$ (3.39)

where $\Sigma$ is given by (3.22) and
$e_{1}=(1,0,\ldots,0)^{T}\in\mathbb{R}^{K}$, and thus $\lambda_{1}\geq C>0$.
Since $\lambda_{1}$ is the minimum of the Rayleigh quotient in
$H^{1}_{0}(\Omega)\setminus\\{0\\}$, the last two estimates yield the second
inequality in (3.32), which completes the proof. ∎

Recall that we have not yet derived estimate (3.17) of Lemma 3.2. To do so, we
will need to estimate the norm of $\varphi_{0}-u^{0}$ (or $\varphi_{0}$) in
$\Omega$.

######  Lemma 3.5.

There exists a positive constant $C$, such that for each positive
$\delta,\varepsilon>0$ sufficiently small

$\|\varphi_{0}-u^{0}\|_{L^{2}(\Omega)}\leq C,\qquad k=1,\ldots,K.$ (3.40)

###### Proof.

Let $\eta\in\mathcal{V}^{\delta}_{0}$ be given by
$\eta=\varphi_{0}-u^{0}_{\delta}$, where $u^{0}_{\delta}$ is the admissible
approximation of $u^{0}$. Then, (2.24) implies

$B_{\varepsilon,\delta}[\varphi_{0},\eta]=0$ (3.41)

and thus using (3.1) we obtain

$B_{\varepsilon,\delta}[\eta,\eta]\leq
B_{\varepsilon,\delta}[\eta,\eta]+B_{\varepsilon,\delta}[\varphi_{0},\varphi_{0}]=B_{\varepsilon,\delta}[u^{0}_{\delta},u^{0}_{\delta}]\leq
C.$ (3.42)

Since $\eta=0$ on $\partial\Omega$, we also have

$\lambda_{1}\|\eta\|_{L^{2}(\Omega)}^{2}\leq
B_{\varepsilon,\delta}[\eta,\eta]\leq C.$ (3.43)

By Theorem 3.4, $\lambda_{1}$ is bounded from below by a positive constant
independent of $\delta$ and $\varepsilon$, therefore,

$\|\varphi_{0}-u^{0}_{\delta}\|_{L^{2}(\Omega)}=\|\eta\|_{L^{2}(\Omega)}\leq
C,$ (3.44)

which yields (3.40) by the triangle inequality, (2.9) and (2.6) and thus
completes the proof. ∎

We can now prove our main results. Here, as above, we suppose $u$, given by
(2.4), is approximated by admissible $u_{\delta}$ as defined in Section 2.2,
and let $X_{K}$ be given by (3.4). For $\varepsilon,\delta$ positive,
$L_{\varepsilon}[\cdot]$ is given by (2.1) with $\mu_{\varepsilon}[\cdot]$
given by (2.19). Finally, we let $\varphi_{0}$ satisfy (2.24) and
$\varphi_{1},\ldots,\varphi_{K}$ satisfy (2.25) weakly in
$\mathcal{V}^{\delta}_{0}$.

######  Theorem 3.6.

  1. 1.

Let $\Pi_{K}^{\varepsilon}[u_{\delta}]$ be the orthogonal projection on
$\Phi_{K}^{\varepsilon,\delta}$, given by (3.3). There exists a positive
constant $C$ such that for every $v\in X_{K}$ and every $\varepsilon,\delta$
sufficiently small,

$\left\|v-\Pi_{K}^{\varepsilon}[u_{\delta}]v\right\|_{L^{2}(\Omega)}\leq
C\sqrt{\varepsilon+\delta}\,\|v\|_{L^{2}(\Omega)}.$ (3.45)

In particular, $v=\widetilde{u}$ and $v=\chi_{A^{k}}$ ($k=1,\ldots,K$) satisfy
(3.45).

  2. 2.

Let $Q_{K}^{\varepsilon}[u_{\delta}]$ be the $L^{2}$-orthogonal projection on
$\varphi_{0}+\Phi_{K}^{\varepsilon,\delta}$, given by (3.5). There exists a
positive constant $C$ such that for every $v\in u^{0}+X_{K}$ and every
$\varepsilon,\delta$ sufficiently small,

$\big{\|}v-Q_{K}^{\varepsilon}[u_{\delta}](v)\big{\|}_{L^{2}(\Omega)}\leq
C\sqrt{\varepsilon+\delta}\,\big{(}\|v-u^{0}\|_{L^{2}(\Omega)}+1\big{)}.$
(3.46)

In particular, $v=u$ and $v=u^{0}$ satisfy (3.46).

######  Remark 3.7.

Theorem 3.6 estimates the projection error for piecewise constant functions in
$X_{K}$ and $u^{0}+X_{K}$. From these we immediately obtain error estimates
for $L^{2}(\Omega)$ functions, e.g, admissible approximations of elements of
$X_{K}$ or $u^{0}+X_{K}$. By the triangle inequality and Theorem 3.6, for
every $v\in X_{K}$ and $w\in L^{2}(\Omega)$, we have

$\big{\|}w-\Pi_{K}^{\varepsilon}[u_{\delta}]w\big{\|}_{L^{2}(\Omega)}\leq
C\sqrt{\varepsilon+\delta}\,\|w\|_{L^{2}(\Omega)}+\|w-v\|_{L^{2}(\Omega)}\,,$
(3.47)

and, similarly, if $v\in u^{0}+X_{K}$ and $w\in L^{2}(\Omega)$, then

$\big{\|}w-Q_{K}^{\varepsilon}[u_{\delta}](w)\big{\|}_{L^{2}(\Omega)}\leq
C\sqrt{\varepsilon+\delta}\,\big{(}\|w-u^{0}\|_{L^{2}(\Omega)}+1\big{)}+\|w-v\|_{L^{2}(\Omega)}\,.$
(3.48)

In particular, (3.47) is satisfied for $v=\widetilde{u}$ and
$w=\widetilde{u}_{\delta}$, and (3.48) is satisfied for $v=u$ and
$w=u_{\delta}$ and for $v=u^{0}$ and $w=u^{0}_{\delta}$.

Similarly to Corollary 6 of [5], we have the following:

######  Corollary 3.8.

  1. 1.

If $u_{h}$ is the interpolation of $u$ in a FE space $V_{h}$ as in Proposition
2.2, and either $\mathcal{V}^{h}=V_{h}$ or $\mathcal{V}^{h}=H^{1}(\Omega)$,
then for every $\varepsilon,h>0$ sufficiently small, estimates (3.45) and
(3.46) with $\delta=h$ hold true.

  2. 2.

If $u_{\delta}$ is the mollification of $u$ as in Proposition 2.3 and
$\mathcal{V}^{\delta}=H^{1}(\Omega)$, then for every $\varepsilon,\delta>0$
sufficiently small, estimates (3.45) and (3.46) hold true.

###### Proof.

This corollary is a direct result of Theorem 3.6 and Propositions 2.2 and 2.3.
∎

Assertion 1 of Corollary 3.8 is particularly important for applications, as it
implies that our main estimates are valid not only for the continuous setting,
but also for Galerkin FE discretizations as follows: Let $u_{h}$ be the
interpolant of $u$ in a FE space $V_{h}$ with mesh size $h$, and let
$\varphi_{0},\varphi_{1},\ldots,\varphi_{K}$ be the Galerkin FE solutions of
(2.24), (2.25) with $u_{\delta}=u_{h}$ in $V_{h}$. By Assertion 1 of Corollary
3.8, the projections $\Pi_{K}^{\varepsilon}[u_{h}],Q_{K}^{\varepsilon}[u_{h}]$
defined by (3.3) and (3.5) – using the _computed_ FE solutions
$\varphi_{0},\varphi_{1},\ldots,\varphi_{K}$ – satisfy (3.45) and (3.46) with
$\delta=h$.

###### Proof of Theorem 3.6.

Here, we only show (3.46); the proof of (3.45) is similar. We have

$\big{\|}v-Q_{K}^{\varepsilon}[u_{\delta}](v)\big{\|}_{L^{2}(\Omega)}=\min_{\beta\in\mathbb{R}^{K}}\bigg{\|}(v-\varphi_{0})-\sum_{k=1}^{K}\beta_{k}\varphi_{k}\bigg{\|}_{L^{2}(\Omega)}.$
(3.49)

By Lemma 3.3 there exists a unique vector $\beta=(\beta_{k})\in\mathbb{R}^{K}$
such that

$\sum_{j=1}^{K}\beta_{j}\langle\varphi_{j}\rangle_{B^{k}_{\delta}}=\langle
v-\varphi_{0}\rangle_{B^{k}_{\delta}},\qquad k=1,\ldots,K,$ (3.50)

and, moreover,

$|\beta|^{2}\leq C_{1}\sum_{k=1}^{K}\langle
v-\varphi_{0}\rangle_{B^{k}_{\delta}}^{2}$ (3.51)

for $C_{1}>0$ independent of $\varepsilon$, $\delta$ and $v$. Thus, we get

$|\beta|\leq\sqrt{C_{1}}\left[\sum_{k=1}^{K}\|v-\varphi_{0}\|_{L^{2}(B^{k}_{\delta})}^{2}\right]^{\frac{1}{2}}.$
(3.52)

By Lemma 3.5, we have

$\|v-\varphi_{0}\|_{L^{2}(B^{k}_{\delta})}\leq\|v-u^{0}\|_{L^{2}(B^{k}_{\delta})}+\|u^{0}-\varphi_{0}\|_{L^{2}(B^{k}_{\delta})}\leq\|v-u^{0}\|_{L^{2}(B^{k}_{\delta})}+C$
(3.53)

which yields

$|\beta|\leq C\big{(}\|v-u^{0}\|_{L^{2}(\Omega)}+1\big{)},$ (3.54)

with $C>0$ independent of $\varepsilon$, $\delta$ and $v$. Define

$\varphi=\varphi_{0}+\widetilde{\varphi},\qquad\widetilde{\varphi}=\sum_{k=1}^{K}\beta_{k}\varphi_{k}\in\Phi_{K}^{\varepsilon,\delta}.$
(3.55)

Thus, we have

$\big{\|}v-Q_{K}^{\varepsilon}[u_{\delta}](v)\big{\|}_{L^{2}(\Omega)}\leq\|v-\varphi\|_{L^{2}(\Omega)}.$
(3.56)

By the triangle inequality, we get

$\displaystyle\|v-\varphi\|_{L^{2}(\Omega)}$
$\displaystyle\leq\|v-\varphi\|_{L^{2}(E_{\delta})}+\|v-u^{0}\|_{L^{2}(\mathcal{M}_{\delta})}+\|u^{0}-\varphi\|_{L^{2}(\mathcal{M}_{\delta})}$
(3.57)
$\displaystyle\quad+\sum_{k=1}^{K}\|v-\varphi\|_{L^{2}(B^{k}_{\delta})}.$

Next we estimate each of the terms on the right hand side. Since $v=u^{0}$ in
$E_{\delta}$, we can estimate the first term as follows:

$\displaystyle\|v-\varphi\|_{L^{2}(E_{\delta})}$
$\displaystyle\leq\|u^{0}-\varphi_{0}\|_{L^{2}(E_{\delta})}+\|\widetilde{\varphi}\|_{L^{2}(E_{\delta})}$
(3.58)
$\displaystyle\leq\|u^{0}-\varphi_{0}\|_{L^{2}(E_{\delta})}+\sum_{k=1}^{K}|\beta_{k}|\|\varphi_{k}\|_{L^{2}(E_{\delta})}$
$\displaystyle\leq
C\sqrt{\varepsilon}\,\big{(}\|v-u^{0}\|_{L^{2}(\Omega)}+1\big{)}$

because of (3.13), (3.14) and (3.54). The second term on the right hand side
of (3.57) is the $L^{2}$ norm of the piecewise constant function $w=v-u^{0}$
in $\mathcal{M}_{\delta}$. Since $w=0$ a.e. in
$\Omega\setminus\overline{\bigcup_{k=1}^{K}B^{k}}$, we have

$\|v-u^{0}\|_{L^{2}(\mathcal{M}_{\delta})}^{2}=\int_{\mathcal{M}_{\delta}}w^{2}=\sum_{k=1}^{K}\int_{\mathcal{M}_{\delta}\cap
B^{k}}w^{2}.$ (3.59)

We now use that $w^{2}$ is constant in each $B^{k}$ and that
$\mathcal{L}(\mathcal{M}_{\delta}\cap B^{k})=\mathcal{O}(\delta)$ [5, Lemma 4]
to get

$\int_{\mathcal{M}_{\delta}\cap
B^{k}}w^{2}=\mathcal{L}(\mathcal{M}_{\delta}\cap B^{k})\,w^{2}|_{B^{k}}\leq
C\delta\,\mathcal{L}(B^{k})\,w^{2}|_{B^{k}}=C\delta\int_{B^{k}}w^{2}$ (3.60)

which yields

$\|v-u^{0}\|_{L^{2}(\mathcal{M}_{\delta})}\leq
C\sqrt{\delta}\,\|v-u^{0}\|_{L^{2}(\Omega)}.$ (3.61)

To estimate the third term we use Lemma 3.2 and (3.54) to obtain

$\displaystyle\|u^{0}-\varphi\|_{L^{2}(\mathcal{M}_{\delta})}$
$\displaystyle\leq\|u^{0}-\varphi_{0}\|_{L^{2}(\mathcal{M}_{\delta})}+\sum_{k=1}^{K}|\beta_{k}|\|\varphi_{k}\|_{L^{2}(\mathcal{M}_{\delta})}$
(3.62) $\displaystyle\leq
C\sqrt{\delta}\,\big{(}\|v-u^{0}\|_{L^{2}(\Omega)}+1\big{)}.$

For each $k=1,\ldots,K$, we estimate $\|v-\varphi\|_{L^{2}(B^{k}_{\delta})}$
as follows: Since $\beta$ solves (3.50), we have $\langle
v-\varphi\rangle_{B^{k}_{\delta}}=0$, which by the Poincaré inequality (3.10)
yields

$\|v-\varphi\|_{L^{2}(B^{k}_{\delta})}\leq
C\|\nabla(v-\varphi)\|_{L^{2}(B^{k}_{\delta})}.$ (3.63)

Since $\nabla v=0$ in $B^{k}_{\delta}$, estimates (3.9) and (3.54) yield

$\displaystyle\|v-\varphi\|_{L^{2}(B^{k}_{\delta})}$ $\displaystyle\leq
C_{1}\|\nabla\varphi\|_{L^{2}(B^{k}_{\delta})}\leq
C_{1}\left(\|\nabla\varphi_{0}\|_{L^{2}(B^{k}_{\delta})}+\sum_{j=1}^{K}|\beta_{j}|\|\nabla\varphi_{j}\|_{L^{2}(B^{k}_{\delta})}\right)$
(3.64) $\displaystyle\leq
C_{2}\sqrt{\varepsilon}\big{(}\|v-u^{0}\|_{L^{2}(\Omega)}+1\big{)}.$

Finally, by combining the above, we obtain

$\big{\|}v-Q_{K}^{\varepsilon}[u_{\delta}](v)\big{\|}_{L^{2}(\Omega)}\leq\|v-\varphi\|_{L^{2}(\Omega)}\leq
C\sqrt{\varepsilon+\delta}\,\big{(}\|v-u^{0}\|_{L^{2}(\Omega)}+1\big{)}$
(3.65)

which completes the proof. ∎

##  4 Numerical examples

Here we present numerical examples which illustrate the main results of our
analysis and, in particular, the remarkable accuracy of AS decompositions for
piecewise constant media111We will use the term _medium_ for functions from
$\Omega\subset\mathbb{R}^{2}$ into $\mathbb{R}$.. First, we consider media
comprised of a constant background $u^{0}$ and a single characteristic
function. Secondly we consider a medium which consists of an inhomogeneous
background comprised of five sets $\Omega^{m}$, $m=1,\ldots,5$, and four
interior inclusions $A^{k}$, $k=1,\ldots,4$ (see Section 2.1). In the third
example, we consider a medium which consists of four adjacent squares in a
constant background. Since the boundaries of the squares are not mutually
disjoint, this example is not covered by our theory. Next we apply the AS
decomposition to two more complex examples that are not covered by our theory:
a polygonal approximation of the map of Switzerland with its 26 cantons and
the well-known Marmousi model from seismic imaging. Finally, we devise a
simple iterative inversion algorithm based on AS decompositions to solve a
standard deconvolution inverse problem from optical imaging [15].

In all examples the domain $\Omega\subset\mathbb{R}^{2}$ is rectangular and we
use a regular, uniform triangular mesh $\mathcal{T}_{h}$ whose vertices lie on
an equidistant Cartesian grid of size $h>0$. We let
$\mathcal{V}^{\delta}\subset H^{1}(\Omega)$, with $\delta=h$, be the standard
$\mathcal{P}^{1}$ FE space of continuous piecewise linear functions and set
$\mathcal{V}^{\delta}_{0}=\mathcal{V}^{\delta}\cap H^{1}_{0}$. For piecewise
constant $u$, we let $u_{\delta}$ denote the $H^{1}$-conforming (continuous)
interpolation of $u$ in the FE space $\mathcal{V}^{\delta}$.

We consider decompositions associated with $L_{\varepsilon}[u_{\delta}]$ given
by (2.1) with $\mu_{\varepsilon}[\cdot]$ of the form (2.2) with $q=2$. We
compute the approximation of the background $\varphi_{0}$ and the first few
eigenfunctions $\varphi_{k}$ of $L_{\varepsilon}[u_{\delta}]$ by numerically
solving (2.24) and (2.25) using the Galerkin FE method. The discretization of
(2.25) leads to a generalized eigenvalue problem

$\displaystyle\mathrm{A}\varphi_{k}=\lambda_{k}\mathrm{M}\varphi_{k}\quad\text{for}\quad
k=1,\ldots,K,$ (4.1)

where the stiffness matrix $\mathrm{A}$ corresponds to the discretization of
$L_{\varepsilon}[u_{\delta}]$ and M is the mass matrix. We solve (4.1)
numerically using the MATLAB function eigs.

Once we have obtained $\varphi_{0}\in\mathcal{V}^{\delta}$ and
$\varphi_{k}\in\mathcal{V}^{\delta}_{0}$ for $k=1,\ldots,K$, we can compute
the projections $\Pi_{K}^{\varepsilon}[u_{\delta}]$ and
$Q_{K}^{\varepsilon}[u_{\delta}]$ given by (3.3) and (3.5). Since
$\\{\varphi_{k}\\}_{k=1}^{K}$ are computed numerically, they satisfy
$\langle\varphi_{k},\varphi_{j}\rangle=\delta_{kj}$ only up to a small error.
This slight loss of orthonormality causes small errors when computing the
projection $\Pi_{K}^{\varepsilon}[u_{\delta}]$ directly from the Fourier
expansion

$\displaystyle\Pi_{K}^{\varepsilon}[u_{\delta}]v=\sum_{k=1}^{K}\langle\varphi_{k},v\rangle\,\varphi_{k}.$

To avoid these errors, we instead compute $\Pi_{K}^{\varepsilon}[u_{\delta}]v$
by solving the $K$-dimensional least squares problem

$\displaystyle\Pi_{K}^{\varepsilon}[u_{\delta}]v=\operatorname*{argmin}_{w\in\Phi_{K}^{\varepsilon,\delta}}\|v-w\|_{L^{2}(\Omega)},\qquad\Phi_{K}^{\varepsilon,\delta}=\operatorname{span}\\{\varphi_{k}\\}_{k=1}^{K}.$

When validating the conclusion of Theorem 3.6 and its corollary in Remark 3.7,
we shall focus on two types of errors

$\|u-Q_{K}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}\qquad\text{and}\qquad\|u_{\delta}-Q_{K}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)};$
(4.2)

the first measures the misfit to the true medium $u$ whereas the second
measures the misfit to the continuous interpolant $u_{\delta}$. Note that in
both cases the same AS basis is used. Computing these expressions requires the
evaluation of $L^{2}$ inner products. As the functions participating in the
expression on the right lie in the FE space $\mathcal{V}^{\delta}$, we can
evaluate the needed integrals exactly. In contrast, the expression on the left
includes inner products involving a piecewise constant function whose
discontinuities are, in general, not aligned with the mesh. Thus, to evaluate
the integrals for the error on the left in (4.2), we use a numerical
quadrature rule from ACM TOMS algorithm $\\#584$ [16] with degree of precision
of $8$ and $19$ quadrature points.

In principle, $\varepsilon>0$ should be as small as possible, while
sufficiently large so that the matrix $\mathrm{A}$ is well-conditioned. Unless
specified otherwise, we always use ${\varepsilon=10^{-8}}$.

###  4.1 Four simple shapes

(a) disc

(b) square

(c) Pac-Man

(d) star

Figure 3: Four simple shapes. The exact medium $u$ (or $u_{\delta}$) consists
of a single characteristic function $\chi_{A^{1}}$ and vanishing $u^{0}$.

We consider the four 2-dimensional piecewise constant media
${u:\Omega\to\mathbb{R}}$, in $\Omega=(0,1)^{2}$, shown in Fig. 3. All four
vanish on the boundary $\partial\Omega$ and correspond to the characteristic
function

$\displaystyle u(x)=\widetilde{u}(x)=\chi_{A^{1}}(x),\quad x\in\Omega$ (4.3)

of a Lipschitz domain and are therefore covered by our analysis. The sets are
chosen purposely with different geometric properties: the disc is convex with
a smooth boundary; the square is convex, but its boundary is only piecewise
smooth; the Pac-Man and the star are both non-convex with piecewise smooth
boundaries.

$10^{-3}$$10^{-2}$$10^{-2}$$10^{-1}$$\delta$ErrordiscsquarePac-
Manstar$\sqrt{\delta}$

$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$10^{0}$$10^{-3}$$10^{-2}$$10^{-1}$$\varepsilon$ErrordiscsquarePac-
Manstar$\varepsilon$

Figure 4: Four simple shapes. The error
$\|u-\Pi_{1}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}$. Left: the error
as a function of $\delta$ for fixed $\varepsilon=10^{-8}$. Right: the error as
a function of $\varepsilon$ for fixed mesh-size $\delta=0.05/2^{6}$.

$10^{-3}$$10^{-2}$$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$\delta$ErrordiscsquarePac-
Manstar${\delta}$

$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$10^{0}$$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$\varepsilon$ErrordiscsquarePac-
Manstar$\varepsilon$

Figure 5: Four simple shapes. The error
$\|u_{\delta}-\Pi_{1}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$.
Left: the error as a function of $\delta$ for fixed $\varepsilon=10^{-8}$.
Right: the error as a function of $\varepsilon$ for fixed mesh-size
$\delta=0.05/2^{6}$.

In Figure 4, we show the error
${\|u-\Pi_{1}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}}$. The left frame
shows the error for varying mesh-size $\delta$ but fixed
$\varepsilon=10^{-8}$. For all four shapes, the error decays as
$\mathcal{O}(\sqrt{\delta})$, as proved in Theorem 3.6. The right frame of
Figure 4 shows the error
$\|u-\Pi_{1}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}$ for varying
$\varepsilon$ on the fixed finest mesh, i.e., with smallest $\delta$. The
error initially decreases with $\varepsilon$ but then levels off at about
$10^{-2}$, at which point it can only be improved by further refining the
mesh.

To eliminate the interpolation error and thereby illustrate the estimates of
Remark 3.7, we show in Figure 5 the projection error
$\|u_{\delta}-\Pi_{1}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$.
On the left, we show the approximation error for varying $\delta$, with
$\varepsilon=10^{-8}$ fixed: The projections of the disc, the square, and the
Pac-Man in the AS basis are remarkably good, with errors at about $10^{-9}$.
For these cases, the projection of each $u_{\delta}$ (hence the first
eigenfunction $\varphi_{1}$ of $L_{\varepsilon}[u_{\delta}]$) essentially
coincides with $u_{\delta}$ itself. In contrast, the error for the star is
larger, though it decays at a rate of $\mathcal{O}(\delta)$, still faster than
the upper estimate of $\mathcal{O}(\sqrt{\delta})$ in Remark 3.7. In all
cases, the errors here are significantly smaller than those in the left frame
of Figure 4, indicating that the errors in Figure 4 are mainly due to
interpolating $u$ in $\mathcal{V}^{\delta}$.

The error
$\|u_{\delta}-\Pi_{1}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$
for varying $\varepsilon$ and fixed $\delta$ is shown in the right frame of
Figure 5. Here we observe a decay rate of $\mathcal{O}(\varepsilon)$, which is
also faster than the upper estimate in Remark 3.7. Here, for all shapes but
the star, the error decreases with $\varepsilon$ down to about $10^{-9}$. In
contrast, the error for the star levels off at about $10^{-3}$.

The significant difference in the behavior of the error for the star compared
to the other shapes, shown in Figure 5, is due to the geometry of the
discontinuities in the media and the mesh. Indeed, if we repeat the experiment
for the star but with a locally adapted mesh aligned with the star’s geometry,
as shown in Figure 6, the error
$\|u_{\delta}-\Pi_{1}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$
also drops below $10^{-8}$. Note that while $\delta$ is smaller in this test
than it is in the tests shown in Figure 5, this reduction by itself is not
sufficient to explain the difference in the errors between figures 5 and 6,
which is of about 6 orders of magnitude.

$10^{-3}$$10^{-2}$$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$\delta$Errorstar${\delta}$

Figure 6: Four simple shapes. Left: The aligned mesh for the star-shaped
medium with $\delta=0.05/2^{2}$. Right: the error
$\|u_{\delta}-\Pi_{1}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$
for mesh-sizes $\delta=0.05/2^{m}$, $m=1,\ldots,6$, and fixed
$\varepsilon=10^{-8}$.

###  4.2 Nonuniform background

(a) The medium $u$ (or $u_{\delta}$)

(b) $\varphi_{1}$ with $\lambda_{1}\approx 14.37$

(c) $\varphi_{3}$ with $\lambda_{3}\approx 36.04$

(d) $\varphi_{0}$

(e) $\varphi_{2}$ with $\lambda_{2}\approx 29.88$

(f) $\varphi_{4}$ with $\lambda_{4}\approx 50.48$

Figure 7: Nonuniform background. The exact medium u with its background
$\varphi_{0}$ and first four eigenpairs $(\lambda_{i},\varphi_{i})$,
$i=1,\ldots,4$.

Next we consider a medium $u$ with non-constant background $u^{0}$. We let
${u:\Omega\to\mathbb{R}}$ be the medium shown in frame (a) of Fig. 7, and
$\Omega=(0,1)^{2}$. Here $u$ admits a decomposition (2.4), (2.5) with ${M=5}$
and ${K=4}$. Figure 7 also shows the approximation $\varphi_{0}$ of the
background and the first four eigenfunctions $\varphi_{1},\ldots,\varphi_{4}$
of $L_{\varepsilon}[u_{\delta}]$.

Figure 8 (left) shows the error
$\|u-Q_{K}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}$ with $K=4$, for six
different meshes with $\delta=0.05/2^{m}$, $m=1,\ldots,6$. Here we observe an
error decay of $\mathcal{O}(\sqrt{\delta})$, consistent with our theoretical
estimates. The right frame of Figure 8 shows the error
$\|u_{\delta}-Q_{K}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$
with $K=4$, as a function of $\varepsilon$ with fixed $\delta=0.05/2^{6}$.
Again, we observe a convergence rate of $\mathcal{O}(\varepsilon)$, faster
than the $\mathcal{O}(\sqrt{\varepsilon})$ rate proved in Remark 3.7.

$10^{-3}$$10^{-2}$$10^{-1.5}$$10^{-1}$$\delta$Errormedium$\sqrt{\delta}$

$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$10^{0}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$\varepsilon$Errormedium$\varepsilon$

Figure 8: Nonuniform background. Left: the error
$\|u-Q_{4}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}$ for mesh-sizes
$\delta=0.05/2^{m}$, $m=1,\ldots,6$, and fixed $\varepsilon=10^{-8}$. Right:
the error
$\|u_{\delta}-Q_{4}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$
for $\varepsilon=10^{-m}$, $m=0,\ldots,8$, and fixed mesh-size
$\delta=0.05/2^{6}$.

###  4.3 Four adjacent Squares

(a) The medium $u$ (or $u_{\delta}$)

(b) $\varphi_{1}$ with $\lambda_{1}\approx 3.3$

(c) $\varphi_{3}$ with $\lambda_{3}\approx 12.65$

(d) $\Pi_{4}^{\varepsilon}[u_{\delta}]u_{\delta}$

(e) $\varphi_{2}$ with $\lambda_{2}\approx 8.88$

(f) $\varphi_{4}$ with $\lambda_{4}\approx 18.37$

Figure 9: Adjacent squares. The medium $u$ and the first four eigenfunctions
$\varphi_{k}$, $k=1,\ldots,4$, of the operator $L_{\varepsilon}[u_{\delta}]$,
together with its AS decomposition
$\Pi_{4}^{\varepsilon}[u_{\delta}](u_{\delta})$ computed on a mesh with
$\delta=0.05/2^{6}$.

Let $\Omega$ be the unit square $\Omega=(0,1)^{2}$ and

$\displaystyle u(x)=\sum_{k=1}^{4}\alpha_{k}\chi_{A^{k}}(x),\quad x\in\Omega,$
(4.4)

with $\alpha_{k}=k$, for $k=1,\ldots,4$, the piecewise constant medium shown
in Fig. 9. Since the boundaries $\partial A^{k}$ of the squares $A^{k}$ are
not mutually disjoint, this example is not covered by our analysis. However,
we may still compute the AS approximation and measure the approximation error.

In Figure 10 we still observe errors of $\mathcal{O}(\sqrt{\delta})$,
consistent with our theoretical estimates. Again, the error with respect to
$\varepsilon$ decays with a rate of $\mathcal{O}(\varepsilon)$, as seen in
Figure 10.

$10^{-3}$$10^{-2}$$10^{-1}$$10^{-0.5}$$\delta$Errormedium$\sqrt{\delta}$

$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$10^{0}$$10^{-8}$$10^{-6}$$10^{-4}$$10^{-2}$$\varepsilon$Errormedium$\varepsilon$

Figure 10: Adjacent squares. Left: the error
$\|u-\Pi_{4}^{\varepsilon}[u_{\delta}](u)\|_{L^{2}(\Omega)}$ for mesh-sizes
$\delta=0.05/2^{m}$, $m=1,\ldots,6$, and fixed $\varepsilon=10^{-8}$. Right:
the error
$\|u_{\delta}-\Pi_{4}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}$
for $\varepsilon=10^{-m}$, $m=0,\ldots,8$, and fixed mesh-size
$\delta=0.05/2^{6}$;

###  4.4 Map of Switzerland

(a) Polygonal Switzerland (b) 3D-view of $\varphi_{5}$

(c) $\varphi_{2}$ with $\lambda_{2}\approx 28.75$

(d) $\varphi_{5}$ with $\lambda_{5}\approx 85.03$

(e) $\varphi_{15}$ with $\lambda_{15}\approx 217.59$

Figure 11: Polygonal approximation of the map of Switzerland $u_{\delta}$ and
its $26$ cantons (top left), together with three eigenfunctions $\varphi_{k}$,
$k=2,5,15$, of the operator $L_{\varepsilon}[u_{\delta}]$.

Here we consider the polygonal approximation of the map of Switzerland with
its $K=26$ cantons, shown in frame (a) of Figure 11, where each canton admits
a constant value. The data of the map are given on a discrete rectangular
pixel based $1563\,\mathrm{px}\times 1002\,\mathrm{px}$ grid with grid-size
$\delta=1\,\mathrm{px}$. We interpolate the data to obtain
$u_{\delta}\in\mathcal{V}^{\delta}_{0}$, and compute the first $K=26$
eigenfunctions, $\varphi_{1},\ldots,\varphi_{K}$ of
$L_{\varepsilon}[u_{\delta}]$; frames (c), (d) and (e) of Figure 11 show three
of the eigenfunctions.

Although a single eigenfunction does not necessarily correspond to any
particular canton, we may still represent each canton in
$\Phi_{26}^{\varepsilon,\delta}=\operatorname{span}\\{\varphi_{k}\\}_{k=1}^{26}$.
If $u^{\mathrm{c}}$ is the characteristic function for a canton shown in the
map in Figure 11, and $u^{\mathrm{c}}_{\delta}$ is its continuous (piecewise
linear) interpolant in $\mathcal{V}^{\delta}$, we can use the AS basis
$\\{\varphi_{k}\\}_{k=1}^{K}$ to approximate $u_{\delta}^{\mathrm{c}}$ as

$\displaystyle
u_{\delta}^{\mathrm{c}}\approx\Pi_{K}^{\varepsilon}[u_{\delta}]\,u_{\delta}^{\mathrm{c}}=\sum_{k=1}^{K}\beta_{k}\varphi_{k},$

with $K=26$. In Figure 12 we show the approximations for the cantons of Bern,
Grisons, and St. Gallen in
$\Phi_{26}^{\varepsilon,\delta}=\operatorname{span}\\{\varphi_{k}\\}_{k=1}^{K}$.
These reconstructions approximate very well the exact cantons in Figure 11.

(a) Canton of Bern

(b) Canton of Grisons

(c) Canton of St. Gallen

Figure 12: Map of Switzerland. Three cantons approximated in the truncated AS
basis $\\{\varphi_{k}\\}_{k=1}^{K}$ with $K=26$.

(a) The Marmousi model

(b) $\varphi_{0}$ with a relative $L^{2}$ error of $12.8\%$

(c) $Q_{100}^{\varepsilon}[u_{\delta}](u_{\delta})$ with a relative $L^{2}$
error of $3.8\%$

Figure 13: The original Marmousi model with its background $\varphi_{0}$ and
AS decomposition with $100$ eigenfunctions.

###  4.5 The Marmousi model

As a last example we consider the subsurface model of the P-wave velocity of
the AGL elastic Marmousi model shown in Figure 13, see [17, 18]. The data of
the model is given as nodal values on a discrete rectangular mesh representing
a $17\,\mathrm{km}\times 3.5\,\mathrm{km}$ area. We interpolate the data in
$\mathcal{V}^{\delta}$ with $\delta=2.5\,\mathrm{m}$ to obtain $u_{\delta}$.
Next, we compute the background $\varphi_{0}\in\mathcal{V}^{\delta}$ as well
as the first $100$ eigenfunctions of the operator
$L_{\varepsilon}[u_{\delta}]$.

Remarkably, the background $\varphi_{0}$ already yields a good approximation
of the model with a relative error of

$\displaystyle\frac{\|u_{\delta}-Q_{0}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}}{\|u_{\delta}\|_{L^{2}(\Omega)}}=\frac{\|u_{\delta}-\varphi_{0}\|_{L^{2}(\Omega)}}{\|u_{\delta}\|_{L^{2}(\Omega)}}\approx
12.8\%,$

probably because many of the internal layers in the model reach the boundary
and thus can be recovered by $\varphi_{0}$. In contrast, the eigenfunctions
$\varphi_{k}$ ($k\geq 1$) account for variations of the medium in the interior
of the domain. Here, the additional contribution of the first $K=100$
eigenfunctions to the approximation further reduces the relative error to
$\|u_{\delta}-Q_{K}^{\varepsilon}[u_{\delta}](u_{\delta})\|_{L^{2}(\Omega)}/\|u_{\delta}\|_{L^{2}(\Omega)}\approx
3.8\%$.

###  4.6 Inverse Problem

Here we devise an iterative inversion algorithm based on AS decompositions to
solve a standard linear deconvolution inverse problem which occurs in optical
imaging [15]. Hence, we consider the Fredholm integral equation of the first
kind

$Fu=y$ (4.5)

where $F:L^{2}(\Omega)\to L^{2}(\Omega)$ is the convolution operator

$Fu(x)=\int_{\Omega}g(x-x^{\prime})u(x^{\prime})\;dx^{\prime},$ (4.6)

with $\Omega=(0,1)^{2}$ and $g$ the Gaussian kernel

$g(x)=\frac{1}{2\pi\gamma^{2}}\,e^{-\frac{|x|^{2}}{2\gamma^{2}}},\qquad\gamma=\frac{1}{32}.$
(4.7)

Given the noisy observation $y^{\eta}$ of $y^{\dagger}=Fu^{\dagger}$ where
$\|y^{\dagger}-y^{\eta}\|_{L^{2}(\Omega)}\leq\eta$, we wish to reconstruct the
true medium/image $u^{\dagger}$. In doing so, we assume the FE interpolant
$u^{\dagger}_{h}$ of $u^{\dagger}$ is known on the boundary $\partial\Omega$.

First, we formulate the problem as the minimization of

$\mathcal{J}(u)=\frac{1}{2}\|Fu-y^{\eta}\|_{L^{2}(\Omega)}^{2}$ (4.8)

in some appropriate space. Then, we proceed iteratively as follows: In the
$m$-th iteration, given the previous estimate $u^{(m-1)}$ of $u^{\dagger}$, we
compute $\varphi_{k}^{(m)}$ $(k=0,\ldots,K)$ by solving

$\displaystyle\begin{aligned}
L_{\varepsilon}[u^{(m-1)}]\varphi_{0}^{(m)}&=0\;&&\text{in}\;\Omega,\qquad\varphi_{0}^{(m)}=u^{\dagger}_{h}\;&&\text{on}\;\partial\Omega,\\\
L_{\varepsilon}[u^{(m-1)}]\varphi_{k}^{(m)}&=\lambda_{k}\varphi_{k}^{(m)}\;&&\text{in}\;\Omega,\qquad\varphi_{k}^{(m)}=0\;&&\text{on}\;\partial\Omega.\end{aligned}$
(4.9)

Next, we compute the current estimate, $u^{(m)}$, by solving the least squares
(LS) problem:

$u^{(m)}=\arg\min\Big{\\{}\mathcal{J}(u):\
u\in\varphi_{0}^{(m)}+\Phi^{(m)}_{K}\Big{\\}},\qquad\Phi_{K}^{(m)}=\operatorname{span}\Big{\\{}\varphi_{k}^{(m)}\Big{\\}}_{k=1}^{K}.$
(4.10)

Since the dimension $K$ of this LS problem is small, we may solve it directly.
The iteration stops when the discrepancy principle,

$\displaystyle\|Fu^{(m)}-y^{\eta}\|_{L^{2}(\Omega)}\leq\tau\eta,$ (4.11)

is satisfied for some fixed $\tau\geq 1$; then $u^{\mathrm{ASI}}$ denotes the
estimate $u^{(m)}$ at the final iteration.

In practice, we solve the problem numerically with the FE method. As in the
previous numerical examples, we use standard $\mathcal{P}^{1}$-FE on a uniform
triangular mesh with mesh size $h=\delta=0.00625$ to discretize the
deconvolution problem (4.5) and the AS problems (4.9), (4.10). The
discretization of (4.5) yields a linear system of equations

$F_{h}\vec{u}_{h}=\vec{y}_{h},$ (4.12)

which is ill-conditioned as the smallest singular value of $F_{h}$ is
$\sigma_{\mathrm{min}}\approx 10^{-17}$. For the test below we let the exact
medium/image $u^{\dagger}$ be given by Figure 7(a), the noise $\eta\approx
4\%$ and set $u^{(0)}=y^{\eta}$ and $K=100$. Thus the dimension $K=100$ of the
LS problem in (4.10) is indeed small compared to the dimension $N\approx
26^{\prime}000$ of the FE space and we can solve it directly.

For comparison, we also solve the deconvolution problem with two other
standard approaches. In the first, we solve (4.12) directly using the LU-
decomposition to obtain the solution $u^{\mathrm{LU}}$. In the second, we
apply the truncated singular value decomposition (TSVD), i.e., we regularize
(4.12) by replacing all singular values of $F_{h}$ smaller than $\sqrt{\eta}$
by zeros; see [15, Chapter 8] or [19, Chapter 1] for more details; that
solution is denoted by $u^{\mathrm{TSVD}}$.

Table 1 provides the relative $L^{2}$ error

$\displaystyle
e_{\mathrm{r}}=\frac{\|u-u^{\dagger}_{h}\|_{L^{2}(\Omega)}}{\|u^{\dagger}_{h}\|_{L^{2}(\Omega)}}\qquad\text{and
the ratio}\qquad\tau=\frac{1}{\eta}\left\|Fu-y^{\eta}\right\|_{L^{2}(\Omega)}$
(4.13)

for the discrepancy principle (4.11), for the three reconstructions
$u^{\mathrm{ASI}}$, $u^{\mathrm{TSVD}}$, and $u^{\mathrm{LU}}$ shown in Figure
14. As expected, using the LU-decomposition for solving the inverse problem
produces the solution with the largest relative $L^{2}$ error, despite a
rather small misfit. The TSVD solution $u^{\mathrm{TSVD}}$ yields an
acceptable reconstruction with a relative error less than $20\;\%$ and
$\tau\approx 1$. Still, as shown in Figure 14(b), the discontinuities are not
well represented. In contrast, the ASI solution in Figure 14(a) has the
smallest relative $L^{2}$ error while discontinuities in the medium are better
detected. Clearly, there are many available image reconstruction techniques
more sophisticated than TSVD [20, 19, 15], which is only used here for the
purpose of illustration.

| ASI | TSVD | LU
---|---|---|---
$e_{\mathrm{r}}$ | $15.1\;\%$ | $18.9\;\%$ | $3.3\cdot 10^{14}\;\%$
$\tau$ | $1.06$ | $1.07$ | $0.001$
Table 1: Inverse problem. The relative error $e_{\mathrm{r}}$ and the relative
misfit $\tau$ given by (4.13) for the three reconstructions
$u^{\mathrm{ASI}}$, $u^{\mathrm{TSVD}}$ and $u^{\mathrm{LU}}$ for the inverse
problem (4.12) with $4\;\%$ added noise.

(a) $u^{\mathrm{ASI}}$

(b) $u^{\mathrm{TSVD}}$

(c) $u^{\mathrm{LU}}$

Figure 14: Inverse problem. Solutions obtained by the three different methods
to solve the inverse problem (4.12) with $4\;\%$ added noise.

## Declarations

#### Acknowledgments.

We thank Giovanni Alberti and Gianluca Crippa for their useful comments and
suggestions regarding Appendix A.

#### Funding.

The authors declare that no funds, grants, or other support were received
during the preparation of this manuscript.

#### Data Availability

The numerical results used to confirm the theory and illlustrate its
usefulness were generated with Matlab codes not intended for public
distribution. However, the corresponding author would certainly make them
available upon reasonable request.

##  Appendix A Level sets of distance functions

In the following, for $p_{1},p_{2}\in\mathbb{R}^{d}$,
$\operatorname{dist}(p_{1},p_{2})$ denotes the Euclidean distance

$\operatorname{dist}(p_{1},p_{2})=|p_{1}-p_{2}|$

between $p_{1}$ and $p_{2}$. Here we prove the following theorem:

######  Theorem A.1.

If $A\subset\mathbb{R}^{d}$ is a $\Lambda$-Lipschitz domain with bounded
boundary, and $\delta>0$ sufficiently small, then $A_{\delta}$ given by

$A_{\delta}=\left\\{x\in A:\ \operatorname{dist}(x,\partial
A)>\delta\right\\}$ (A.1)

is also $\Lambda$-Lipschitz.

We say that a domain $A\subset\mathbb{R}^{d}$ with bounded boundary $\partial
A$ is $\Lambda$-Lipschitz, if near its boundary it locally coincides with the
epigraph of a $\Lambda$-Lipschitz function [21]. As a preliminary result we
first show in Theorem A.6 of Section A.1 a similar result for the epigraph of
a Lipschitz function.

###  A.1 Distance functions for Lipschitz graphs

Let $\hat{\mathcal{B}}\subset\mathbb{R}^{d-1}$ be a ball of radius $R$,
$f:\hat{\mathcal{B}}\to\mathbb{R}$ $\Lambda$-Lipschitz, $\widehat{F}$ the
graph of $f$ in $\hat{\mathcal{B}}$, $\mathcal{B}\subset\hat{\mathcal{B}}$ a
ball of radius $r<R$ concentric with $\hat{\mathcal{B}}$, and

$G(\delta)=\left\\{p=(x,y):\ x\in\mathcal{B},\ y>f(x),\
\operatorname{dist}(p,\widehat{F})=\delta\right\\}.$ (A.2)

The setup is illustrated in the left frame of Figure 15. Here we show that
$G(\delta)$ is the graph of a $\Lambda$-Lipschitz function
$g:\mathcal{B}\to\mathbb{R}$.

Figure 15: Left: the graph $\widehat{F}$ of $f$ in $\hat{\mathcal{B}}$ and
$G(\delta)$; right: illustration of the setup of Proposition A.4 in the plane.

For $p\in\mathbb{R}^{d}$, we let $\mathcal{C}_{p}$ denote the open (two-sided)
infinite cone,

$\mathcal{C}_{p}=p+\mathcal{C}_{0},\qquad\mathcal{C}_{0}=\big{\\{}(x,y)\in\mathbb{R}^{d-1}\times\mathbb{R}:\
|y|>\Lambda|x|\big{\\}}.$

We shall use that a function $g:\mathcal{B}\to\mathbb{R}$ is
$\Lambda$-Lipschitz if and only if for every point $p$ in its graph,
$\operatorname{graph}(g)$, we have
$\mathcal{C}_{p}\cap\operatorname{graph}(g)=\emptyset$.

First we show that for every $x\in\mathcal{B}$ and $y>f(x)$ sufficiently
large, the distance of $(x,y)$ to $\widehat{F}$ is greater than $\delta$.

######  Proposition A.2.

If $x\in\mathcal{B}$ and $y>f(x)+\Lambda_{0}\delta$, with
$\Lambda_{0}=\sqrt{1+\Lambda^{2}}$, then

$\operatorname{dist}((x,y),\widehat{F})>\delta;$ (A.3)

especially $(x,y)\notin G(\delta)$.

###### Proof.

Fix $x\in\mathcal{B}$ and $h>h_{0}=\Lambda_{0}\delta$. We show that
$p=(x,f(x)+h)$ satisfies $\operatorname{dist}(p,\widehat{F})>\delta$. If
$\Lambda=0$, then $f$ is constant and the conclusion is clear. Suppose
$\Lambda>0$, and let $\hat{x}\in\hat{\mathcal{B}}$,
$\hat{p}=(\hat{x},f(\hat{x}))$, and $\tau=|f(x)-f(\hat{x})|/\Lambda$. Then,

$\displaystyle\operatorname{dist}(p,\hat{p})^{2}$
$\displaystyle=|x-\hat{x}|^{2}+(f(x)+h-f(\hat{x}))^{2}$ (A.4)
$\displaystyle\geq\frac{1+\Lambda^{2}}{\Lambda^{2}}|f(x)-f(\hat{x})|^{2}-2h|f(x)-f(\hat{x})|+h^{2}$
$\displaystyle={1+\Lambda^{2}}\tau^{2}-2h\Lambda\tau+h^{2}=:\psi(\tau).$

Since the minimum of $\psi$ is achieved in

$\tau_{*}=\frac{h\Lambda}{1+\Lambda^{2}},$ (A.5)

we have

$\operatorname{dist}(p,\hat{p})^{2}\geq\psi(\tau_{*})=h^{2}{1-\frac{\Lambda^{2}}{1+\Lambda^{2}}}=\frac{h^{2}}{1+\Lambda^{2}}>\frac{(1+\Lambda^{2})\delta^{2}}{1+\Lambda^{2}}=\delta^{2}$
(A.6)

which yields the conclusion. ∎

As a result we have that for every $x\in\mathcal{B}$, there exists $y>f(x)$
such that $(x,y)\in G(\delta)$, and, in particular, we obtain an estimate of
$y-f(x)$.

######  Proposition A.3.

For each $x\in\mathcal{B}$, there exists $t\in[\delta,\Lambda_{0}\delta]$,
with $\Lambda_{0}=\sqrt{1+\Lambda^{2}}$, such that

$(x,f(x)+t)\in G(\delta).$

###### Proof.

Let $\rho(t)=\operatorname{dist}((x,f(x)+t),\widehat{F})$, $p=(x,f(x))$, and
$h_{0}=\Lambda_{0}\delta$. Since

$\operatorname{dist}(p,(x,f(x)+\delta))=\delta,$

we have $\rho(\delta)\leq\delta$. In addition, by Proposition A.2,
$\rho(h)>\delta$, for $h>h_{0}$. Since $\rho$ is continuous, there exists
$t\in[\delta,h)$ such that

$\operatorname{dist}((x,f(x)+t),\widehat{F})=\rho(t)=\delta$ (A.7)

Because the above is true of every $h>h_{0}$, we have the conclusion. ∎

The following proposition puts restrictions on $f$ in a neighborhood of a
point $x\in\mathcal{B}$, provided $p=(x,y)\in G(\delta)$. The idea of the
proof is illustrated in the right frame of Figure 15.

######  Proposition A.4.

Let $p=(x,y)\in G(\delta)$, and $\hat{x}\in\hat{\mathcal{B}}$.

  1. 1.

If $|\hat{x}-x|\leq\delta$, then

$f(\hat{x})\leq y-\sqrt{\delta^{2}-|\hat{x}-x|^{2}}\,.$ (A.8)

  2. 2.

If $|\hat{x}-x|>\delta\Lambda/\Lambda_{0}$, where
$\Lambda_{0}=\sqrt{\Lambda^{2}+1}$, then

$f(\hat{x})\leq\Lambda|\hat{x}-x|+y-\Lambda_{0}\delta.$ (A.9)

###### Proof.

1\. Assertion 1 is true because $f$ is continuous, $f(x)<y$, and
$\operatorname{dist}(p,\widehat{F})=\delta$.

2\. We show (A.9) by contradiction. Suppose, that $\hat{x}$ does not satisfy
(A.9). By considering the plane containing the points $p=(x,y)$, $(x,f(x))$
and $(\hat{x},f(\hat{x}))$ (note that they are indeed not collinear), we
reduce the problem to the 2-dimensional case, where we may assume without loss
of generality that $\hat{x}>x$. For $x_{1}=x+\delta\Lambda/\Lambda_{0}$ we
have $|x_{1}-x|=x_{1}-x=\delta\Lambda/\Lambda_{0}<\delta$ and therefore by
(A.8) and $\Lambda_{0}^{2}=\Lambda^{2}+1$,

$f(x_{1})\leq y-\sqrt{\delta^{2}-(x-x_{1})^{2}}=y-\frac{\delta}{\Lambda_{0}}.$
(A.10)

Thus, using $\Lambda_{0}^{2}=\Lambda^{2}+1$ and
$x_{1}=x+\delta\Lambda/\Lambda_{0}$ we obtain

$\displaystyle f(\hat{x})-f(x_{1})$
$\displaystyle>\big{(}\Lambda(\hat{x}-x)+y-\Lambda_{0}\delta\big{)}-{y-\frac{\delta}{\Lambda_{0}}}$
(A.11)
$\displaystyle=\Lambda{\hat{x}-x}-\delta\,\frac{\Lambda_{0}^{2}-1}{\Lambda_{0}}=\Lambda{\hat{x}-x_{1}},$

which contradicts $f$ being $\Lambda$-Lipschitz. ∎

Figure 16: Illustrations for the proof of Lemma A.5; here
$\mathcal{C}_{p}^{+}$ and $\mathcal{C}_{p}^{-}$ denote the upper and lower
halves of the cone $\mathcal{C}_{p}$, respectively.

As a result of Proposition A.4 we have that if $p=(x,y)\in G(\delta)$, then
the graph $\widehat{F}$ of $f$ in $\hat{\mathcal{B}}$ is a subset of

$\displaystyle\widetilde{\mathcal{C}}_{p}$
$\displaystyle=\left\\{(\hat{x},\hat{y})\in\hat{\mathcal{B}}\times\mathbb{R}:\
|\hat{x}-x|\leq\delta\tfrac{\Lambda}{\Lambda_{0}},\ \hat{y}\leq
y-\sqrt{\delta^{2}-|\hat{x}-x|^{2}}\right\\}$ (A.12)
$\displaystyle\quad\bigcup\left\\{(\hat{x},\hat{y})\in\hat{\mathcal{B}}\times\mathbb{R}:\
|\hat{x}-x|>\delta\tfrac{\Lambda}{\Lambda_{0}},\
\hat{y}\leq\Lambda|\hat{x}-x|+y-\Lambda_{0}\delta\right\\}$
$\displaystyle=\left\\{r\in\hat{\mathcal{B}}\times\mathbb{R}:\
\operatorname{dist}\\!\big{(}r,\mathcal{C}_{p}^{+}\big{)}\geq\delta\right\\},$

illustrated in the right frame of Figure 16, where $\mathcal{C}_{p}^{+}$
denotes the upper half of the cone $\mathcal{C}_{p}$. The second equality in
(A.12) can be verified by using the radial symmetry of the sets about the
vertical line $\hat{x}=x$ and then reducing the problem to the 2-dimensional
case, similarly to the proof of Assertion 2 of Proposition A.4. We use this
observation to get the following.

######  Lemma A.5.

If $p\in G(\delta)$, then $\mathcal{C}_{p}\cap G(\delta)=\emptyset$.

###### Proof.

We show separately the two propositions $\mathcal{C}_{p}^{\pm}\cap
G(\delta)=\emptyset$, for the upper and lower parts $\mathcal{C}_{p}^{\pm}$ of
the cone $\mathcal{C}_{p}$.

1\. Consider the lower part $\mathcal{C}_{p}^{-}$ of the cone
$\mathcal{C}_{p}$. Since $p=(x,y)\in G(\delta)$, there exists
$\hat{p}=(\hat{x},f(\hat{x}))\in\widehat{F}$ such that
$\operatorname{dist}(p,\hat{p})=\delta$ and $y>f(\hat{x})$ (by Proposition
A.4). Since $f$ is $\Lambda$-Lipschitz and $\widehat{F}$ is the graph of $f$
in $\hat{\mathcal{B}}$, we have
$\mathcal{C}_{\hat{p}}^{-}\cap\widehat{F}=\emptyset$, and in particular
$\mathcal{C}_{\hat{p}}^{-}$ lies below $\widehat{F}$. However, the lower part
$\mathcal{C}_{p}^{-}$ of $\mathcal{C}_{p}$ is given by
$\mathcal{C}_{p}^{-}=p-\hat{p}+\mathcal{C}_{\hat{p}}^{-}$. Since the length of
$p-\hat{p}$ is $\delta$, we have that every point $r$ in the interior of
$\mathcal{C}_{p}^{-}$ is at a distance of $\delta$ from a point in the
interior of $\mathcal{C}_{\hat{p}}^{-}$, which yields
$\operatorname{dist}(r,\widehat{F})<\delta$ and thus $r\notin G(\delta)$.
Since $r\in\mathcal{C}_{p}^{-}$ is arbitrary, we get $\mathcal{C}_{p}^{-}\cap
G(\delta)=\emptyset$.

2\. Now consider the upper part $\mathcal{C}_{p}^{+}$ of the cone
$\mathcal{C}_{p}$, and let $r\in\mathcal{C}_{p}^{+}$. In this case,
illustrated in the right frame of Figure 16, it is clear that
$\operatorname{dist}(r,\widehat{F})>\delta$, since $r\in\mathcal{C}_{p}^{+}$
and $\widehat{F}\subset\widetilde{\mathcal{C}}_{p}$ given by (A.12). ∎

######  Theorem A.6.

For $\delta>0$, the set $G(\delta)$ is the graph of a $\Lambda$-Lipschitz
function $g:\mathcal{B}\to\mathbb{R}$.

###### Proof.

By Proposition A.3 and Lemma A.5, for each $x\in\mathcal{B}$, there exists a
unique $y$ such that $p=(x,y)\in G(\delta)$. This defines a function
$g:\mathcal{B}\to\mathbb{R}$ such that $G(\delta)$ is its graph. Moreover, by
Lemma A.5, for each $p\in G(\delta)$,
$G(\delta)\cap\mathcal{C}_{p}=\emptyset$, which yields that $g$ is
$\Lambda$-Lipschitz. ∎

###  A.2 Distance functions for Lipschitz domains

For $r>0$, let $B(r)$ denote the open ball in $\mathbb{R}^{d-1}$ of radius $r$
centered at the origin.

###### Proof of Theorem A.1.

Since $A$ is $\Lambda$-Lipschitz and $\partial A$ is bounded, there is a
finite set of pairs $(V_{n},f_{n})$, with $n=1,\ldots,N$, of bounded open
right cylinders $V_{n}$ and functions $f_{n}$ of $d-1$ variables satisfying
the following:

  1. 1.

$\\{V_{n}\\}_{n}$ is a finite open cover of $\partial A$,

  2. 2.

the bases of $V_{n}$ are at a positive distance from $\partial A$,

  3. 3.

$f_{n}$ is $\Lambda$-Lipschitz, and $f_{n}(0)=0$,

  4. 4.

for each $n$, there exists a Cartesian coordinate system $(\xi,\eta)$, with
$\xi\in\mathbb{R}^{d-1}$ and $\eta\in\mathbb{R}$, for which

$V_{n}=B(r_{n})\times(-b_{n},b_{n}),$ (A.13)

for some $r_{n},b_{n}>0$, and

$A\cap\hat{V}_{n}=\left\\{(\xi,\eta):\ \xi\in B(2r_{n}),\
f_{n}(\xi)<\eta<b_{n}\right\\},\qquad\hat{V}_{n}=B(2r_{n})\times(-b_{n},b_{n}).$
(A.14)

Choose $\delta>0$ such that

$\partial A_{\delta}\subset\bigcup_{n=1}^{N}V_{n}$ (A.15)

and for all $n$, with respect to the $n$-th coordinate system $(\xi,\eta)$,
the part of the boundary of $A_{\delta}$ lying in $V_{n}$ coincides with the
set $G_{n}(\delta)=G(\delta)$ given by (A.2) with $f=f_{n}$,
$\mathcal{B}=B(r_{n})$, $\hat{\mathcal{B}}=B(2r_{n})$. By Theorem A.6,
$G_{n}(\delta)$ is the graph of a $\Lambda$-Lipschitz function
$g_{n}:B(r_{n})\to\mathbb{R}$. Thus, the boundary $\partial A_{\delta}$ of
$A_{\delta}$ is covered by a finite collection of open sets $V_{n}$, such that
for each $n$ there exists a coordinate system $(\xi,\eta)$ in which $\partial
A_{\delta}\cap V_{n}$ coincides with the graph of the $\Lambda$-Lipschitz
function $g_{n}$ and $A_{\delta}\cap V_{n}$ lies above $g_{n}$, which yields
the conclusion. ∎

##  Appendix B Estimates in thin sets

We show the following theorem.

######  Theorem B.1.

If $A\subset\Omega$ is a $\Lambda$-Lipschitz domain, then there exists a
constant $C>0$, such that for every sufficiently small $\delta>0$ and every
$v\in H^{1}(\Omega)$,

$\|v\|_{L^{2}(U_{\delta})}^{2}\leq C{\delta^{2}\|\nabla
v\|_{L^{2}(U_{\delta})}^{2}+\delta\|v\|_{H^{1}(A_{\delta})}^{2}},$ (B.1)

where

$U_{\delta}=\left\\{x\in A:\ \operatorname{dist}(x,\partial
A)<\delta\right\\},\qquad A_{\delta}=A\setminus\overline{U_{\delta}}.$ (B.2)

We begin by citing some results of [21] regarding the flattening of Lipschitz
graphs. Let $V$ be a bounded domain such that
$V\subset\mathcal{B}\times\mathbb{R}$, with
$\mathcal{B}\subset\mathbb{R}^{d-1}$ an open ball, and let
$f:\mathcal{B}\to\mathbb{R}$ $\Lambda$-Lipschitz. We define
$Y:V\longrightarrow Y(V)$ by

$Y(x)=(\hat{x},x_{d}-f(\hat{x}))\qquad
x=(\hat{x},x_{d})\in\mathcal{B}\times\mathbb{R}.$ (B.3)

Note that the graph of $f$ is mapped by $Y$ to the flat surface
$\mathcal{B}\times\\{0\\}$. It is easy to verify that

$\bigg{|}\det\frac{\partial Y}{\partial x}\bigg{|}=1,$ (B.4)

and that $Y$ is invertible and

$Y^{-1}(\hat{y},y_{d})=(\hat{y},y_{d}+f(\hat{y})).$ (B.5)

We define

$T:H^{1}(V)\longrightarrow H^{1}(Y(V))\qquad Tu(y)=u\big{(}Y^{-1}(y)\big{)}.$
(B.6)

The operator $T$ is well defined [21], i.e., for every $u\in H^{1}(V)$, $Tu\in
H^{1}(Y(V))$. For any summable $g:V\to\mathbb{R}$, by the area formula we have

$\int_{V}g(x)dx=\int_{Y(V)}g(Y^{-1}(y))dy.$ (B.7)

Therefore,

$\|Tu\|_{L^{2}(Y(V))}=\|u\|_{L^{2}(V)}.$ (B.8)

We also have [21]

$\|\nabla(Tu)\|_{L^{2}(Y(V))}\leq C\|\nabla u\|_{L^{2}(V)},$ (B.9)

where $C$ is independent of $u$ and therefore $T$ is continuous from
$H^{1}(V)$ to $H^{1}(Y(V))$. If

$\Gamma=\left\\{(\hat{x},f(\hat{x})):\
\hat{x}\in\mathcal{B}\right\\}\subset\partial V$

then there exists $C>0$ such that for every $u\in H^{1}(V)$

$\|Tu\|_{L^{2}(Y(\Gamma))}\leq\|u\|_{L^{2}(\Gamma)}\leq
C\|Tu\|_{L^{2}(Y(\Gamma))}.$ (B.10)

Next we derive Poincaré-type inequalities for functions in cylinders bounded
by Lipschitz graphs. Specifically, we are interested in the behavior of the
constants of the inequalities with respect to the height of the cylinder.

######  Lemma B.2.

Let $f:\mathcal{B}\to\mathbb{R}$ be $\Lambda$-Lipschitz and for $h>0$ let

$\mathcal{C}_{h}=\left\\{(\hat{x},x_{d}):\ \hat{x}\in\mathcal{B},\
|x_{d}-f(\hat{x})|<h\right\\},\qquad\Gamma_{h}=\left\\{(\hat{x},f(\hat{x})+h):\
\hat{x}\in\mathcal{B}\right\\}.$

There exists a constant $C>0$, such that for every $h>0$, and $v\in
H^{1}(\mathcal{C}_{h})$,

$C\|v\|_{L^{2}(\mathcal{C}_{h})}^{2}\leq h^{2}\|\nabla
v\|_{L^{2}(\mathcal{C}_{h})}^{2}+h\,\|v\|_{L^{2}(\Gamma_{h})}^{2}.$ (B.11)

###### Proof.

Fix $h>0$ and let $\mathcal{C}=\mathcal{C}_{h}$ and $\Gamma=\Gamma_{h}$. The
estimate for $f\equiv 0$ follows easily from standard estimates for the
smallest eigenvalue $\lambda$ of the problem

$\displaystyle-\Delta u=\lambda u\qquad\text{in}\quad\mathcal{C}$ (B.12)
$\displaystyle\partial_{n}u=-h^{-1}u\qquad\text{on}\quad\Gamma$ (B.13)
$\displaystyle\partial_{n}u=0\qquad\text{on}\quad\partial\mathcal{C}\setminus\Gamma.$
(B.14)

Suppose $f$ is $\Lambda$-Lipschitz. Then
$Y(\mathcal{C})=\mathcal{B}\times(-h,h)$, and
$Y(\Gamma)=\mathcal{B}\times\\{h\\}$. Since $Y(\mathcal{C})$ is a standard
right cylinder, we get

$\|Tv\|_{L^{2}(Y(\mathcal{C}))}^{2}\leq
C{h^{2}\|\nabla(Tv)\|_{L^{2}(Y(\mathcal{C}))}^{2}+h\|Tv\|_{L^{2}(Y(\Gamma))}^{2}}.$
(B.15)

Due to (B.8), (B.9) and (B.10) we get the conclusion. ∎

We now can prove Theorem B.1

###### Proof of Theorem B.1.

Let $v\in H^{1}(\Omega)$. Fix $x\in\partial A$. Since $A$ is bounded and
$\Lambda$-Lipschitz, there exists a cylinder $\mathcal{C}$ and a
$\Lambda$-Lipschitz function $f$ of $d-1$ variables such that $f(0)=0$, the
bases of $\mathcal{C}$ are at a positive distance from $\partial A$, and there
exists a Cartesian coordinate system $(\xi,\eta)$, with
$\xi\in\mathbb{R}^{d-1}$ and $\eta\in\mathbb{R}$, in which

$\mathcal{C}=B(r)\times(-b,b),$ (B.16)

for $r,b>0$, $B(r)\in\mathbb{R}^{d-1}$ the ball of radius $r$ centered at zero
and

$A\cap\mathcal{C}=\left\\{(\xi,\eta):\ \xi\in B(r),\ f(\xi)<\eta<b\right\\}.$
(B.17)

For $\kappa>0$, let $V_{\kappa}$ denote

$V_{\kappa}=\left\\{(\xi,\eta):\ \xi\in B(r),\ 0<\eta-f(\xi)<\kappa\right\\}.$
(B.18)

Choose $\delta_{0}>0$ such that
$\kappa_{0}=2\delta_{0}\sqrt{1+\Lambda^{2}}<b$, and set
$\kappa=\Lambda\delta$, for $\delta<\delta_{0}$. Then, by Proposition A.2 we
have

$U_{\delta}\cap V_{\kappa}=U_{\delta}\cap\mathcal{C}$ (B.19)

and

$\widetilde{V}=\left\\{(\xi,\eta):\ \xi\in B(r),\
\kappa<\eta-f(\xi)<\kappa_{0}\right\\}\subset A_{\delta}.$ (B.20)

Lemma B.2 yields

$C\|v\|_{L^{2}(V_{\kappa})}^{2}\leq\kappa^{2}\|\nabla
v\|_{L^{2}(V_{\kappa})}^{2}+\kappa\|v\|_{L^{2}(\Gamma)}^{2}$ (B.21)

where

$\Gamma=\left\\{(\xi,f(\xi)+\kappa):\ \xi\in B(r)\right\\}.$

Since $\kappa$ is bounded at a positive distance below $\kappa_{0}$, we have

$\|v\|_{L^{2}(\Gamma)}^{2}\leq C\|v\|_{H^{1}(\widetilde{V})}^{2}.$ (B.22)

Combining the above we obtain

$C_{1}\|v\|_{L^{2}(V_{\kappa})}^{2}\leq\kappa^{2}\|\nabla
v\|_{L^{2}(V_{\kappa})}^{2}+\kappa\|v\|_{H^{1}(\widetilde{V})}^{2}$ (B.23)

Since $V_{\kappa}\subset\mathcal{C}\cap A$, we have

$\|\nabla v\|_{L^{2}(V_{\kappa})}^{2}\leq\|\nabla v\|_{L^{2}(\mathcal{C}\cap
A)}^{2}=\|\nabla v\|_{L^{2}(\mathcal{C}\cap U_{\delta})}^{2}+\|\nabla
v\|_{L^{2}(\mathcal{C}\cap A_{\delta})}^{2}$ (B.24)

Substituting this into (B.23) and using $\widetilde{V}\subset\mathcal{C}\cap
A_{\delta}$ yields

$C\|v\|_{L^{2}(V_{\kappa})}^{2}\leq\delta^{2}\|\nabla
v\|_{L^{2}(U_{\delta})}^{2}+\delta(1+\delta)\|v\|_{H^{1}(\mathcal{C}\cap
A_{\delta})}^{2}.$ (B.25)

Since $\partial A$ is compact, we can cover it by a finite number of
neighborhoods $\mathcal{C}$, independent of $\delta$ and thus obtain

$C\|v\|_{L^{2}(U_{\delta})}^{2}\leq\delta^{2}\|\nabla
v\|_{L^{2}(U_{\delta})}^{2}+\delta(1+\delta)\|v\|_{H^{1}(A_{\delta})}^{2}$
(B.26)

which completes the proof ∎

## References

  * [1] Maya de Buhan and Axel Osses.  Logarithmic stability in determination of a 3D viscoelastic coefficient and a numerical example.  Inverse Problems, 26(9):095006, 2010.
  * [2] Maya de Buhan and Marie Kray.  A new approach to solve the inverse scattering problem for waves: combining the TRAC and the adaptive inversion methods.  Inverse Problems, 29(8):085009, 2013.
  * [3] Marcus Grote, Marie Graff-Kray, and Uri Nahum.  Adaptive eigenspace method for inverse scattering problems in the frequency domain.  Inverse Problems, 33:025006, 02 2017.
  * [4] Marcus J. Grote and Uri Nahum.  Adaptive eigenspace for multi-parameter inverse scattering problems.  Computers and Mathematics with Applications, 2019.
  * [5] Daniel H. Baffet, Marcus J. Grote, and Jet Hoe Tang.  Adaptive spectral decompositions for inverse medium problems.  Inverse Problems, 37(2):025006, jan 2021.
  * [6] Martin Burger, Guy Gilboa, and Michael Moeller.  Nonlinear spectral analysis via one-homogeneous functionals: Overview and future prospects.  Journal of Mathematical Imaging and Vision, 56(2):300–319, 2016\.
  * [7] Daniel Cremers, Guy Gilboa, Lina Eckardt, Martin Burger, and Michael Möller.  Spectral decompositions using one-homogeneous functionals.  CoRR, abs/1601.02912, 2016.
  * [8] G. Bellettini, V. Caselles, and M. Novaga.  The total variation flow in $\mathbb{R}^{N}$.  Journal of Differential Equations, 184(2):475 – 525, 2002.
  * [9] Maja de Buhan and Marion Darbas.  Numerical resolution of an electromagnetic inverse medium problem at fixed frequency.  Computers and Mathematics with Applications, 74:3111 – 3128, 2017\.
  * [10] M. Graff, M. J. Grote, F. Nataf, and F. Assous.  How to solve inverse scattering problems without knowing the source term: a three-step strategy.  Inverse Problems, 35:1041001, 2019.
  * [11] Florian Faucher, Otmar Scherzer, and Hélène Barucq.  Eigenvector models for solving the seismic inverse problem for the Helmholtz equation.  Geophysical Journal International, 221(1):394–414, 01 2020.
  * [12] Alfio Quateroni.  Numerical Models for Differential Problems.  Springer, 4 edition, 2008.
  * [13] Lawrence C. Evans and Ronald F. Gariepy.  Measure Theory and Fine Properties of Functions.  CRC Press, 1992.
  * [14] A. Boulkhemair and A. Chakib.  On the uniform poincaré inequality.  Communications in Partial Differential Equations, 32(9):1439–1447, 2007.
  * [15] Mario Bertero, Patrizia Boccacci, and Christine De Mol.  Introduction to Inverse Problems in Imaging.  CRC press, 2021.
  * [16] Dirk Pieter Laurie.  Algorithm 584: Cubtri: Automatic cubature over a triangle.  ACM Transactions on Mathematical Software (TOMS), 8(2):210–218, 1982.
  * [17] Gary S. Martin, Robert Wiley, and Kurt J. Marfurt.  Marmousi2: An elastic upgrade for marmousi.  The leading edge, 25(2):156–166, 2006.
  * [18] AGL elastic marmousi.  https://wiki.seg.org/wiki/AGL_Elastic_Marmousi.
  * [19] Curtis R Vogel.  Computational Methods for Inverse Problems.  SIAM, 2002.
  * [20] Per Christian Hansen.  Discrete Inverse Problems: Insight and Algorithms.  SIAM, 2010.
  * [21] Zhonghai Ding.  A proof of the trace theorem of sobolev spaces on lipschitz domains.  Proceedings of the American Mathematical Society, 124(2):591–600, 1996.