Ill-Posed Problems: From Linear to Nonlinear and Beyond

Abstract

Inverse (ill-posed) problems appear in many applications such as medical imaging, astronomy, seismic imaging, nondestructive testing, signal processing, etc. Typically, these problems cannot be solved by conventional methods as they suffer from instabilities and regularization is required. This chapter has evolved from a mini-course taught at the Summer School on Applied Harmonic Analysis and Machine Learning at the University of Genoa in 2019. It offers an overview of the theory of inverse problems and discusses three ill-posed problems that have been studied rather recently in the literature: limited data reconstruction in computerized tomography, phase retrieval, and image classification with DNNs. The selection highlights that for modern problems, the usefulness of standard theory of regularization can be limited.

1 Introduction

In many applications in science and engineering, one seeks to recover an object from some acquired measurements. Such reconstruction problems are often vulnerable to small changes in the measured data, in the sense that slight perturbations in the data can lead to large deviations in the reconstructed objects. Such a property is of course highly unpleasant, as it makes the reconstruction unreliable. This observation has led to studying so-called inverse problems and to developing the theory of regularization that aims at introducing reconstruction algorithms that are sensitive to these instabilities and that aim at extracting information as stably as possible from such unstable systems.

For problems that can be modeled with a linear forward operator, the theory of linear inverse problems is quite developed. The unboundedness of the inverse (or generalized inverse) can be nicely characterized by the closedness of the range of the forward operator. When the forward operator has a singular value decomposition, the instabilities can often be quantified, as we show in the example of the truncated Hilbert transform (arising in limited data computerized tomography) in Sect. 3. Moreover, regularization theory is in many cases very effective for linear problems. It can give guarantees for convergence (and convergence rates) of algorithms, when they are suitably chosen so that regularization can be guaranteed. Regularization is, in principle, tied to assuming prior knowledge on the solution and, therefore, to searching for solutions only in a restricted set. This way, we also demonstrate how regularization can be guaranteed for the truncated Hilbert transform in Sect. 4.2.

When the underlying problem is nonlinear, one can still (to some extent) describe unboundedness of the inverse problem and suggest regularization methods. However, as the example of phase retrieval demonstrates (see Sect. 6), even if the inverse is bounded, the nonlinear case is very different: if the inverse is not uniformly bounded, one will in practice still witness instabilities in the reconstruction. The problem of phase retrieval is very particular in that regularization is not effective for stable recovery from phaseless measurements. However, one can give up on the strong notion of unique reconstruction to achieve some sort of stable recovery that we call atoll function reconstruction.

The last problem we visit in Sect. 7 is the one of image classification with deep neural networks (DNNs). The network is obtained by training it on a set of test images for which the correct labels are provided. The DNN should then perform the task of correctly classifying objects in images it has not seen during training. For this problem, we do not even have a rigorous mathematical formulation of the forward operator at hand, at least not one that allows for a useful analysis. However, we witness instabilities in the form of so-called adversarial examples. One can construct algorithms that find, for most correctly classified images, a slightly perturbed version that the neural network will no longer classify correctly. While some remedies have been suggested in the form of altering the training process in form of adversarial training, these methods still do not give rise to robust classifiers, as one can think of other ways to “fool” the network, such as slightly deforming the images.

This chapter is organized as follows: in Sect. 2 we provide an introduction to linear inverse problems. In Sect. 3 we introduce the problem of limited data computerized tomography and describe the truncated Hilbert transform as the resulting linear forward operator. This includes the derivation of the SVD of the truncated Hilbert transform as well as the asymptotic behavior of its singular values. The theory of regularization of linear problems is the subject of Sect. 5, in which results on the regularization of the truncated Hilbert transform are given as well. Nonlinear problems are then discussed in Sect. 6, with Gabor phase retrieval as an example. Finally, we present the problem of image classification in Sect. 7.

2 Linear Inverse Problems

A study of ill-posed problems naturally begins with linear operators as the theory for the linear case is rather complete. We will therefore follow this path and refer to the classical book of Engl et al. [21] for further details. In Sect. 3, we will then analyze a specific linear problem using the theory of ill-posed problems combined with Sturm–Liouville theory and Wentzel–Kramers–Brillouin approximations. When the underlying operator is nonlinear, the theory is by far less straightforward. However, the main results for nonlinear inverse problems are inspired by the linear case.

In what follows, $T:X \rightarrow Y$ will always denote a bounded linear operator from X to Y, where X and Y are separable Hilbert spaces. The range and nullspace of an operator will be denoted by $\mathcal {R}$ and $\mathcal {N}$, respectively. We take T to be the forward operator of the inverse problem in question and follow the classical definition by Hadamard: a problem is well-posed if it satisfies the following criteria.

Definition 1

(Hadamard’s well-posedness) The inversion of $T:X\rightarrow Y$ is said to be well-posed if the following properties hold:

• Existence: For all $g \in Y$, there exists $f \in X$ such that $T f = g$, i.e.,

  $$\begin{aligned} \mathcal {R}(T)=Y. \end{aligned}$$

  (1)

• Uniqueness: For all $g \in Y$, the solution is unique, i.e.,

  $$\begin{aligned} \mathcal {N}(T)=\{0\}. \end{aligned}$$

  (2)

• Stability: The solution depends continuously on the data, i.e.,

  $$\begin{aligned} T^{-1} \in \mathcal {L}(Y,X). \end{aligned}$$

  (3)

Here, $\mathcal {L}(Y,X)$ denotes the set of all bounded linear transforms mapping from Y to X.

If at least one of the three conditions is violated, the problem is said to be ill-posed.

Non-uniqueness can be undesirable, for instance, in reconstruction problems where one is interested in recovering a signal, an image, an electron density, etc. from some acquired measurements. If the same set of measurements can be created by two different objects, then this is problematic for the reconstruction problem. We will address the question of uniqueness in the reconstruction problems that will be discussed in Sects. 3 and 6. However, if the inverse problem in question is the identification of system parameters in a PDE so that a given state is reached, then having more than one candidate parameter set is of course less of an obstruction (though some notion of uniqueness might still be desirable for the numerical solution that involves an optimization problem).

The lack of stability creates serious numerical issues. Acquired measurements are never exact and can only be given up to a certain accuracy. No stable dependence of the solution on the data means that straightforward calculations of the reconstruction will, in principle, be unreliable, as they might be arbitrarily far from the ground truth. The theory of regularization aims at tackling this issue: the idea is to extract information as stably as possible, meaning that the guarantees that one will be able to give, will depend on the noise level, i.e., on the accuracy of the measurements.

In case the first property (existence) is violated, i.e., if $Tf=g$ is not solvable for a given right-hand side $g \not \in \mathcal {R}(T)$, one can relax the notion of a solution. Instead of a classical solution, one can search for a generalized solution. To introduce this concept, we first start with ensuring existence by simply searching for the “best fit”.

Definition 2

(Least-squares solution) An element $f \in X$ is called a least-squares solution for $Tf=g$ if

$$ \Vert Tf-g\Vert _Y \le \Vert Th-g\Vert _Y, \quad \forall \, h \in X. $$

To further characterize least-squares solutions, we let Q be the orthogonal projection of Y on $\overline{\mathcal {R}(T)}$, i.e.,

$$ \langle Q g, u \rangle _Y = \langle g, u \rangle _Y, \quad \forall \, g \in Y, \ \forall \, u \in \overline{\mathcal {R}(T)}. $$

The following facts can then be stated.

$$ \Vert Qg-g\Vert _Y \le \Vert u-g\Vert _Y, \quad \forall \, u \in \overline{\mathcal {R}(T)}, \qquad \text{(minimality } \text{ property) } $$

and

$$\begin{aligned} Qg-g \in \mathcal {R}(T)^\perp . \end{aligned}$$

(4)

In addition, we also recall a standard result.

Theorem 3

Let $T:X \rightarrow Y$ be a bounded linear operator between Hilbert spaces X and Y. Then,

$$\begin{aligned} \mathcal {N}(T)= & {} \mathcal {R}(T^*)^\perp , \end{aligned}$$

(5)

$$\begin{aligned} \overline{\mathcal {R}(T)}= & {} \mathcal {N}(T^*)^\perp . \end{aligned}$$

(6)

The above properties enable us to make the following link between least-squares solutions, orthogonal projections, and solutions to the normal equation.

Theorem 4

Let $g \in Y$, $f \in X$ and $T \in \mathcal {L}(X,Y)$. The following are equivalent:

$$\begin{aligned} Tf= & {} Qg, \end{aligned}$$

(7)

$$\begin{aligned} \Vert Tf-g\Vert _Y\le & {} \Vert Th-g\Vert _Y, \quad \forall \, h \in X, \end{aligned}$$

(8)

$$\begin{aligned} T^* T f= & {} T^* g. \end{aligned}$$

(9)

Proof

We show that (7) $\Rightarrow$ (8) $\Rightarrow$ (9) $\Rightarrow$ (7). The first implication is established by employing (4):

$$\begin{aligned} \Vert Th-g\Vert _Y^2&= \Vert Th-Qg\Vert _Y^2 + \Vert Qg-g\Vert _Y^2, \end{aligned}$$

(10)

$$\begin{aligned}&= \Vert Th-Qg\Vert _Y^2 + \Vert Tf-g\Vert _Y^2, \end{aligned}$$

(11)

$$\begin{aligned}&\ge \Vert Tf-g\Vert _Y^2. \end{aligned}$$

(12)

The second implication can be established as follows: first, we note that since $Qg \in \overline{\mathcal {R}(T)}$, there exists a sequence $(f_n)_{n \in \mathbb {N}} \subset X$ s.t. $T f_n \rightarrow Qg$ as $n \rightarrow \infty$. Hence, by assumption, Eq. (8) yields

$$ \Vert Qg-g\Vert _Y^2 = \lim _{n \rightarrow \infty } \Vert T f_n - g\Vert _Y^2 \ge \Vert T f - g\Vert _Y^2. $$

Together with (4), this then implies

$$\begin{aligned} \Vert Tf-g\Vert _Y^2&= \Vert Tf-Qg\Vert _Y^2 + \Vert Qg-g\Vert _Y^2, \\&\ge \Vert Tf-Qg\Vert _Y^2 + \Vert Tf-g\Vert _Y^2. \end{aligned}$$

Thus, $Tf=Qg$. Moreover,

$$ Tf-g = Qg-g \in \mathcal {R}(T)^\perp = \mathcal {N}(T^*). $$

We can thus conclude that

$$ T^*(Tf-g) = 0. $$

Part (9) $\Rightarrow$ (7) can be seen as follows: The assumption that $Tf-g \in \mathcal {N}(T^*) = \mathcal {R}(T)^\perp$ implies

$$ Q(Tf-g) = 0. $$

Consequently,

$$ 0 = Q(Tf-g) = QTf-Qg = Tf-Qg, $$

and, hence, $Tf = Qg$.    $\square$

The above theorem is extremely useful, as it states that least-squares solutions are nothing else than solutions to the normal equation $T^*Tf=T^*g$. Also, they are equivalent to solutions of $Tf=Qg$, i.e., the original equation with right-hand side projected on $\overline{\mathcal {R}(T)}$. With this at hand, one can make a statement about the existence of least-squares solutions:

Corollary 5

Let L(g) denote the set of least-squares solutions to right-hand side g, i.e.,

$$ L(g):= \{ f \in X: T^* T f = T^* g \}. $$

Then, the following hold:

• (i) L(g) is nonempty if and only if $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp .$

• (ii) If $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp ,$ then L(g) is a nonempty, closed, and convex subset of X.

Proof

Part (i): First, if $f \in L(g)$, then $T^*Tf = T^*g$, and hence

$$ Tf-g \in \mathcal {N}(T^*) = \mathcal {R}(T)^\perp . $$

Decomposing g as $g = Tf + (g-Tf)$, it then follows that $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp$. To show the other direction, we remark that for $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp$, a splitting $g=g_1+g_2$ with $g_1 \in \mathcal {R}(T), g_2 \in \mathcal {R}(T)^\perp$ is unique with the only option for $g_1$ to be $g_1=Qg$. The property that $g_1 \in \mathcal {R}(T)$ means the existence of an element $f \in X$ such that $g_1=Tf$, and hence

$$ Qg=Tf. $$

By Theorem 4, we can thus conclude that this element f is a least-squares solution, i.e., $f \in L(g)$.

Part (ii): Nonemptiness is already established in Part (i). To show convexity, we proceed in the standard way of considering $f, f' \in L(g)$ and

$$ h:= tf' + (1-t)f $$

for arbitrary $t \in [0,1]$. By Theorem 4, we have

$$\begin{aligned} T^* T f= & {} T^* g,\\ T^* T f'= & {} T^* g. \end{aligned}$$

Linearity of T then yields

$$ T^* T h = t T^* T f' + (1-t) T^* T f = t T^* g + (1-t) T^* g = T^* g, $$

i.e., $h \in L(g)$.

To show that L(g) is closed, we consider a sequence $(f_n)_{n \in \mathbb {N}} \subset L(g)$ with $f_n \rightarrow f$ as $n \rightarrow \infty$. Closure of X implies $f \in X$. Moreover, since each $f_n$ is in L(g),

$$ \Vert Tf-g\Vert _Y = \lim _{n \rightarrow \infty } \Vert T f_n - g\Vert _Y \le \Vert Th -g \Vert _Y, \quad \forall \, h \in X. $$

Thus, $f \in L(g)$.    $\square$

By its definition, the least-squares solution is not necessarily unique. For if $\mathcal {N}(T) \ne \{0\}$ and $\overline{f}$ is a least-squares solution, then also any $\overline{f} + f_0$ with $f_0 \in \mathcal {N}(T)$ is a least-squares solution as well. This implies that if $\mathcal {N}(T) \ne \{0\},$ then there are infinitely many least-squares solutions. We will later characterize the set of least-squares solutions. For now, we are interested in a notion of solution that enjoys uniqueness. One popular choice is to pick the least-squares solution with minimal norm and this is sometimes referred to as best approximate solution.

Definition 6

(Best approximate solution) An element $f \in X$ is called best approximate solution if it is a least-squares solution, i.e., $f \in L(g)$, and it has minimal norm, i.e.,

$$ \Vert f\Vert _X = \inf \{ \Vert h\Vert _X: h \in L(g)\}. $$

Corollary 7

If $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp$, then the best approximate solution to $Tf=g$ is unique.

This is a direct consequence of the convexity of L(g) stated in Corollary 5. Note also that $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp$ is the only interesting case, since otherwise L(g) is empty.

2.1 The Moore–Penrose Generalized Inverse

So far, the previous discussion has been centered around restoring the notions of existence and uniqueness and the best approximate solution, or minimum-norm least-squares solution, is a candidate that fulfills these requirements. We intend to continue this discussion in an operator-theoretic way. To do so requires the introduction of the Moore–Penrose generalized inverse, which is the map from $g \in \mathcal {R}(T) \oplus \mathcal {R}(T)^\perp$ to the unique best approximate solution, i.e., to the element in L(g) with minimal norm. One way to define the Moore–Penrose generalized inverse $T^\dagger$ of T is to introduce the invertible restriction $\widetilde{T}:= T|_{\mathcal {N}(T)^\perp }$ of T.

Definition 8

(Moore–Penrose generalized inverse) For $T \in \mathcal {L}(X,Y)$, its Moore–Penrose generalized inverse is defined as the unique linear extension of $\widetilde{T}^{-1}$ to

$$ \mathcal {D}(T^\dagger ):=\mathcal {R}(T) \oplus \mathcal {R}(T)^\perp $$

with

$$ \mathcal {N}(T^\dagger ) = \mathcal {R}(T)^\perp . $$

Thus, the Moore–Penrose generalized inverse maps each $g \in \mathcal {D}(T^\dagger )$ to $f \in L(g)$ with minimal norm, $f:= T^\dagger g$. We record a few basic properties of $T^\dagger$.

Corollary 9

Let $T^\dagger$ be the Moore–Penrose generalized inverse of $T \in \mathcal {L}(X,Y)$. Then,

• (i) the domain $\mathcal {D}(T^\dagger )$ is dense in Y. Moreover, $\mathcal {R}(T)$ is closed if and only if $\mathcal {D}(T^\dagger )=Y.$

• (ii) If $\mathcal {R}(T)$ is closed and $T^{-1}$ exists, it follows that

  $$ T^\dagger |_{\mathcal {R}(T)} = T^{-1}. $$

• (iii) $\mathcal {R}(T^\dagger ) = \mathcal {N}(T)^\perp \quad (=\overline{\mathcal {R}(T^*)})$.

• (iv) $T^\dagger$ is linear.

• (v) For $g \in \mathcal {D}(T^\dagger )$, $T^\dagger g$ is the unique element in $L(g) \cap \mathcal {N}(T)^\perp$.

Proof

Except for item (iii), the statements are straightforward consequences of the definition of $T^\dagger$ and the results we have collected so far about least-squares solutions. To show item (iii), let $h \in \mathcal {R}(T^\dagger )$ so that there exists an element $g \in \mathcal {D}(T^\dagger )$ with $T^\dagger g = h$. By definition, g can be decomposed as $g=g_1+g_2$ with $g_1 \in \mathcal {R}(T)$ and $g_2 \in \mathcal {R}(T)^\perp = \mathcal {N}(T^\dagger )$. Thus, by linearity of $T^\dagger$,

$$ h = T^\dagger g = T^\dagger g_1 + T^\dagger g_2 = T^\dagger g_1 = \widetilde{T}^{-1} g_1. $$

Hence, $h \in \mathcal {R}(\widetilde{T}^{-1}) = \mathcal {N}(T)^\perp$ so that overall, $\mathcal {R}(T^\dagger ) \subseteq \mathcal {N}(T)^\perp .$ On the other hand, suppose that $h \in \mathcal {N}(T)^\perp$. Then, by definition of $\widetilde{T}$, $\widetilde{T} h = T h$. This implies

$$ h = \widetilde{T}^{-1} T h = T^\dagger T h, $$

so that $h \in \mathcal {R}(T^\dagger )$ and hence $\mathcal {N}(T)^\perp \subseteq \mathcal {R}(T^\dagger )$.    $\square$

The first item in the above corollary states that $\mathcal {D}(T^\dagger )$ is dense in Y. Note also, that by item (i) in Corollary 5, L(g) is empty when $g \not \in \mathcal {D}(T^\dagger )$, so that in this case no least-squares solution exists.

We emphasize that in the discussion about generalized solutions and inverses we have not addressed the question of stability at all. In fact, while the Moore–Penrose generalized inverse restores uniqueness, it does not restore stability of the inversion problem. Boundedness (and hence continuity) of $T^\dagger$ can, however, be characterized as follows:

Theorem 10

Let $T^\dagger$ be the Moore–Penrose generalized inverse of $T \in \mathcal {L}(X,Y)$. Then, $T^\dagger$ is bounded if and only if $\mathcal {R}(T)$ is closed.

Proof

The proof is based on establishing that the graph of $T^\dagger$ is closed. See, e.g., Proposition 2.4 and its proof in [21] for the full argument.    $\square$

Remark 11

Since the closedness of $\mathcal {R}(T)$ is equivalent to $\mathcal {D}(T^\dagger ) = Y$ (cf. Corollary 9, item (i)), one further has

$$ \mathcal {D}(T^\dagger ) = Y \Longleftrightarrow T^\dagger \text{ is } \text{ bounded }. $$

In terms of Hadamard’s well-posedness criteria, this amounts to equivalence of existence and stability in the least-squares solution sense.

2.2 Compact Operators

In inverse problems, an important class of bounded linear transforms $T \in \mathcal {L}(X,Y)$ is compact operators. On one hand, they appear frequently, e.g., integral operators are typically compact under some suitable assumptions on the kernel. On the other hand, they are inherently ill-posed, as we will see in this section.

Definition 12

(Compact operator) Let $K:X \rightarrow Y$ be a linear operator. Then, K is said to be compact if for any bounded set $B \subset X$, the closure of its image $\overline{K(B)}$ is compact.

Alternatively, compact operators can be characterized as follows.

Theorem 13

A linear operator $K:X \rightarrow Y$ is compact if and only if for any bounded sequence $(f_n)_{n \in \mathbb {N}} \subset X$, the sequence $(K f_n)_{n \in \mathbb {N}}$ has a convergent subsequence.

We remark that it is easily shown that compact operators are always bounded, i.e., $K \in \mathcal {L}(X,Y)$. Some useful properties of compact operators are the following.

Lemma 14

Let $K_1 \in \mathcal {L}(X,Y)$ and $K_2 \in \mathcal {L}(Y,Z)$. If at least one of the two operators is compact, then $K_1 K_2$ is also compact.

Lemma 15

(Identity operator) The identity operator id:$X \rightarrow X$ is compact if and only if X is finite dimensional.

The range of a compact operator has the following special property.

Theorem 16

(Range of compact operators) Let $K \in \mathcal {L}(X,Y)$ be a compact operator. Then, its range $\mathcal {R}(K)$ is closed if and only if it is finite dimensional.

The proof can be found in Proposition 2.7 of [21] but we still provide it for the sake of completeness and illustration:

Proof

Clearly, if $\mathcal {R}(K)$ is finite dimensional, then it is closed. For the other direction, note that the operator

$$\widetilde{K}:=K|_{\mathcal {N}(K)^\perp }: \mathcal {N}(K)^\perp \rightarrow \mathcal {R}(K)$$

is bijective, linear, and compact. If $\mathcal {R}(K)$ is closed, then the inverse mapping theorem implies that $\widetilde{K}^{-1}$ is bounded. Hence, by Lemma 14, also $\widetilde{K} \widetilde{K}^{-1} = \text{ Id }|_{\mathcal {R}(K)}$ is compact. Thus, by Lemma 15, $\mathcal {R}(K)$ is finite dimensional.    $\square$

In view of Theorem 10, the above result implies that for compact operators, the Moore–Penrose generalized inverse $K^\dagger$ is unbounded when the range of K is infinite dimensional:

Corollary 17

Let $K \in \mathcal {L}(X,Y)$ be compact and let $K^\dagger$ be its generalized inverse. Then, $K^\dagger$ is bounded if and only if $\mathcal {R}(K)$ is finite dimensional.

This property of inherent instability for the inversion of compact operators can be seen more explicitly when the singular value decomposition (SVD) is utilized. Since it will be useful in Sect. 3, we will start with a reminder on the spectrum of an operator $T \in \mathcal {L}(X)$ (cf. Sect. VI.3 in [42]).

Definition 18

(Resolvent set and spectrum) For $T \in \mathcal {L}(X),$ the resolvent set $\rho (T)$ is defined as

$$ \rho (T):= \{ \lambda \in \mathbb {C}: \lambda \text{ Id }-T \text{ is } \text{ bijective, } R_\lambda (T):=(\lambda \text{ Id }-T)^{-1} \text{ is } \text{ bounded }\}. $$

The operator $R_\lambda (T)$ is called the resolvent of T at $\lambda$. The spectrum $\sigma (T)$ of T is defined as $\sigma (T):=\mathbb {C} \backslash \rho (T)$.

In fact, the boundedness of the inverse does not have to be asked for explicitly: if $\lambda \text{ Id }- T$ is bijective, then by the inverse mapping theorem its inverse is bounded (note that $\lambda \text{ Id }-T$ is linear). For compact operators $K: X \rightarrow X$, the spectrum can be rather elegantly described as the following properties hold (cf. Theorems VI.15, VI.16, and VI.17 in [42]):

Theorem 19

(Riesz–Schauder theorem) The spectrum $\sigma (K)$ of a compact operator $K \in \mathcal {L}(X)$ is at most countable with 0 as the only possible accumulation point. Every $\lambda \in \sigma (K) \backslash \{0\}$ is an eigenvalue of K.

Remark 20

If X is infinite dimensional, then $0 \in \sigma (K)$. For if X is infinite dimensional, then K being bijective implies $\mathcal {R}(K) = X$ and hence $\mathcal {R}(K)$ is closed. From this, however, and Theorem 16 we can deduce that $\mathcal {R}(K)$ and, hence X, is finite dimensional, which is a contradiction. Therefore, K cannot be a bijection, and thus $0 \in \sigma (K)$.

Theorem 21

(Hilbert–Schmidt theorem) Let $K:X \rightarrow X$ be a compact, self-adjoint operator. Then, there exist a sequence of nonzero eigenvalues $(\lambda _n)_{n=1}^N \subset \mathbb {R}$ and a sequence $(u_n)_{n=1}^N \subset X$ such that

$$ K u_n = \lambda _n u_n, $$

where $(u_n)_{n=1}^N$ is an orthonormal basis of $\overline{\mathcal {R}(K)}$ and $N=\text{ rank }(K)$. If $N=\infty$, then $\lambda _n \rightarrow 0$ as $n \rightarrow \infty$.

Theorem 22

Let $K:X \rightarrow Y$ be a compact operator. Then, there exist sequences $(\sigma _n)_{n=1}^N \subset \mathbb {R_+}$, $(u_n)_{n=1}^N \subset X$ and $(v_n)_{n=1}^N \subset Y,with$ $N \in \mathbb {N} \cup \infty ,$ such that

$$\begin{aligned} K u_n= & {} \sigma _n v_n, \\ K^* v_n= & {} \sigma _n u_n. \end{aligned}$$

The system $(u_n)_{n=1}^N$ is an orthonormal basis of $\overline{\mathcal {R}(K^*)}= \mathcal {N}(K)^\perp$, and $(v_n)_{n=1}^N$ is an orthonormal basis of $\overline{\mathcal {R}(K)}$. If $N=\infty$, then $\sigma _n \rightarrow 0$ as $n \rightarrow \infty$. The operator K takes on the representation

$$ K = \sum _{n=1}^N \sigma _n \langle \cdot , u_n\rangle _X v_n. $$

The numbers $\sigma _n>0$ are called singular values of K and the system $(\sigma _n,u_n,v_n)$ is said to form the singular value decomposition (SVD) of K.

As we have seen before, the generalized solution may not always exist. More precisely, it only exists when $g \in \mathcal {D}(K^\dagger )$ (cf. Corollary 5). For compact operators, the existence of the generalized solution can be characterized with the Picard criterion (we will always assume $N=\infty$ in what follows, as this is the interesting case in which the generalized inverse is unbounded (cf. Corollary 17)).

Theorem 23

(Picard criterion). Let $K \in \mathcal {L}(X,Y)$ be a compact operator. Then,

$$\begin{aligned} g \in \mathcal {D}(K^\dagger ) \Longleftrightarrow \sum _{n=1}^\infty \frac{|\langle g,v_n\rangle _Y|^2}{\sigma _n^2} < \infty . \end{aligned}$$

(13)

Proof

• “$\Longrightarrow$”: Since $g \in \mathcal {D}(K^\dagger )$, we can decompose it into $g=g_1+g_2$ with $g_1=Kf_1 \in \mathcal {R}(K)$, $g_2 \in \mathcal {R}(K)^\perp$, for some $f_1 \in X$. Then, noting that $v_n \in \mathcal {R}(K)$, one can deduce

  $$ \langle g,v_n \rangle _{Y}= \langle g_1+g_2,v_n \rangle _{Y} = \langle g_1, v_n \rangle _{Y} = \langle f_1, K^* v_n \rangle _{X} = \sigma _n \langle f_1, u_n \rangle _{X}. $$

  Thus,

  $$ \sum _{n=1}^\infty \frac{|\langle g,v_n\rangle _Y|^2}{\sigma _n^2} = \sum _{n=1}^\infty |\langle f_1, u_n \rangle _{X}|^2 \le \Vert f_1\Vert _X^2 < \infty , $$

  where we have used that $(u_n)_{n \in \mathbb {N}}$ is an orthonormal basis of $\mathcal {N}(K)^\perp$, a closed subspace of X.

• “$\Longleftarrow$”: By assumption, the sequence $\left( \sigma _n^{-1} \langle g, v_n \rangle _Y \right) _{n \in \mathbb {N}}$ is in $\ell ^2({\mathbb N}).$ Thus, the Riesz–Fischer theorem yields that f defined as

  $$ f:= \sum _{n=1}^\infty \sigma _n^{-1} \langle g,v_n \rangle _Y u_n $$

  is an element in X.

  The orthogonal projection Q onto $\overline{\mathcal {R}(K)}$ can be expressed with the orthonormal basis $(v_n)_{n \in \mathbb {N}}$ of $\overline{\mathcal {R}(K)}$:

  $$ Q = \sum _{n=1}^\infty \langle \cdot , v_n \rangle _Y v_n. $$

  With this, one can deduce

  $$ K f = \sum _{n=1}^\infty \sigma _n^{-1} \langle g,v_n \rangle _Y K u_n = \sum _{n=1}^\infty \langle g, v_n \rangle _Y v_n = Qg. $$

  Thus, $Qg \in \mathcal {R}(K)$, and hence $g \in \mathcal {R}(K) \oplus \mathcal {R}(K)^\perp = \mathcal {D}(K^\dagger )$.

   $\square$

With the singular value decomposition of K at hand, one can even give an explicit representation for the Moore–Penrose generalized inverse $K^\dagger$.

Theorem 24

Let $K \in \mathcal {L}(X,Y)$ be compact with SVD $(\sigma _n, u_n, v_n)_{n \in \mathbb {N}}$. Then, the operator $K^\dagger : \mathcal {D}(K^\dagger ) \rightarrow \mathcal {N}(K)^\perp$ can be represented as

$$ K^\dagger = \sum _{n=1}^\infty \frac{\langle \cdot , v_n\rangle _Y}{\sigma _n} u_n. $$

Proof

Let $g \in \mathcal {D}(K^\dagger )$. Then, the Picard criterion holds and

$$ f:= \sum _{n=1}^\infty \sigma _n^{-1} \langle g,v_n \rangle _Y u_n \in X, $$

with $Kf=Qg$ as derived in the previous proof. Thus, by Theorem 4, $f \in L(g)$. In view of item 5 of Corollary 9, it remains to show that $f \in \mathcal {N}(K)^\perp$. This follows immediately from the above definition of f and $(u_n)_{n \in \mathbb {N}}$ spanning $\mathcal {N}(K)^\perp$.    $\square$

Remark 25

• (i) For compact operators, the fact that a generalized solution does not always exist is characterized by Picard’s criterion: it only exists if $(\langle g,v_n\rangle _{Y}/\sigma _n)_{n \in \mathbb {N}}$ decays fast enough. Note that here $\sigma _n \rightarrow 0$ as $n \rightarrow \infty$. Thus, Theorem 23 links the existence of the generalized solution to the decay of the coefficients $\langle g, v_n \rangle _{Y}$ with respect to the singular values $\sigma _n$. The faster the singular values decay, the more rapid the decay of the coefficients of g has to be in order for a solution to exist.

• (ii) The Picard criterion also reveals that while error components corresponding to large singular values $\sigma _n$ are harmless, error components corresponding to small $\sigma _n$ get amplified and cause severe numerical issues.

• (iii) Typically, the ill-posedness of compact operator equations is characterized by the decay rate of $(\sigma _n)_{n \in \mathbb {N}}$. A problem is said to be mildly ill-posed if $(\sigma _n)_{n \in {\mathbb N}}$ decays algebraically. When the singular values decay exponentially, the problem is said to be severely ill-posed.

Example 26

We conclude the treatment of compact operators by featuring a concrete example that we borrow from Sect. 1.5 in [21]. The backward heat equation can be described as assuming a final temperature at time $T=1$:

$$ h(x):=u(x,1), \quad x \in [0,\pi ], \ h(0)=h(\pi )=0, $$

where the temperature u(x, t) at position $x \in [0,\pi ]$ and time $t \ge 0$ is governed by

$$ \frac{\partial u}{\partial t}(x,t) = \frac{\partial ^2 u}{\partial x^2}(x,t), $$

with homogenous Dirichlet boundary conditions

$$ u(0,t) = u(\pi ,t)=0, \quad t \ge 0. $$

For the backward heat equation, we then aim at determining the initial temperature u(x, 0), $x \in [0,\pi ]$. One can find that the corresponding forward operator is an integral operator of the first kind:

$$ h(x) = \frac{2}{\pi } \sum _{n=1}^\infty \int _0^\pi u(\tau ,0) \sin (n\tau ) d\tau e^{-n^2} \sin (nx). $$

With the kernel of the integral operator thus given explicitly, one can derive the SVD of the operator which is $(e^{-n^2}, \sqrt{2/\pi } \sin (nx), \sqrt{2/\pi } \sin (nx))_{n \in \mathbb {N}}$. Thus, the inverse problem is severely ill-posed (since $\sigma _n = e^{-n^2}$).

We further note that the singular functions $(\sqrt{2/\pi } \sin (nx))_{n \in \mathbb {N}}$ form an orthonormal basis of $L^2([0,\pi ])$ so that $\mathcal {R}(K)$ is dense in $L^2([0,\pi ])$ and $\mathcal {D}(K^\dagger ) = \mathcal {R}(K)$. Applying the Picard criterion then yields that the backward heat equation is (uniquely) solvable if and only if

$$ \sum _{n=1}^\infty e^{2n^2} |h_n|^2 < \infty , $$

where $h_n:= \sqrt{2/\pi } \int _0^\pi f(\tau ) \sin (n\tau ) d\tau .$ In other words, a solution exists if and only if the Fourier coefficients of the final temperature h decay rapidly (much faster than $e^{-n^2}$).

2.3 General Bounded Linear Transforms

To conclude this section, we complete the discussion by noting that more generally than for compact operators, the spectrum of $T^*T$ reveals the stability properties of the inverse problem with forward operator $T \in \mathcal {L}(X,Y)$. A self-adjoint bounded linear operator $A:X \rightarrow X$ is completely characterized by the spectral theorem (see Chap. VII in [42] for a detailed treatment). It can be derived by drawing on the functional calculus for continuous functions f which allows to meaningfully define the operator $f(A) \in \mathcal {L}(X)$ (see Theorem VII.1 in [42]). With the continuous functional calculus introduced, one can deduce that for $\psi \in X$, $\langle \psi , f(A) \psi \rangle _{X}$ is a continuous linear functional on $C(\sigma (A))$, the set of continuous functions on the spectrum $\sigma (A)$. The Riesz–Markov theorem further implies that there is a unique measure $\mu _\psi$ on the compact set $\sigma (A)$ such that

$$\begin{aligned} \langle \psi , f(A) \psi \rangle _{X} = \int _{\sigma (A)} f(\lambda ) d\mu _\psi . \end{aligned}$$

(14)

The measure $\mu _\psi$ is said to be the spectral measure associated with $\psi$. Introducing spectral measures leads to a natural extension of the functional calculus to general bounded Borel functions: defining f(A) for f a bounded Borel function on $\mathbb {R}$ such that (14) holds, the polarization identity allows for recovery of $\langle \psi , f(A) \phi \rangle$ , $\phi \in X$, and hence for f(A) by utilizing the Riesz lemma.

By generalizing to bounded Borel functions, one can take characteristic functions $\chi _\Omega$ of Borel sets $\Omega$ and define spectral projections of A as operators

$$ P_\Omega := \chi _\Omega (A). $$

Lemma 27

Let $A \in \mathcal {L}(X)$ be self-adjoint and let $(P_\Omega )$ be its family of spectral projections. Then, the following hold:

• (i) each spectral projection $P_\Omega$ is an orthogonal projection;

• (ii) $P_{\emptyset } = 0$;

• (iii) there exists $a >0$ s.t. $P_{(-a,a)}=\,$id; and

• (iv) for any sequence of pairwise disjoint bounded Borel sets $(\Omega _n)_{n \in \mathbb {N}}$ and $\Omega := \bigcup _{n=1}^\infty \Omega _n$,

  $$ P_\Omega = \lim _{N \rightarrow \infty } \left( \sum _{n=1}^N P_{\Omega _n} \right) . $$

Here, as before, $\text{ Id }$ denotes the identity operator on X. A family of projections fulfilling conditions (i) to (iv) is called a projection-valued measure. With this concept at hand, we can state the spectral theorem for bounded self-adjoint operators in its projection-valued measure form (cf. Theorem VII.8 in [42]).

Theorem 28

(Spectral theorem). There is a one-to-one correspondence between bounded linear self-adjoint operators and bounded projection-valued measures:

$$\begin{aligned} A \longmapsto (P_\Omega )= & {} (\chi _\Omega (A)), \\ (P_\Omega ) \longmapsto A= & {} \int _{\sigma (A)} \lambda dP_\lambda . \end{aligned}$$

In the next section, we introduce and study an inverse problem with non-compact forward operator and derive its spectral properties to understand the sources of ill-posedness.

3 Limited Data Computerized Tomography

In the remainder of this chapter, we will treat three different ill-posed problems. In this section, we start with the first, which is also the most classical of them: it can be modeled by a linear forward operator and we will show how the spectral properties can be derived and used to prove that certain reconstruction algorithms are regularization methods, a concept we introduce in Sect. 4.

The linear inverse problem we aim to discuss stems from medical imaging, more precisely from computerized tomography (CT). In the classical two-dimensional (2D) setup, full data is acquired, which means that there is a moving X-ray source that rotates $180^{\circ }$ (“short scan”) or $360^{\circ }$ (“long scan”) around the 2D region (i.e., a cross-section of a three-dimensional object). In such a scan, the rotating source shoots X-rays from different directions in a sufficiently dense scanning scheme at the object of interest. The attenuation of the X-ray beams is then recorded on the other side of the object by an array of detectors. The region which is covered by a full angular range (i.e., at least $180^{\circ }$) is called the field-of-view (FOV), see Fig. 1.

Fig. 1

Classical 2D CT: the field-of-view fully covers the object support D

Fig. 2

Line integrals of the 2D cross-section

The attenuation of the X-ray beams, i.e., their intensity loss as they travel through the object, can reveal the structure of the object density. To make this more precise, we introduce the object support $D \subset \mathbb {R}^2$, the object density $f_D \in L^2(D)$ and parametrize a line L on which an X-ray beam travels by its distance $s\ge 0$ from the origin and its orientation $\theta \in S^1$, see Fig. 2. The attenuation can be modeled with the Beer–Lambert law of optics so that the CT scan essentially yields line integrals of f:

$$ \int _{\mathbb {R}} f_D(s\theta +t\theta ^\perp ) dt = -\ln \frac{I_L(\theta ,s)}{I_0(\theta ,s)}, $$

where $I_0(\theta ,s)$ and $I_L(\theta ,s)$ denote the intensity of the traveling beam as it exits the source and as it arrives at the detector, respectively. The mapping from functions to their line integrals is well known as the Radon transform. Thus, the measurements collected in 2D CT can be modeled as the Radon transform of $f_D$:

$$ \left( R f_D \right) (\theta ,s) = \int _{\mathbb {R}} f_D(s\theta +t \theta ^\perp ) dt, \quad s \in \mathbb {R}, \theta \in S^1. $$

Reconstruction of $f_D$ from 2D CT data hence amounts to inversion of the Radon transform. In light of the preceding discussion in Sect. 1, a natural question that arises in order to understand this linear inverse problem is whether we can determine the spectral properties of $R^* R$. This has been done in [39] and we briefly summarize the findings therein. First of all, one can assume w.l.o.g. that $D \subseteq B_2$, where $B_2$ denotes the unit disk in $\mathbb {R}^2$ and consider the Radon transform as a mapping from functions in $L^2(B_2)$ into a certain weighted $L^2$-space. Then, this operator is continuous (cf. Chap. 2 in [39]).

Theorem 29

(Continuity of the Radon transform) Let R be defined as the Radon transform with the following mapping:

$$ R:L^2(B_2) \rightarrow L^2(S^1 \times [-1,1],(1-s^2)^{-1/2}), $$

where $L^2(S^1 \times [-1,1],(1-s^2)^{-1/2})$ is the weighted $L^2$-space with weight $(1-s^2)^{-1/2}$ on $[-1,1]$. Then, R is continuous.

This operator admits a singular value decomposition (cf. Chap. 4 in [39]) with singular values decaying at a rate $\sigma _n \sim 1/\sqrt{n}$. In light of the discussion in the previous section, we can conclude that the reconstruction problem from full Radon transform data is only mildly ill-posed. This also implies that CT reconstruction can be rather easily regularized using standard methods such as filtered back-projection (FBP), see, e.g., Sect. V.1 in [39]. Radon inversion becomes much more delicate when no longer full Radon transform data are available, in which case one speaks of a limited data problem. We present one such instance in the following.

Fig. 3

Limited data 2D CT: the field-of-view does not cover the object support D

3.1 Truncated Projections

In this limited data CT problem, one has full angular coverage of the X-ray beams in only a subregion of the support D of the 2D object, see Fig. 3 for an illustration. In this case, one can only hope at recovering the object on the intersection of D with the field-of-view. We will refer to this intersection as the region-of-interest (ROI).

In such a setup, the FBP leads to only very poor reconstructions. Instead of performing Radon inversion in two steps (filtering and back-projection), an equivalent formulation can be given involving three steps:

Differentiated back-projection (DBP):

• (i) Differentiation:

  $$ r_D(\phi ,s) = \frac{\partial }{\partial s} (R f_D)(\theta ,s), \quad \theta ^\perp = (\cos \phi , \sin \phi ). $$

• (ii) Back-projection:

  $$ b_{\phi _1,\phi _2}(x) = \frac{1}{\pi } \int _{\phi _1}^{\phi _2} r_D (\phi ,s) |_{s=x\cdot \theta } \, d\phi . $$

  It can be calculated that

  $$ b_{\phi _1,\phi _2}(x) = (H_{\theta _2^\perp } f_D) (x) - (H_{\theta _1^\perp } f_D) (x), $$

  where $H_\theta f_D$ denotes the Hilbert transform of $f_D$ along the line through x with direction $\theta$.

• (iii) Hilbert transform inversion: The choice $\phi _2=\phi _1+\pi$ yields $\theta _2^\perp = -\theta _1^\perp$ and hence

  $$ b_{\phi _1,\phi _1+\pi }(x) = 2(H_{\theta _2^\perp } f_D)(x). $$

  Thus, the inversion of $H_{\theta _2^\perp }$ recovers $f_D$ on a line, so that the reconstruction of $f_D$ can be obtained by solving a family of one-dimensional (1D) problems.

The first two steps of DBP pose no problem in the case of truncated projections: differentiation is a local process and back-projection is angular averaging, which can be done in the region-of-interest because one has full angular coverage therein. The question of inverting the Hilbert transform is more delicate and requires careful analysis.

For the remainder of this section, let $a_1, a_2, a_3, a_4$ be positive real numbers such that $a_1<a_3$ and $a_2<a_4$. We will denote a 1D slice of the object density $f_D$ by f and assume that $f \in L^2([a_2,a_4])$, i.e., $\text{ supp } f \subseteq [a_2,a_4]$. Furthermore, the Hilbert transform $H:L^2(\mathbb {R}) \rightarrow L^2(\mathbb {R})$ is defined by the principal value integral

$$ (Hf)(x) = \frac{1}{\pi } \text{ p.v. } \int _\mathbb {R} \frac{f(y)}{y-x}dy. $$

For any $f \in L^2(\mathbb {R})$, the inversion of Hilbert transform data is simple, if Hf is measured on all of $\mathbb {R}$: The inverse of the Hilbert transform is just $H^{-1} = -H$, so that f can be recovered via $f = - H H f$.

In the case of truncated projections, each Hilbert transform of a slice f is only known on a finite interval, which we denote by $[a_1,a_3]\subset \mathbb {R}$. For an interval $I \subset \mathbb {R}$, let $\mathcal {P}_I:L^2(\mathbb {R}) \rightarrow L^2(\mathbb {R})$ denote the projection operator on I, i.e., $(\mathcal {P}_I f)(x) = f(x)$ for $x \in I$ and $(\mathcal {P}_I f)(x)=0$ otherwise. With this, one can define the truncated Hilbert transform as the operator

$$ H_T:= \mathcal {P}_{[a_1,a_3]} H \mathcal {P}_{[a_2,a_4]}. $$

Note that its adjoint is given by $H_T^* = -\mathcal {P}_{[a_2,a_4]} H \mathcal {P}_{[a_1,a_3]}$, which follows from a basic property of the Hilbert transform that its adjoint is simply $H^* = -H$. To understand the stability properties of solving

$$ H_T f = g, $$

for given right-hand side g, it is essential to study the spectrum $\sigma (H_T^* H_T)$.

This has been done in [29, 30] for the truncated Hilbert transform with a gap, i.e., for the case $[a_1,a_3] \cap [a_2,a_4] = \emptyset$, and the interior problem, i.e., when $[a_1,a_3] \subset [a_2,a_4]$, respectively, see Fig. 4. Here, we present a different limited data scenario than in [29, 30]: the truncated Hilbert transform with overlap, i.e., $a_1<a_2<a_3<a_4$, see Fig. 5.

Fig. 4

The truncated Hilbert transform with a gap (a) and the interior problem (b)

Fig. 5

The truncated Hilbert transform with overlap

The common theme of the spectral analysis in these problems is to relate the operators in question with differential operators through an intertwining property and to exploit the spectrum of the differential operators. This idea goes back to older problems, such as the spectral analysis of the interior Radon transform [34]. The most prominent example is the problem of Landau, Pollak, and Slepian [31, 32, 44] in communication theory. It can be described as follows: a signal (for example, in telecommunication) is naturally time-limited, say, to an interval $[-T,T]$. At the same time, when signals are transmitted through devices, this can only happen up to a certain frequency. Let $[-W,W]$ be the corresponding bandwidth. Then, the process of transmitting a time-limited signal can be described as applying the operator

$$ {\mathcal F}_{TW} := \mathcal {P}_{[-W,W]} {\mathcal F}\mathcal {P}_{[-T,T]}, $$

where ${\mathcal F}$ denotes the Fourier transform on $L^2({\mathbb R})$. From the uncertainty principle, it is apparent that for any signal f,  taking ${\mathcal F}_{TW}$ means some loss of information, in either time or frequency (or both). Engineers have thus been interested in quantifying this loss which can be measured by the ratio

$$ \frac{\Vert {\mathcal F}_{TW} f \Vert _{L^2({\mathbb R})}^2}{\Vert f\Vert _{L^2({\mathbb R})}^2} = \frac{\langle {\mathcal F}_{TW}^* {\mathcal F}_{TW} f,f \rangle _{L^2({\mathbb R})}}{\Vert f\Vert _{L^2({\mathbb R})}^2}. $$

This value is maximized when f is an eigenvector to the largest eigenvalue of ${\mathcal F}_{TW}^* {\mathcal F}_{TW}$. The fact that the eigenvalues and eigenvectors of ${\mathcal F}_{TW}^* {\mathcal F}_{TW}$ can be determined relies on the nice property that this operator commutes with the second-order differential operator

$$ (Df)(x) = \left( (T^2-x^2) f'(x) \right) ' - \frac{W^2}{\pi ^2} x^2 f(x) $$

and Sturm–Liouville theory can be employed to obtain its eigensystem. The eigenfunctions $(u_n)_{n \in {\mathbb N}}$ of D are known as the prolate spheroidal wave functions and, due to the commutation property, they are also the eigenfunctions of ${\mathcal F}_{TW}^* {\mathcal F}_{TW}$. The eigenvalues of ${\mathcal F}_{TW}^* {\mathcal F}_{TW}$ can then be determined as

$$\lambda _n:= \Vert {\mathcal F}_{TW}^* {\mathcal F}_{TW} u_n \Vert _{L^2({\mathbb R})}/\Vert u_n\Vert _{L^2({\mathbb R})}.$$

The commutation of D with ${\mathcal F}_{TW}^* {\mathcal F}_{TW}$ appears to be a lucky accident and while it is not the sole instance of a limited data integral operator commuting with a differential operator, there still exists no coherent theory for this phenomenon. However, the results of Landau, Pollak, and Slepian have to some extent been generalized in [26].

We now return to our problem of finding the spectrum $\sigma (H_T^* H_T)$ for $H_T$ the truncated Hilbert transform with overlap. Motivated by the analysis of the Landau–Pollak–Slepian operator, as well as the interior Radon transform and the two truncated Hilbert transforms in [29, 30], we, too, embark on the journey of finding commuting differential operators of which the spectral properties can be understood. We can formulate our goal more precisely as finding second-order differential operators $L_S$ and $\widetilde{L_S}$ such that

$$ H_T L_S = \widetilde{L_S} H_T. $$

In view of the desired aim to analyze the spectral properties of these operators, we require $L_S$ and $\widetilde{L_S}$ to be self-adjoint. If it turns out that $L_S, \widetilde{L_S}$ have simple discrete spectra, then one can work toward obtaining the SVD of $H_T$. Note that beforehand, there is no guarantee that $H_T$ has an SVD, i.e., that $\sigma (H_T^* H_T)$ is purely discrete.

Since we seek to find differential, and hence unbounded, operators $L_S$, $\widetilde{L_S}$ that are also self-adjoint, it is worth reviewing a fundamental theorem.

Theorem 30

(Hellinger–Toeplitz theorem) Let A be a linear everywhere-defined operator on a Hilbert space X with

$$ \langle f_1, A f_2 \rangle _X = \langle A f_1, f_2 \rangle _X, \quad \forall f_1, f_2 \in X. $$

Then, A is bounded.

In other words, an unbounded self-adjoint operator A cannot have its domain agreeing with all of X, i.e., $\mathcal {D}(A) \subsetneq X$. To make this more precise, we give the following definition:

Definition 31

(Symmetric operator) A densely defined operator A on X is symmetric if and only if

$$ \langle f_1, A f_2 \rangle _X = \langle A f_1, f_2 \rangle _X, \quad \forall f_1, f_2 \in \mathcal {D}(A). $$

We remark that for a symmetric operator A, $\mathcal {D}(A) \subseteq \mathcal {D}(A^*)$. Furthermore, A is self-adjoint if and only if it is symmetric and $\mathcal {D}(A) = \mathcal {D}(A^*)$. Starting from a symmetric operator, we will thus search for self-adjoint extensions by specifying suitable domains. Note that the spectrum of an unbounded operator is very sensitive to the choice of the domain. As in [29, 30], we choose to start with the differential form $L(x,d_x)$ defined as

$$\begin{aligned} L(x,d_x) \psi (x):= \left( P(x) \psi '(x)\right) ' + Q(x) \psi (x), \end{aligned}$$

(15)

where $P(x):=\prod _{i=1}^4 (x-a_i)$ and $Q(x):= 2 \left( x-\frac{1}{4} \sum _{i=1}^4 a_i \right) ^2$. The aim is to find self-adjoint operators $L_S,$ $\widetilde{L_S}$ with $\mathcal {D}(L_S)\subset L^2([a_2,a_4])$ and $\mathcal {D}(\widetilde{L_S}) \subset L^2([a_1,a_3])$, respectively. Formally, they are self-adjoint extensions of symmetric operators $L_{min},$ $\widetilde{L}_{min}$ with $\mathcal {D}(L_S) \supset \mathcal {D}(L_{min})$ and $\mathcal {D}(\widetilde{L_S}) \supset \mathcal {D}(\widetilde{L}_{min})$ and we refer to [9] for a definition of these operators.

For the spectral analysis, the interest lies in solutions $\psi$ to the Sturm–Liouville problem (SLP)

$$\begin{aligned} L(x,d_x) \psi (x) = \lambda \psi (x), \end{aligned}$$

(16)

for $\lambda \in \mathbb {C}$. A point $x_0 \in \overline{\mathbb {C}}$ is said to be ordinary if the functions

$$\begin{aligned} \widetilde{P}(x):= & {} \frac{P'(x)}{P(x)}, \\ \widetilde{Q}(x):= & {} \frac{Q(x)-\lambda }{P(x)} \end{aligned}$$

are analytic at $x_0$. The points $a_i, i=1,\dots ,4$ in (15) are not ordinary. More precisely, they are regular singular, meaning that at $a_i$, $\widetilde{P}(x)$ has a pole of up to order 1 and $\widetilde{Q}(x)$ has a pole of up to order 2. A standard result known as Fuchs’ theorem roughly states that at regular singular points, solutions to (16) are either bounded or have a logarithmic singularity.

In the analysis of the interior problem and the truncated Hilbert transform with a gap, the same differential form $L(x,d_x)$ as in (15) appears. However, in these cases, one seeks self-adjoint operators on intervals I and J for which $a_i$ are endpoints, but no point $a_i$ appears inside the intervals I and J. This makes the corresponding eigenvalue problems standard singular Sturm–Liouville problems with the only singular points being the endpoints of the interval. In such a case, the spectral properties of a self-adjoint extension are well known (cf. [47]).

The case of the truncated Hilbert transform with overlap is fundamentally different: here, we need to consider self-adjoint extensions on intervals $[a_2,a_4]$ and $[a_1,a_3]$ with $a_3$ and $a_2$, respectively, in the interior of the interval. With this, one exits standard Sturm–Liouville theory and is required to work with a singular Sturm–Liouville problem on two intervals (meaning that, e.g., when considering $L_S$ with $\mathcal {D}(L_S) \subset L^2([a_2,a_4])$, there are two involved subintervals $[a_2,a_3]$ and $[a_3,a_4]$ as the interval $[a_2,a_4]$ is interrupted by an interior singular point, namely $a_3$). For such two interval problems, there is some theory on self-adjoint extensions (cf. [47]) that we will employ. However, the results on the spectral properties are no longer straightforward. For a self-adjoint extension $L_S$ with $\mathcal {D}(L_S) \subset L^2([a_2,a_4])$, where $a_3 \in (a_2,a_4)$, the introduction of two boundary conditions (BCs) and two transmission conditions (TCs) is necessary to obtain a self-adjoint realization. The rationale for having four conditions is that now one works with two intervals and hence needs double the number of conditions (for a second-order ODE on one interval we need two conditions). The two BCs will act on the endpoints $a_2$ and $a_4$, while the two TCs will be there to connect the two subintervals $(a_2,a_3)$ and $(a_3,a_4)$.

Ultimately, we seek solutions to (16) that take on a special form: the (potential) eigenfunctions $(u_n)_{n\in {\mathbb N}}$ and $(v_n)_{n\in {\mathbb N}}$ of $L_S$ and $\widetilde{L_S}$, respectively, should satisfy

$$\begin{aligned} H_T u_n= & {} \sigma _n v_n,\\ H_T^* v_n= & {} \sigma _n u_n, \end{aligned}$$

for some real numbers $\sigma _n$. We can use this goal, together with some intuition on the Hilbert transform, to find suitable BCs and TCs. For example, when we take the Hilbert transform of a function $\psi$ with a jump discontinuity at $x_0$, then $H\psi$ will have a logarithmic singularity at $x_0$. On the other hand, suppose that at a point $x_0$, a function $\psi$ has a logarithmic singularity, i.e., in a region around $x_0$,

$$\begin{aligned} \psi (x) = \phi _{11}(x) + \phi _{12}(x) \ln |x-x_0|, \quad x<x_0, \end{aligned}$$

(17)

and

$$\begin{aligned} \psi (x) = \phi _{21}(x) + \phi _{22}(x) \ln |x-x_0|, \quad x>x_0, \end{aligned}$$

(18)

for some analytic functions $\phi _{ij}$. Then, in order for $H\psi$ to be bounded at $x_0$, one necessarily has

$$\begin{aligned} \lim _{x\rightarrow x_0^-} \phi _{11}(x)= & {} \lim _{x\rightarrow x_0^+} \phi _{21}(x), \end{aligned}$$

(19)

$$\begin{aligned} \lim _{x\rightarrow x_0^-} \phi _{12}(x)= & {} \lim _{x\rightarrow x_0^+} \phi _{22}(x). \end{aligned}$$

(20)

These observations lead to a specific picture of the singular functions of $H_T$, should they exist. They are bounded at the endpoints and have a logarithmic singularity of type (17)–(20) at the interior singular point. See [9] for full details and Fig. 6 for an illustration.

Fig. 6

Sketch of the (potential) singular functions $u_n$ and $v_n$ of $H_T$. They are bounded at the endpoints and have a logarithmic singularity at the interior singular point

To present a suitable candidate for $L_S$, we need a few more preparations. First, for an open interval $I \subset {\mathbb R}$, define the function space

$$ AC_{loc}(I):= \{\psi :I \rightarrow {\mathbb C}: \psi \text{ is } \text{ absolutely } \text{ continuous } \text{ on } \text{ all } [\alpha ,\beta ]\subset I \}. $$

Next, let the maximal domain $D_{max} \subset L^2([a_2,a_4])$ be given by

$$\begin{aligned} D_{max}:= \{ \psi :(a_2,a_4) \rightarrow {\mathbb C}: \psi |_{(a_i,a_{i+1})}, (P\psi ')|_{(a_i,a_{i+1})}\in & {} AC_{loc}((a_i,a_{i+1})), i=2,3, \\ \psi , L\psi\in & {} L^2([a_2,a_4]) \}, \end{aligned}$$

and recall the notion of the Lagrange sesquilinear form $[\cdot ,\cdot ]$ of two functions $r,s \in D_{max}$ which is defined as

$$ [r,s]:=rP\overline{s}' - \overline{s}Pr'. $$

One can deduce from Green’s formula that for all $r,s \in D_{max}$, the limits $\lim _{\alpha \rightarrow a_2^+} [r,s](\alpha )$, $\lim _{\beta \rightarrow a_3^-} [r,s](\beta )$, $\lim _{\alpha \rightarrow a_3^+} [r,s](\alpha )$, and $\lim _{\beta \rightarrow a_4^-} [r,s](\beta )$ exist and are finite.

Theorem 32

Let $L_S:D(L_S) \rightarrow L^2([a_2,a_4])$ be the extension of $L_{min}$ to the domain

$$\begin{aligned} D(L_S):=\{ \psi \in D_{max}: \left[ \psi ,r\right] (a_2^+)= & {} \left[ \psi ,r\right] (a_4^-) = 0, \\ \left[ \psi ,r\right] (a_3^-)= & {} \left[ \psi ,r\right] (a_3^+), \\ \left[ \psi ,s\right] (a_3^-)= & {} \left[ \psi ,s\right] (a_3^+)\}, \end{aligned}$$

with $r,s \in D_{max}$ chosen as

$$\begin{aligned} r(y):= & {} 1,\\ s(y):= & {} \sum _{i=1}^4 \prod _{j \ne i \atop j \in \{1,\dots ,4\}} \frac{1}{a_i-a_j} \ln |y-a_i|. \end{aligned}$$

Then, $L_S$ is a self-adjoint operator.

Proof

See Chap. 13 in [47], in which all self-adjoint extensions for two interval problems are given.    $\square$

Note that for $\lambda \in {\mathbb C}$, the above two BCs at $a_2$ and $a_4$, as well as the two TCs at $a_3$ simplify for solutions of $L \psi = \lambda \psi$. More precisely, if $\psi$ solves $L_S \psi = \lambda \psi$, then the above BCs mean that $\psi$ is bounded at the endpoints $a_2$ and $a_4$. Furthermore, the two TCs translate to (17)–(20). This gives hope that indeed, for this choice of $L_S$, there is a (much anticipated) relation between $H_T$ and $L_S$. In main contrast to Sturm–Liouville problems on one interval with no interior singular point, we have no straightforward guarantee that the spectrum of $L_S$ is purely discrete. One of the main findings in [9] is that this is, however, indeed the case. We summarize the result as follows.

Theorem 33

(Spectrum of $L_S$) Let $L_S$ be the self-adjoint extension of $L_{min}$ with domain $D(L_S) \subset L^2([a_2,a_4])$ as defined in Theorem 32. Then, its spectrum $\sigma (L_S)$ has the following properties:

• (i) $\sigma (L_S)$ is purely discrete.

• (ii) The set of eigenfunctions $(u_n)_{n \in {\mathbb N}}$ of $L_S$ are complete in $L^2([a_2,a_4])$.

• (iii) $\sigma (L_S)$ is simple, i.e., each eigenvalue has multiplicity 1.

• (iv) For all eigenfunctions $u_n$ of $L_S$:

  $$ \left( H_T L(y,d_y) u_n \right) (x) = L(x,d_x) \left( H_T u_n \right) (x). $$

One can define a second self-adjoint operator $\widetilde{L_S}$ with $D(\widetilde{L_S}) \subset L^2([a_1,a_3])$ equivalently to the definition of $L_S$ (by simply replacing the points $a_2, a_3$ and $a_4$ by $a_1, a_2$, and $a_3$, respectively. This allows to write property (iv) in the above more compactly as

$$ H_T L_S = \widetilde{L_S} H_T. $$

With that, one finally arrives at the following.

Theorem 34

(SVD of $H_T$) The eigenfunctions $u_n$ of $L_S$, together with

$$\begin{aligned} v_n:= & {} H_T u_n/\Vert H_T u_n\Vert _{L^2([a_1,a_3])},\\ \sigma _n:= & {} \Vert H_T u_n\Vert _{L^2([a_1,a_3])}, \end{aligned}$$

form the SVD of $H_T$:

$$\begin{aligned} H_T u_n= & {} \sigma _n v_n, \\ H_T^* v_n= & {} \sigma _n u_n. \end{aligned}$$

The functions $(v_n)_{n \in {\mathbb N}}$ are the eigenfunctions of $\widetilde{L_S}$ and form a complete orthonormal system of $L^2([a_1,a_3])$. In light of Hadamard’s well-posedness criteria one can further show that

$$ \mathcal {N}(H_T) = \{0\}, $$

i.e., the inversion problem enjoys uniqueness, and

$$ \mathcal {R}(H_T) \ne L^2([a_2,a_4]), $$

while $\mathcal {R}(H_T)$ is dense in $L^2([a_2,a_4])$. Thus, inverting from truncated Hilbert transform data is ill-posed in the sense that the solution does not depend continuously on the data. Another interesting fact is the following.

Theorem 35

The values 0 and 1 are (the only) accumulation points of the singular values of $H_T$.

This property implies that $H_T$ is not a compact operator. The accumulation of the singular values at 0 causes the instability of inverting the truncated Hilbert transform. As discussed in Remark 25, the decay rate of the singular values reveals the nature of the ill-posedness. To find how severe the ill-posedness of inverting $H_T$ is, we again make use of the differential operators $L_S$, $\widetilde{L_S}$. We aim at finding the asymptotics of the eigenfunctions $\psi _n$ of $L_S$ as $\lambda _n \rightarrow \pm \infty$ in

$$ L_S \psi _n = \lambda _n \psi _n. $$

Note that the two accumulation points $+\infty$ and $-\infty$ of $\lambda _n$ correspond to the accumulation points 0 and 1 of $\sigma _n$, respectively. The asymptotic analysis of $\psi _n$ for $n \rightarrow \pm \infty$ is based on three ingredients:

• (i) Global asymptotics: away from the regular singular points $a_i$, the solution $\psi _n$ is analytic and its asymptotics can be described with WKB (Wentzel–Kramers–Brillouin) approximations.

• (ii) Local asymptotics: close to the regular singular points $a_i$, the solution $\psi _n$ can be characterized by linear combinations of the Bessel functions $J_0$ and $Y_0$.

• (iii) Asymptotic matching: global and local asymptotics need to be matched in specified regions in which both are valid.

The above is just a sketch of the recipe and we refer to [5] for the full argument. Since the eigenfunctions of $L_S$ and $\widetilde{L_S}$ correspond to the two sets of singular functions of $H_T$, one has thus found the asymptotics of the singular functions of $H_T$. This can be used to further derive the asymptotic behavior of $\sigma _n \rightarrow 1$ and $\sigma _{-n} \rightarrow 0$ as $n \rightarrow \infty$. The result can be stated as follows.

Theorem 36

Let $(\sigma _n)_{n \in {\mathbb N}}$ and $(\sigma _{-n})_{n \in {\mathbb N}}$ denote the sequences of singular values of $H_T$ accumulating at 1 and 0, respectively. Then, there exist constants $c_1, c_2>0$ depending on only P and the points $a_i, i=1,\dots ,4$ such that

$$\begin{aligned} \sigma _n= & {} 2 e^{-c_1 n} \cdot \left( 1+ \mathcal {O}\left( n^{-1/2+\delta }\right) \right) , \\ \sigma _{-n}= & {} 1-2 e^{-c_2 n} \cdot \left( 1+ \mathcal {O}\left( n^{-1/2+\delta }\right) \right) , \quad \text{ as } n \rightarrow \infty , \end{aligned}$$

for some small fixed $\delta >0$.

Thus, the decay to 0 is exponential, which leads us to classify this inversion problem as severely ill-posed. We remark that this is typical for limited data problems in CT.

4 Regularization

So far, we have discussed detecting the instability of an inverse problem and, if an SVD exists, characterizing the severity of the ill-posedness through the decay rate of the singular values. This, of course, is only of theoretical interest, if it does not lead to new reconstruction methods dealing with these instabilities. In this section, we will see how one can aim at extracting information as stably as possible from an unstable system. This is the goal of regularization. With the example of the truncated Hilbert transform, we will further demonstrate in Sect. 4.2, how the derived knowledge of the SVD of the underlying operator and its asymptotic properties can enable us to prove rigorous results on the proposed regularization methods.

Clearly, solving for $Tf=g$ can be done by applying the Moore–Penrose generalized inverse to the right-hand side, resulting in a best-approximate solution:

$$ f^\dagger = T^\dagger g. $$

However, in practice, g is not known exactly, but only some measurement $g^\delta$ is acquired up to some noise level $\delta$, i.e., one only has a guarantee of the form

$$ \Vert g-g^\delta \Vert _Y \le \delta . $$

The main issue is the lack of continuous dependence of the data on the right-hand side: recall that if Hadamard’s third property is violated, then $T^\dagger$ is not a continuous operator. Thus, in general, $T^\dagger g^\delta$ is not a good approximation of $T^\dagger g$. Also note that $T^\dagger g^\delta$ might not even exist, since $\mathcal {D}(T^\dagger ) \subsetneq Y$ when $T^\dagger$ is not continuous.

In regularization theory, one seeks to find an approximation $f^\delta$ of $f^\dagger$ such that

• $f^\delta$ depends continuously on $g^\delta$,

• $f^\delta \rightarrow f^\dagger$ as $\delta \rightarrow 0$.

This is achieved by constructing a family of continuous operators $(R_\alpha )_{\alpha \in (0,\overline{\alpha })},$ $\overline{\alpha } \in {\mathbb R}_+ \cup \infty ,$ that approximate the unbounded operator $T^\dagger$. More precisely, for $\alpha = \alpha (\delta ,g^\delta )$, define $f_\alpha ^\delta := R_\alpha g^\delta$. The goal is to choose $\alpha (\delta ,g^\delta )$ and $R_\alpha$ such that $f_\alpha ^\delta \rightarrow f^\dagger$ as $\delta \rightarrow 0$. In other words, the lower the noise level, the more accurate the approximation $f_\alpha ^\delta$ is required to be. For high noise levels $\delta$, the reconstruction $f_\alpha ^\delta$ does not need to be close to $f^\dagger$. This matches the intuition that if the right-hand side is only known up to $\delta$, it is not feasible to aim at an approximation of the true solution $f^\dagger$ that is closer than $\delta$.. A precise definition of a regularization can be given as follows.

Definition 37

Let $T \in \mathcal {L}(X,Y)$, $\overline{\alpha } \in {\mathbb R}_+ \cup \{\infty \}$ and let $R_\alpha :Y \rightarrow X$ be a continuous operator for every $\alpha \in (0,\overline{\alpha })$. Suppose that for all $g \in \mathcal {D}(T^\dagger )$ there exists a parameter choice rule $\alpha = \alpha (\delta ,g^\delta ):{\mathbb R}_+ \times Y \rightarrow (0,\overline{\alpha })$ such that the following hold:

$$\begin{aligned} \limsup _{\delta \rightarrow 0} \left\{ \alpha (\delta ,g^\delta ):g^\delta \in Y, \Vert g-g^\delta \Vert _Y \le \delta \right\} = 0, \end{aligned}$$

(21)

and

$$\begin{aligned} \limsup _{\delta \rightarrow 0} \left\{ \Vert R_{\alpha (\delta ,g^\delta )} g^\delta - T^\dagger g\Vert _X: g^\delta \in Y, \Vert g-g^\delta \Vert _Y \le \delta \right\} = 0. \end{aligned}$$

(22)

Then, the family $(R_\alpha )_{\alpha \in (0,\overline{\alpha })}$ is called a regularization for $T^\dagger$. For every $g \in \mathcal {D}(T^\dagger )$, a pair $(R_\alpha ,\alpha )$ is called a convergent regularization method for solving $Tf=g$, if Eqs. (21) and (22) hold.

A regularization method is thus defined by two components:

• the operators $R_\alpha$ and

• the parameter choice rule $\alpha (\delta ,g^\delta )$.

A fundamental result by Bakushinsky states that $\alpha$ cannot be chosen independently of $\delta$.

Theorem 38

(A. B. Bakushinsky) If $\alpha = \alpha (g^\delta )$ yields a convergent regularization method, then $T^\dagger$ is bounded.

There are two possible choices of dependencies left and they are divided into a priori parameter choice rules, i.e., $\alpha = \alpha (\delta ),$ and a posteriori parameter choice rules, i.e., $\alpha = \alpha (\delta ,g^\delta )$.

Existence of a priori parameter choice rules can be guaranteed when $(R_\alpha )_{\alpha \in (0,\overline{\alpha })}$ is a family of continuous operators converging to $T^\dagger$ point-wise.

Theorem 39

If for all $\alpha > 0$, $R_\alpha$ is a continuous operator and

$$ R_\alpha \rightarrow T^\dagger \ \text{ point-wise } \text{ on } \mathcal {D}(T^\dagger ), \quad \text{ as } \alpha \rightarrow 0, $$

then $(R_\alpha )_{\alpha \in {\mathbb R}_+}$ is a regularization of $T^\dagger$ and for all $g \in \mathcal {D}(T^\dagger )$ there exists an a priori parameter choice rule $\alpha (\delta )$ for which $(R_\alpha , \alpha )$ is a convergent regularization method for $Tf=g$.

A regularization consisting of linear operators $R_\alpha$ is called a linear regularization method. Note that one can also consider a family of nonlinear operators $R_\alpha$ for approximating a linear operator $T^\dagger$. A well-known example is the conjugate gradient method equipped with an early stopping criterion to ensure regularization.

In order to construct regularization methods, the following viewpoint is helpful: Suppose that the operator $T^* T$ was continuously invertible with spectral projections $P_{\lambda }$, so that its inverse could be expressed as

$$ \left( T^* T\right) ^{-1} = \int _{\sigma (T^* T)} \frac{1}{\lambda } d P_\lambda . $$

Then, in view of (9), the following holds for the best-approximate solution $f^\dagger$:

$$\begin{aligned} f^\dagger = \int _{\sigma (T^* T)} \frac{1}{\lambda } d P_\lambda T^* g. \end{aligned}$$

(23)

If, however, $\mathcal {R}(T)$ is not closed, the above integral does not exist because zero belongs to the spectrum of $T^* T$, and hence the integrand $1/\lambda$ has a pole at zero. The concept of regularization is to replace $1/\lambda$ by a family of functions $(s_\alpha (\lambda ))_{\alpha \in {\mathbb R}_+}$ that approximates $1/\lambda$ and satisfies some continuity conditions. Instead of computing $f^\dagger$ one then constructs

$$\begin{aligned} f_\alpha := \int _{\sigma (T^* T)} s_\alpha (\lambda ) d P_{\lambda } T^* g, \end{aligned}$$

(24)

and the corresponding regularization operators are given by

$$\begin{aligned} R_\alpha := \int _{\sigma (T^* T)} s_\alpha (\lambda ) d P_\lambda T^*. \end{aligned}$$

(25)

More precisely, one has the following.

Theorem 40

For all $\alpha > 0$, let $s_\alpha :[0,\Vert T\Vert ^2] \rightarrow {\mathbb R}$ be piecewise continuous and suppose that there is a constant $C>0$ such that for all $\lambda \in (0,\Vert T\Vert ^2]$

$$\begin{aligned} \left| \lambda s_\alpha (\lambda ) \right| \le C, \end{aligned}$$

(26)

and

$$\begin{aligned} \lim _{\alpha \rightarrow 0} s_\alpha (\lambda ) = \frac{1}{\lambda }. \end{aligned}$$

(27)

Then, for all $g \in \mathcal {D}(T^\dagger )$,

$$ \lim _{\alpha \rightarrow 0} f_\alpha = f^\dagger $$

with $f^\dagger = T^\dagger y$ and

$$ f_\alpha := \int _{\lambda \in \sigma (T^* T)} s_\alpha (\lambda ) d P_\lambda T^* g. $$

Note that in view of the discussion in Sect. 2.3, the continuous functional calculus enables us to write

$$\begin{aligned} f_\alpha = s_\alpha (T^*T) T^* g. \end{aligned}$$

(28)

Similarly, for reconstruction from noisy data $g^\delta$, the approximation via $s_\alpha$ is expressed as

$$\begin{aligned} f_\alpha ^\delta = s_\alpha (T^*T) T^* g^\delta . \end{aligned}$$

(29)

Further note that, due to the ill-posedness, $\alpha$ has to be chosen carefully because when $g \not \in \mathcal {D}(T^\dagger )$,

$$ \lim _{\alpha \rightarrow 0} \Vert f_\alpha ^\delta \Vert _X = \infty . $$

One way to ensure convergence of $f_\alpha ^\delta$ is to choose $\alpha (\delta ,g^\delta )$ via Morozov’s discrepancy principle, which is an a posteriori rule.

Theorem 41

Let $s_\alpha$ be as in Theorem 40, fulfilling (26) and (27) and assume that for each $\lambda > 0$, $\alpha \mapsto s_\alpha (\lambda )$ is continuous from the left. Also, define

$$ r_\alpha (\lambda ):= 1 - \lambda s_\alpha (\lambda ). $$

Furthermore, let

$$ S_\alpha := \sup \left\{ s_\alpha (\lambda ): \ \lambda \in [0,\Vert T\Vert ^2]\right\} $$

be such that

$$ S_\alpha \le \frac{\tilde{c}}{\alpha }, \ \text{ for } \alpha >0, $$

for some constant $\tilde{c}>0$ and

$$ \tau> \sup \left\{ \left| r_\alpha (\lambda ) \right| : \ \alpha >0, \, \lambda \in [0,\Vert T\Vert ^2]\right\} . $$

Then, the discrepancy principle defined by

$$\begin{aligned} \alpha (\delta ,g^\delta ) := \sup \left\{ \alpha >0: \ \Vert T f_\alpha ^\delta - g^\delta \Vert _Y \le \tau \delta \right\} \end{aligned}$$

(30)

and $R_\alpha$ defined as in (25) form a convergent regularization method $(R_\alpha , \alpha )$ for all $g \in \mathcal {R}(T)$.

Remark 42

• The requirement that $g \in \mathcal {R}(T)$ is not restrictive: if $g\in \mathcal {D}(T^\dagger )$, but $g \not \in \mathcal {R}(T)$, then we can simply solve for

  $$ T^* T f = T^* g $$

  instead of $Tf=g$. This is then solvable for $g \in \mathcal {D}(T^\dagger )$ and the same result applies for this normal equation.

• The philosophy of the discrepancy principle is very intuitive: one compares the residual with the error bound $\delta$ and does not aim at an approximation that achieves a residual below $\delta$ as this is not meaningful: for noisy data $g^\delta$, with $\Vert g-g^\delta \Vert _Y \le \delta$, the best one should ask for is a residual of the order of $\delta$. On the other hand, from the viewpoint of regularization, one should aim at a regularization parameter as large as possible to ensure stability. This is a trade-off between accuracy and stability and the discrepancy principle roughly aims at achieving the optimal balance.

Next, we give two simple and well-known examples of regularization methods.

Example 43

One way to regularize the inversion of $T^* T$ is via a simple threshold:

$$ s_\alpha (\lambda ):= \bigg \{ \begin{array}{lr} \frac{1}{\lambda },&{} \text{ for } \lambda \ge \alpha , \\ 0,&{} \text{ for } \lambda < \alpha . \end{array} $$

For an operator with an SVD $(\sigma _n,u_n,v_n)_{n \in {\mathbb N}}$, this amounts to a truncated SVD:

$$ f_\alpha ^\delta := \sum _{n=1 \atop \sigma _n^2 \ge \alpha }^\infty \frac{1}{\sigma _n} \langle g^\delta , v_n \rangle _Y u_n. $$

Example 44

The most prominent example for regularization is Tikhonov regularization which amounts to defining

$$ s_\alpha (\lambda ) := \frac{1}{\lambda +\alpha }, $$

for $\alpha >0$. Since $\{\lambda + \alpha : \lambda \in \sigma (T^*T)\}$ is the spectrum of $T^* T + \alpha \text{ Id }$, Tikhonov regularization can be interpreted as

$$ f_\alpha ^\delta = \int _{\sigma (T^*T)} s_\alpha (\lambda ) d P_\lambda T^* g^\delta = \left( T^*T + \alpha \text{ Id }\right) ^{-1} T^* g^\delta . $$

In other words, one solves the regularized normal equation

$$\begin{aligned} \left( T^* T + \alpha \text{ Id }\right) f_\alpha ^\delta = T^* g^\delta . \end{aligned}$$

(31)

For an operator with an SVD $(\sigma _n, u_n, v_n)_{n \in {\mathbb N}}$, this can be written as

$$\begin{aligned} f_\alpha ^\delta := \sum _{n=1}^\infty \frac{\sigma _n}{\sigma _n^2 + \alpha } \langle g^\delta , v_n \rangle _Y u_n, \end{aligned}$$

(32)

i.e., the unbounded term $1/\sigma _n$ is replaced by the bounded term $\sigma _n/(\sigma _n^2+\alpha )$. One can show that $f_\alpha ^\delta$ in (32) is the unique minimizer of the Tikhonov functional

$$\begin{aligned} f \mapsto \Vert Tf-g^\delta \Vert _Y^2+ \alpha \Vert f\Vert _X^2. \end{aligned}$$

(33)

Formulated this way, Tikhonov regularization exhibits the typical form that instead of simply minimizing the residual, one introduces an additional penalty term, in this case the norm of f. As the noise level $\delta$ decreases, one can choose smaller $\alpha$, so that the penalty term becomes less emphasized.

Theorem 45

If $\alpha (\delta ,g^\delta )$ is chosen according to the discrepancy principle (30), Tikhonov regularization converges for all $g \in \mathcal {R}(T)$.

4.1 Miller’s Theory

As suggested in (33), one can alternatively study regularization from an optimization perspective. This has been suggested by Miller [37] and further discussed by Bertero, De Mol, and Viano in [15]. Suppose for simplicity that $T^{-1}$ exists and that a right-hand side $g^\delta$ is given with noise level $\Vert g-g^\delta \Vert _Y \le \delta$. In case of ill-posedness, $T^{-1}$ is unbounded and hence the set

$$ H(\delta ,g^\delta ):=\{f \in X: \Vert T f - g^\delta \Vert _Y \le \delta \} $$

is unbounded. Thus, finding an element in $H(\delta ,g^\delta )$ does not give any guarantee on how close it is to the exact solution. To achieve regularization, one introduces a restricted set of admissible solutions $\mathcal {S}(\delta ,g^\delta ) \subset H(\delta ,g^\delta )$, i.e., one assumes prior knowledge on the solution and hence only searches in a restricted set $\mathcal {S}(\delta ,g^\delta )$. If

$$\begin{aligned} \text{ diam } \ \mathcal {S}(\delta , g^\delta ) \rightarrow 0, \quad as \ \delta \rightarrow 0, \end{aligned}$$

(34)

then the problem is said to be regularized and any method $(R_\alpha ,\alpha )$ that guarantees

$$ R_{\alpha (\delta ,g^\delta )} g^\delta \in \mathcal {S}(\delta ,g^\delta ) $$

is a convergent regularization method. A typical choice for $\mathcal {S}(\delta ,g^\delta )$ is $\{f \in X: \Vert T f - g^\delta \Vert _Y \le \delta , \, \Vert Lf\Vert _X \le c \}$, for some constant $c>0$ and L a densely defined operator with bounded inverse. The choice $L=\text{ Id }$ corresponds to Tikhonov regularization. Other popular choices for L are differential operators, in which case the constraint amounts to a smoothness condition on f.

4.2 Regularization for the Truncated Hilbert Transform

We conclude this section by presenting results on the regularized reconstruction from truncated Hilbert transform data. As outlined in Sect. 3, the spectral properties of the operator $H_T$ have been derived in [5, 9]. The main tool for determining the asymptotics of the singular values is to find the global asymptotic behavior of the singular functions. This knowledge has been further used in [6, 10] to derive results on the regularization in the sense of Miller’s approach.

More precisely, when studying the asymptotics of the singular functions, one finds two characteristics:

• Oscillating behavior. The singular functions $u_n$ corresponding to accumulation in the spectrum at 1 oscillate inside the overlapping region, i.e., on $[a_2,a_3]$, and decay monotonically on $[a_3,a_4]$. On the other hand, the $u_n$’s corresponding to accumulation in the spectrum at 0 oscillate outside of the overlapping region, i.e., on $[a_3,a_4]$ and decay monotonically on $[a_2,a_3]$ (see Fig. 7). This suggests that the part of the spectrum causing instabilities corresponds to signals that are highly oscillating outside of the region-of-interest. Thus, to restore stability, one needs to suppress high oscillations outside of the overlapping region.

• Logarithmic singularity at the interior singular point. As we have already seen in Sect. 3, all singular functions have logarithmic singularities at the interior singular point, i.e., at $a_3$ (for $u_n$) and at $a_2$ (for $v_n$), see Fig. 7. Thus, methods that are SVD based (cf. Examples 43 and 44) might not be ideal: since they use a superposition of the singular functions in the reconstruction, they will most likely create reconstruction artifacts in the form of logarithmic singularities at $a_3$.

Fig. 7

Examples of singular functions $u_n$ and $v_n$ in red and blue, respectively. Here, $a_1=0$, $a_2=3$, $a_3=6$, $a_4=12$. Singular functions for $\sigma _n$ close to 0 in (a); singular functions for $\sigma _n$ close to 1 in (b). All of the singular functions exhibit singularities at the interior singular points

The derivation of stability estimates from the asymptotic expansions of $u_n$ and $v_n$ is very involved and technical and outside of the scope of this chapter. We merely present the results here. The first statement is that if one is only concerned with stability in a slightly restricted region-of-interest of the form $[a_2,a_3-\mu ]$, for some small $\mu >0$, then the method of Tikhonov already yields a regularization for reconstruction from $H_T$.

Theorem 46

Let $g \in \mathcal {R}(H_T)$ and $g^\delta \in L^2([a_1,a_3])$ be noisy data such that $\Vert g-g^\delta \Vert _Y \le \delta$ for some noise level $\delta >0$. For $E>0$, define the set of admissible solutions as

$$ \mathcal {S}(\delta , g^\delta ):= \{f \in L^2([a_2,a_4]): \ \Vert H_T f - g \Vert _{L^2([a_1,a_3])} \le \delta , \ \Vert f\Vert _{L^2([a_2,a_4])} \le E \}. $$

Let $\mu >0$ be constant and consider the reconstruction on $(a_2,a_3-\mu )$. Then, for sufficiently small $\delta$, any $f_1, f_2 \in \mathcal {S}(\delta ,g^\delta )$ satisfy a bound of the form

$$ \Vert f_1-f_2\Vert _{L^2([a_2,a_3-\mu ])} \le C_1 \delta + C_2 E^{1-\gamma } \delta ^\gamma , $$

where $C_1, C_2, \gamma >0$ are constants depending on only $\mu$ and the relative positions of the points $a_1, a_2, a_3, a_4$.

Remark 47

As already stated, the drawback of using Tikhonov regularization here is that it will create artifacts at the boundary of the region-of-interest due to the logarithmic singularities of the singular functions. See Figs. 8 and 9 for an example: Tikhonov regularization clearly exhibits these artifacts on the boundary of the ROI.

Fig. 8

Example of a limited data problem: the black circle indicates the field-of-view (FOV)

Fig. 9

Regularized reconstruction for the limited data problem in Fig. 8 using Tikhonov regularization in (a) and total variation (TV) regularization in (b). The artifacts at the boundaries of the ROI are apparent in the Tikhonov reconstruction but not in the TV reconstruction

As one can see in Fig. 9, the reconstruction using total variation (TV) regularization does not show the artifacts on the boundary of the ROI. This is because the method is not SVD based and penalizes singularities. To be more precise, in TV regularization, the set of admissible solutions $\mathcal {S}(\delta ,g^\delta )$ is chosen by restricting the total variation of the admissible functions. For weakly differentiable functions f with derivative $f_x$, the TV semi-norm is given by

$$ \left| f\right| _{TV}:= \Vert f_x\Vert _{L^1({\mathbb R})}. $$

The reason we are interested in TV regularization is that a TV penalty is the natural quantity to penalize both the artifacts on the boundary of the ROI, as well as highly oscillating behavior, causing ill-posedness. Again, exploiting the fine properties of the global asymptotic behavior of the singular functions (and now combined with an argument using Helly’s selection theorem), one can formulate a stability estimate for TV regularization. In fact, it suffices to penalize the total variation on a subinterval $[a_3-\mu ,a_4]$, for some $\mu >0$.

Theorem 48

Let $g \in \mathcal {R}(H_T)$ and $g^\delta \in L^2([a_1,a_3])$ be noisy data such that $\Vert g-g^\delta \Vert _Y \le \delta$ for some noise level $\delta >0$. For $\mu , \kappa >0$, define the set of admissible solutions as

$$\begin{aligned} \mathcal {S}(\delta , g^\delta ):= \{f \in W^{1,1}([a_2,a_4]): \ \Vert H_T f - g \Vert _{L^2([a_1,a_3])}\le & {} \delta , \ \Vert f_x\Vert _{L^1([a_3-\mu ,a_4])} \le \kappa , \\ \int _{a_2}^{a_4} f(x) dx= & {} C\}, \end{aligned}$$

for some constant C. Then, as $\delta \rightarrow 0$, one has that

$$ \text{ diam } \ \mathcal {S}(\delta ,g^\delta ) = \mathcal {O}(\left| \log \delta \right| ^{-1/2}) $$

and the constants in the decay rate depend on only $\mu$ and the relative positions of the points $a_1, a_2, a_3, a_4$.

Remark 49

Note that this decay rate is only logarithmic, while for Tikhonov regularization one has a decay of order $\delta ^\gamma$. However, the imposed prior knowledge in the case of TV regularization is mainly on the region outside of the ROI. Also, the guarantee that one obtains for the reconstruction is on $\Vert f_1-f_2\Vert _{L^2([a_2,a_4])}$ instead of merely on $\Vert f_1-f_2\Vert _{L^2([a_2,a_3-\mu ])}$.

5 Nonlinear Inverse Problems

While the theory of regularization is well understood in the linear case, it is much less straightforward in the case of nonlinear problems. Since for nonlinear operators there is hardly any spectral theory at hand, the analysis of the regularization becomes much more challenging. In this section, we intend to make brief mention of the particularities of treating nonlinear problems and refer to [21, 28] for a detailed discussion of the subject. In what follows, a nonlinear operator is denoted by

$$ F(f) = g, \quad F: \mathcal {D}(F) \subset X \rightarrow Y $$

and ill-posedness always refers to the lack of continuous dependence of the solution on the data. An important class of nonlinear (typically ill-posed) problems is that of parameter estimation in PDEs.

Example 50

Suppose that for some material with support in $\Omega \subset {\mathbb R}^3$, $u(x), x \in \Omega$ denotes the temperature distribution after sufficiently long time, h denotes internal heat sources and q the heat conductivity of the material. Assuming that u is kept zero at the boundary, the dependencies can be modeled as follows:

$$\begin{aligned} - \nabla \cdot \left( q(x) \nabla u \right)= & {} h(x), \quad x \in \Omega , \\ u(x)= & {} 0, \quad x \in \partial \Omega . \end{aligned}$$

Further assuming that h is known, the following problem is a typical parameter estimation problem: Given internal measurements of u or boundary measurements of the heat flux $q \frac{\partial u}{\partial n}$, determine the heat conductivity q. Note that the underlying operator $F: q \mapsto u_q$ is not given explicitly but is described through the PDE.

General assumptions typically made when considering nonlinear inverse problems (and also assumed in the remainder of this section) are the following:

• F is continuous,

• F is weakly sequentially closed, i.e.,

  $$ \begin{array}{cc} f_n&{}\rightharpoonup f \text{ in } X \\ F(f_n)&{}\rightharpoonup g \text{ in } Y \end{array}\bigg \} \Longrightarrow f \in \mathcal {D}(F) \text{ and } F(f) = g. $$

• For simplicity, one assumes $g \in \mathcal {R}(F)$.

For linear problems, the notion of minimum-norm solution has been introduced. For nonlinear problems, one rather considers the $f^*$-minimum-norm solution $f^\dagger$ which minimizes $\Vert f-f^*\Vert _X$. This is because the element 0 no longer plays a special role for nonlinear problems. Typically, one aims at choosing $f^*$ such that it includes some a priori information on the solution. The above assumptions guarantee existence of the $f^*$-minimum-norm solution. However, since F is nonlinear, it is not necessarily unique.

When analyzing the ill-posedness of linear operators, the closedness of the range is a simple criterion that characterizes the stability of the problem. Therefore, it would be convenient if for nonlinear problems it was possible to consider the linearization of the nonlinear operator. However, in general, there is no guaranteed connection between the ill-posedness of a nonlinear problem and its linearization.

Recall that for linear operators $T:X \rightarrow Y$, one has that compactness and injectivity of T implies unboundedness of $T^{-1}$ when X is infinite dimensional. There is a “nonlinear counterpart” to this statement: roughly, when F is compact and locally injective, then $\mathcal {D}(F)$ being “infinite dimensional around $f^\dagger$” implies the non-continuity of the inverse $F^{-1}$. A precise formulation is the following.

Theorem 51

Let F be a nonlinear compact and continuous operator with $\mathcal {D}(F)$ weakly closed. Let $F(f^\dagger )=g$ and suppose there exists $\epsilon > 0$ such that $F(f) = \hat{g}$ is uniquely solvable for all $\hat{g} \in \mathcal {R}(F) \cap B_\epsilon (g)$, where $B_\epsilon (g)$ denotes the ball of radius $\epsilon$ around g.

If there exists a sequence $(f_n)_{n \in {\mathbb N}} \subset \mathcal {D}(F)$ with

$$\begin{aligned} f_n \rightharpoonup f^\dagger , \text{ while } f_n \not \rightarrow f^\dagger , \end{aligned}$$

(35)

then $F^{-1}$ (defined on $\mathcal {R}(F) \cap B_\epsilon (g)$) is not continuous in g.

Note that assumption (35) can roughly be interpreted as infinite dimensionality of $\mathcal {D}(F)$ around $f^\dagger$: If $B_\epsilon (f^\dagger ) \subset \mathcal {D}(F)$, one can take $f_n = f^\dagger + \epsilon \cdot e_n$, where $e_n$ form a basis of X (recall that X is assumed to be separable). Then, since $e_n \rightharpoonup 0$, one has $f_n \rightharpoonup f^\dagger$ but $\Vert f_n-f^\dagger \Vert _X = \epsilon$.

We conclude this section by mentioning two standard approaches for solving nonlinear inverse problems: Tikhonov regularization and iterative methods.

In the nonlinear setting, Tikhonov regularization amounts to solving the following optimization problem:

$$\begin{aligned} \underset{f \in \mathcal {D}(F)}{\text{ arg } \text{ min }} \, \Vert F(f)-g^\delta \Vert _Y^2 + \alpha \Vert f-f^*\Vert _X^2, \end{aligned}$$

(36)

where, as before, $g^\delta \in Y$ denotes the noisy data and $\alpha$ the regularization parameter. As already noted, (36) has a solution but it is not necessarily unique due to the nonlinearity of F. Thus, one just searches for a solution of (36), which we will denote by $f_{\alpha }^\delta$. In general, this optimization problem is non-convex and it is possible to get stuck in local minima. The following is a result on Tikhonov regularization for appropriately chosen regularization parameter $\alpha$.

Theorem 52

Let $g \in \mathcal {R}(F)$ and $g^\delta \in Y$ with $\Vert g^\delta -g\Vert _Y \le \delta$ for $\delta >0$. Let $\alpha (\delta )$ be chosen such that

$$\begin{aligned} \alpha (\delta )\rightarrow & {} 0, \quad \text{ as } \delta \rightarrow 0,\\ \frac{\delta ^2}{\alpha (\delta )}\rightarrow & {} 0, \quad \text{ as } \delta \rightarrow 0. \end{aligned}$$

Furthermore, suppose that $(\delta _n)_{n \in {\mathbb N}}$ and $(\alpha _n)_{n \in {\mathbb N}}$ are sequences such that $\delta _n \rightarrow 0$ as $n \rightarrow \infty$ and $\alpha _n:=\alpha (\delta _n)$. Then, the sequence $(f_{\alpha _n}^{\delta _n})_{n \in {\mathbb N}}$ of solutions $f_{\alpha _n}^{\delta _n}$ to (36) for $\delta =\delta _n$ and $\alpha =\alpha _n$ has a convergent subsequence. The limit of every convergent subsequence is an $f^*$-minimum-norm solution. If the $f^*$-minimum-norm solution $f^\dagger$ is unique, then

$$ \lim _{\delta \rightarrow 0} f_{\alpha (\delta )}^\delta = f^\dagger . $$

We remark that for nonlinear problems, using Morozov’s discrepancy principle straightforwardly for Tikhonov regularization is a bit problematic because in general,

$$ \Vert F(f_{\alpha }^\delta )-g^\delta \Vert _Y = \delta $$

is only solvable under restrictive assumptions, and even if it is, this requires solving an additional nonlinear problem simultaneously. On the other hand, the discrepancy principle can be easily implemented for iterative methods. One can take a conventional iterative solver and often restore regularization by early stopping, where the stopping index $k_*$ has to depend on the noise level $\delta$. This is also true (and used) for linear problems. A stopping criterion in accordance to the discrepancy principle takes the form: stop the iteration at $k_*$, where

$$ \Vert g^\delta - F(f_{k_*}^\delta )\Vert _Y \le \tau \delta< \Vert g^\delta - F(f_k^\delta )\Vert _Y, \quad k < k_*, $$

for some $\tau >1$.

6 Phase Retrieval

In this section, we discuss a nonlinear inversion problem that does not very much fit into the theory outlined in the previous section and therefore also highlights the delicacy of studying nonlinear problems. The general setup is as follows.

Let X be a separable Hilbert space and $(\varphi _\lambda )_{\lambda \in \Lambda } \subset X$ some measurement system with index set $\Lambda \subseteq {\mathbb C}$. Typically, the requirement on $(\varphi _\lambda )_{\lambda \in \Lambda }$ is that any $f \in X$ can be stably and uniquely recovered from $( \langle f, \varphi _\lambda \rangle _{X})_{\lambda \in \Lambda }$. For $\Lambda$ a discrete index set, this can be conveniently summarized as $(\varphi _\lambda )_{\lambda \in \Lambda }$ being a discrete frame, meaning that there exist uniform constants $A,B>0$ such that

$$ A\Vert f\Vert _X^2 \le \sum _{\lambda \in \Lambda } \left| \langle f, \varphi _\lambda \rangle _X \right| ^2 \le B \Vert f\Vert _X^2, \quad \forall f \in X. $$

The question of phase retrieval can then be formulated as follows: When is it possible to uniquely (and stably) recover a function $f \in X$ from magnitude measurements

$$ \left( \left| \langle f, \varphi _\lambda \rangle _X \right| \right) _{\lambda \in \Lambda }? $$

Note that uniqueness of phase retrieval always has to be understood up to a global constant phase factor, i.e., unique recovery of f amounts to finding $\tau f$, for any $\tau \in S^1$. Thus, the distance between two elements $f_1, f_2 \in X$ is defined as

$$ \text{ dist}_X (f_1,f_2):= \inf _{\tau \in S^1} \Vert f_1-\tau f_2\Vert _X. $$

A lot of work has been done on phase retrieval for general frames, see, e.g., [13, 14, 16], as well as for more structured measurement systems, cf. [2, 3, 11, 17,18,19,20, 23, 24, 27, 33, 36, 40, 41, 43, 46] for example. However, many questions on uniqueness and stability of phase retrieval remain open. In what follows, we want to highlight a specific phase retrieval problem with a structured measurement system, showing that even if one can (partially) answer the question of uniqueness, the problem is in some sense highly unstable and difficult to regularize.

Gabor Phase Retrieval

Let $X=L^2({\mathbb R})$ and let the inner product on $L^2({\mathbb R})$ (or $L^2({\mathbb R}^2)$) simply be denoted by $\langle \cdot , \cdot \rangle$. We consider Gabor frames, i.e., frames that are built from a window function that we will choose to be the Gaussian

$$ \varphi (t):= e^{-\pi t^2} $$

and its time-frequency shifts: for each $\lambda = x+iy \in {\mathbb C}$, which we also identify with the vector $(x,y) \in {\mathbb R}^2$, we define

$$ \varphi _\lambda (t)=\varphi _{(x,y)}(t):= M_y T_x \varphi (t), $$

where $T_x$ denotes the translation (or time shift) by $x \in {\mathbb R}$:

$$ T_x f(t) := f(t-x), $$

and modulation (or frequency shift) by $y \in {\mathbb R}$ is denoted as

$$ M_y f(t) := e^{2\pi i y \cdot t} f(t). $$

While there is a rich theory on Gabor frames in which stable and unique recovery of a signal f is guaranteed from measurements $(\langle f, \varphi _\lambda \rangle )_{\lambda \in \Lambda }$, $\Lambda$ a discrete subset of ${\mathbb C}$, see, e.g., [22], we consider the best case scenario here: we assume that $\Lambda = {\mathbb C}$, i.e., the measurements are highly redundant and the measurements are given by the continuous transform

$$ V_\varphi f(x,y):= \int _{\mathbb R}f(t) \overline{\varphi (t-x)} e^{-2 \pi i t \cdot y} dt = \langle f, \varphi _{(x,y)} \rangle , \quad \forall \ x,y \in {\mathbb R}, $$

known as the Gabor transform of f. In phase retrieval, the task is to reconstruct f from

$$ \left( \left| V_\varphi (x,y) f \right| \right) _{(x,y) \in {\mathbb R}^2}. $$

More precisely, define the forward operator

$$\begin{aligned} \mathcal {A}_\varphi : L^2({\mathbb R})/S^1\rightarrow & {} L^2({\mathbb R}^2, {\mathbb R}_0^+),\\ f\mapsto & {} \left| V_\varphi f\right| , \end{aligned}$$

then phase retrieval amounts to the inversion of $\mathcal {A}_\varphi$.

Injectivity of Gabor Phase Retrieval

The question of uniqueness can be rather easily settled with the following fundamental formula:

$$\begin{aligned} \mathcal {F}\left( \left| V_g f \right| ^2 \right) (x,y) = V_f f (-y,x) \cdot \overline{V_g g(-y,x)}, \end{aligned}$$

(37)

where $\mathcal {F}$ denotes the two-dimensional Fourier transform on $L^2({\mathbb R}^2)$. Formula (37) holds, for example, when g is a Schwartz function and f is a tempered distribution [25]. Note that for $g=\varphi$, $V_\varphi \varphi$ is (up to some modulation factor) simply a two-dimensional Gaussian and therefore has no zeroes on all of ${\mathbb C}$. Thus, (37) implies that given $\left| V_\varphi f \right|$, one can recover $V_f f$ uniquely. More precisely, suppose that

$$\begin{aligned} \mathcal {F}\left( \left| V_\varphi f_1 \right| ^2 \right) (x,y)= & {} V_{f_1} f_1 (-y,x) \cdot \overline{V_\varphi \varphi (-y,x)},\\ \mathcal {F}\left( \left| V_\varphi f_2 \right| ^2 \right) (x,y)= & {} V_{f_2} f_2 (-y,x) \cdot \overline{V_\varphi \varphi (-y,x)}, \end{aligned}$$

and

$$ \left| V_\varphi f_1\right| = \left| V_\varphi f_2 \right| . $$

Then, (37) implies

$$ \left( V_{f_1} f_1 - V_{f_2} f_2 \right) \cdot \overline{V_\varphi \varphi } = 0, $$

and hence $V_{f_1} f_1 = V_{f_2} f_2$. One can further show (by taking one-dimensional Fourier transforms) that

$$ V_{f_1} f_1 = V_{f_2} f_2 \Rightarrow f_1 = \tau f_2, \quad \text{ for } \text{ some } \tau \in S^1, $$

which guarantees uniqueness of phase retrieval from measurements $\left| V_\varphi f \right| _{(x,y) \in {\mathbb R}^2}$, cf. [25]. Note, however, that for practical purposes formula (37) is not very useful as the exponential decay in $V_\varphi \varphi$ leads to serious instabilities in the reconstruction.

Stability of Gabor Phase Retrieval

In the strict regularization-theoretic sense, phase retrieval is not an ill-posed problem because of a result in [7], which states that

$$ \mathcal {A}_\varphi \text{ injective } \Rightarrow \ \mathcal {A}_\varphi ^{-1} \text{ continuous } \text{ on } \mathcal {R}(\mathcal {A}_\varphi ) \text{ and } \mathcal {R}(\mathcal {A}_\varphi ) \text{ closed. } $$

However, in practice, instabilities do occur. As shown in [7], the operator $\mathcal {A}_\varphi ^{-1}$ is never uniformly continuous when X is infinite dimensional. More precisely, there is no uniform constant $c_1 > 0$ for which

$$ c_1 \, \text{ dist}_X(f_1,f_2) \le \Vert \mathcal {A}_\varphi (f_1) - \mathcal {A}_\varphi (f_2) \Vert _{L^2({\mathbb R}^2)}, \quad \forall \ f_1, f_2 \in X. $$

For Gabor phase retrieval, this lack of stability has been quantified to some extent in [8]. A rather simple example captures the inherent nature of instability. For this, let $(f_a^+,f_a^-)$ be a parameter-dependent pair of functions defined as

$$\begin{aligned} f_a^+:= & {} T_a\varphi + T_{-a}\varphi , \end{aligned}$$

(38)

$$\begin{aligned} f_a^-:= & {} T_a\varphi - T_{-a}\varphi , \end{aligned}$$

(39)

see Fig. 10 for a plot of $(f_5^+,f_5^-)$. As one would expect, the Gabor transforms of such functions are almost the sum of two Gaussian bumps in the complex plane (see Fig. 11). For not too small a, the difference in magnitude of these Gabor transforms $V_\varphi f_a^+$ and $V_\varphi f_a^-$ is very small (see Fig. 12).

Fig. 10

The functions $f_a^+$ (blue) and $f_a^-$ (orange) for $a=5$

Fig. 11

Magnitudes of the Gabor transforms of $f_2^+$ in (a) and of $f_2^-$ in (b)

Fig. 12

$\left| \left| V_\varphi f_a^+ \right| - \left| V_\varphi f_a^- \right| \right|$ for $a=2$

This causes the typical instability: while the measurements are very close, this is not true for $f_a^+$ and $f_a^-$. More precisely, for this pair of parameter-dependent functions one can show (see [8]):

Theorem 53

Let the functions $f_a^+$ and $f_a^-$ be defined as in (38) and (39). Then there exists a uniform constant $C>0$ such that for all $a>0$ and for all $k \in (0, \pi /2)$:

$$\begin{aligned} \text{ dist}_{L^2({\mathbb R})} (f_a^+, f_a^-) \ge C e^{k \, a^2} \left\| \left| V_\varphi f_a^+ \right| - \left| V_\varphi f_a^- \right| \right\| _{W^{1,2}({\mathbb R}^2)}. \end{aligned}$$

(40)

So already in this explicit example, one has an exponential degradation of stability in the phase retrieval problem, which makes it “severely ill-posed”, though not in the classical sense.

Regularization for Gabor Phase Retrieval

We conclude this section by remarking that the above example also reveals that classical regularization will be ineffective in restoring stability of the phase retrieval problem. In essence, one would aim at finding a suitable penalty such that the problem is regularized by minimizing

where g denotes the measured data and $\alpha$ a suitably chosen regularization parameter. However, one can verify (see [8] for details) that all classical penalties, such as $L^2$, Besov space, modulation space norm, etc., do not resolve the occurring instability as they result in

for the above example.

The construction of $f_a^+$ and $f_a^-$, however, also reveals the source of instability: for these functions, the gap between the two Gaussian bumps centered at $\pm a$, cannot be bridged by the Gabor transform magnitude data in a stable way. The Gabor transform is to some extent well concentrated in both time and frequency and thus the measurements are disconnected, which is emphasized more strongly for larger a. This is also reflected in the bound (40) which degrades exponentially in $a^2$. More generally, whenever the Gabor transform of a signal is mainly concentrated on more than one region and the measurements are small outside of these regions, then phase retrieval will be unstable. We could have, for example, created similar instances to $f_a^+$ and $f_a^-$ of functions that present a gap in frequency instead of time. One could also think of functions that neither have a gap in frequency nor in time, but a time-frequency gap in their respective Gabor transforms. This observation has led to proposing a novel notion of solution such that stability is restored. In [4], it has been suggested to give up on global phase reconstruction when the Gabor transform is concentrated on more than one atoll and is small outside of these regions: then, one would only aim at global phase reconstruction on each individual atoll since this is the best one can do stably for Gabor phase retrieval. Figure 13 illustrates the concept. This atoll function reconstruction indeed results in a stability estimate [4]. However, it relies heavily on $\varphi$ being a Gaussian: in this case, $V_\varphi f$ is related to the Bargmann transform, which is a holomorphic function on ${\mathbb C}$. One can then argue via Cauchy–Riemann equations to obtain stability in regions where the measurements are not small. This has been further formalized in [25], with the concept of the Cheeger constant of the measurements describing their connectedness.

We remark that the use of such a “semi-global” phase reconstruction is justified in audio processing applications. There, constant phase factors on almost isolated regions do not audibly change the signal. See Fig. 14 for an example.

Fig. 13

The Gabor transform of f being concentrated on three regions (highlighted in color). Outside of these regions, $V_\varphi f$ is very small. We aim at reconstructing $V_\varphi f$ up to global phase on each of the three atolls individually. Inside each atoll, one can allow for small lagoons (highlighted in white) on which the measurements are small. The number and size of these lagoons both enter the stability estimate

Fig. 14

Gabor transform magnitude of an audio signal containing sounds of a bird and a bison. The region highlighted in light-blue is an example of an atoll: taking the original audio signal, and an audio signal for which the highlighted region has an additional constant phase factor, audibly results in the same signal

7 Instabilities in Image Classification

In the previous sections, we have taken the route of discussing linear inverse problems and the analysis and regularization that can be done for such problems, highlighting limited data reconstruction as an example. For nonlinear problems, the analysis is already more cumbersome and less straightforward and we showed phase retrieval as an example that does not fit the classical regularization theory but still exhibits instabilities. To conclude this discussion, we provide one more instance of a problem that suffers from instabilities but for which no rigorous theory has been developed so far. Thus, there is no meaningful analysis that can be provided to date but one can still point out the lack of robustness with explicit constructions.

The problem we have in mind is, in a broad sense, using deep neural networks (DNNs) as function approximations. In what follows, we will discuss the problem of object classification in images, but instabilities have, for example, also been reported in using DNNs for medical imaging applications [12].

In its simplest form, image classification aims at recognizing a single object in a given image. Typically, there is a set of labels to choose from and the task is to assign to each image the correct label. A function that maps images to labels is called a classifier. Suppose that the inputs are all RGB images of fixed square size, with $P= w^2$ pixels, so that they can be described as vectors in $X:={\mathbb R}^{3P}$. Let $L \ge 2$ be the number of labels or categories. Then, a classifier is a map

$$ \mathcal {K}: X \rightarrow \{1, \dots , L \}. $$

Typically, one chooses $\mathcal {K}$ to pick the most likely label from a feature vector, i.e.,

$$ \mathcal {K}(x):= \underset{k=1,\dots ,L}{\text{ arg } \text{ max }} \, F_k(x) $$

for some mapping $F:X \rightarrow {\mathbb R}^L$. State-of-the-art results are currently achieved by taking F to be a deep neural network. A simplified description of a neural network is the following.

Definition 54

A feedforward neural network of depth $D$ is a mapping

$$ F = F^D \circ F^{D-1} \circ \ldots \circ F^1, $$

where

$$ F^d:{\mathbb R}^{n_{d-1}} \rightarrow {\mathbb R}^{n_d},\quad x\mapsto \rho (W^d x + b^d), $$

for some $W^d\in {\mathbb R}^{n_d \times n_{d-1}}$, $b^d\in {\mathbb R}^{n_d}$ and a nonlinear activation function $\rho :\mathbb {R}\rightarrow \mathbb {R}$ applied element-wise to $W^d x + b^d$.

In practice, state-of-the-art networks are more sophisticated than in the above definition, but it still gives a good description of their structure: in essence, they are a repeated concatenation of affine transforms and element-wise nonlinearities.

The weight matrices $W^d$ as well as the bias vectors $b^d$ are free parameters learned during training: in supervised learning a training set of size m, i.e., a set of pairs of images and their correct labels $(x_j,l_j) \in X \times \{1,\dots ,L\}$, $j \in \{1,\dots ,m\},$ is given. One then aims at finding $F:X \rightarrow {\mathbb R}^L$ such that it captures the dataset distribution well enough. This is usually done by empirical risk minimization, where the objective is to minimize

$$ \mathcal {R}\left( F, (x_j,l_j)_{j=1}^m \right) := \frac{1}{m} \sum _{j=1}^m J\left( F,x_j,l_j\right) , $$

for some loss function J. In classification, the “default” is the cross-entropy loss function defined as

$$ J_{CE}\left( F,x_j,l_j\right) := - \log (F_{l_j}(x_j)), $$

where we assume that F outputs a vector of probabilities. Otherwise, an intermediate step called softmax layer needs to be introduced to output probabilities from F.

While the results obtained with supervised learning and deep neural network architectures are really astonishing for large training sets, it has also been pointed out over the last decade that DNNs are vulnerable to so-called adversarial examples.

In their seminal work [45], Szegedy et al. demonstrate that DNNs can be rather easily “fooled” by creating small perturbations such that the perturbed image looks (almost) the same upon visual inspection, but the network will no longer be able to correctly classify the object in the image. Since then, adversarial examples have evolved to an entire field of research in machine learning, with a number of contributions that have exploded by now, making it impossible to give a fair account of the existing literature.

To illustrate the phenomenon of adversarial examples, however, we do give an example of an algorithm that searches for small perturbations such that the perturbed image is incorrectly classified. The DeepFool algorithm introduced in [38] can be summarized as follows.

Let $\mathcal {K}=\text{ arg } \text{ max}_{k=1,\dots ,L} \, F$ be a trained classifier and let $x\in X$ be an image with correct label $l = \mathcal {K}(x)$. The DeepFool algorithm searches for $y=x+r$ with $\mathcal {K}(y)\ne l$ as follows:

• Choose a target label $k\ne l$.

• Set $f:=F_k - F_l$, where the goal is to achieve $f(y)>0$.

• Using $f(x+r)\approx f(x)+\nabla f(x)\cdot r$, define the perturbation

  $$ r := -\frac{ f(x) }{\Vert \nabla f(x) \Vert _{\ell ^2}^2} \nabla f(x) $$

  and set $\hat{x} = x + r$.

• If $\mathcal {K}(\hat{x})=k$, then we are successful. Otherwise, start at the top with $x$ replaced by $\hat{x}$.

The target label $k$ may be selected at each iteration to minimize $\Vert r\Vert$, for some chosen norm $\Vert \cdot \Vert$.

In Fig. 15, we give an example of a correctly classified image and a slightly perturbed image, which is classified incorrectly.

Fig. 15

Left: The object is correctly classified as a ptarmigan. Right: A small perturbation is added, of size $\Vert r\Vert _{\ell ^\infty } = 0.027$. The object is now incorrectly classified as a partridge. This example has been produced using the DeepFool algorithm on the ImageNet dataset with the Inception-v3 model

We note that adversarial examples can be very effectively constructed: for state-of-the-art networks such as Inception-v3 or ResNet-101, a very high percentage of correctly classified images indeed has an adversarial example in its vicinity. It is therefore very crucial to address this problem of instability. Many defenses against adversarial attacks have been suggested but they mainly follow, in one way or the other, the theme of adversarial training: adversarial examples are incorporated in the training procedure so that the network learns these instances. While this is a quite effective method, it also has its issues. Typically, networks are adversarially trained with respect to small perturbations. However, as demonstrated in, e.g., [1], small additive perturbations are not the only type of possible attack in image classification. For example, if an image is slightly deformed, the classification output should not be changed either. However, creating adversarial deformations is rather straightforward.

The ADef algorithm proposed in [1] can be described as follows: First of all, to facilitate the discussion on deformations, we model images as continuous objects, i.e., as elements of the space

$$ L^2([0,1]^2,{\mathbb R}^3)=\left\{ \xi : \, [0,1]^2\rightarrow {\mathbb R}^3:\int _{[0,1]^2}|\xi (u)|^2\,du<+\infty \right\} . $$

Given a vector field $\tau :[0,1]^2 \rightarrow {\mathbb R}^{2}$, we define the image after deformation by $\tau$ as

$$ \xi _\tau (u):=\xi (u+\tau (u)), \quad \forall \, u \in [0,1]^2, $$

where $\xi$ is extended by zero outside of $[0,1]^2$. In this context, the distance between $\xi$ and $\xi _\tau$ is not well quantified by a norm of $\xi -\xi _\tau$. Instead, we measure it with a norm on $\tau$ which we define to be

$$ \Vert \tau \Vert _T :=\Vert \tau \Vert _{L^\infty ({[0,1]^2})}= \sup _{u\in [0,1]^2} \Vert \tau (u)\Vert _{\ell ^2({\mathbb R}^2)}. $$

Suppose that a discrete image $x \in X$ is a discretization of $\xi$ on a regular grid $\{\frac{1}{w+1}, \dots , \frac{w}{w+1}\}^2$. In return, one can build such a function $\xi$ from x by interpolation. This way, one can make sense of a deformed image $x_\tau$ by defining it to be

$$ x_\tau (s,t) = \xi \left( \frac{(s,t)+\tau (s,t)}{w+1}\right) , \quad \forall \, (s,t) \in \left\{ \frac{1}{w+1}, \dots , \frac{w}{w+1}\right\} ^2. $$

To construct adversarial deformations for a classifier $\mathcal {K}=\text{ arg } \text{ max }\, F$ and a correctly classified image $x\in X$ with label $l = \mathcal {K}(x)$, we aim at finding a small vector field $\tau$ such that $l \ne \mathcal {K}(x_\tau )$. In the spirit of the DeepFool algorithm, one can again take gradient descent steps to achieve this:

• Choose a target label $k\ne l$ and set $f:= F_k -F_l.$

• Define the mapping $g:\, \tau \mapsto f(x_\tau )$ and search for $\tau$ such that $g(\tau )>0$ .

• By linear approximation

  $$ g(\tau )\approx g(0)+(D_0g)\tau , $$

  with (Fréchet) derivative

  $$ (D_0g)\tau = \sum _{s,t=1}^{w} A(s,t) \cdot \tau (s,t),\quad \text{ with } \ A(s,t):=\frac{1}{w+1} $$
  $$(\nabla f(x))(s,t) \nabla \xi \left( \frac{(s,t)}{w+1}\right) . $$

• $(D_0g)\tau = -g(0)$ does not have a unique solution. We can solve it in the least-squares sense:

  $$ \tau (s,t) = -\frac{g(0)}{\sum _{s,t=1}^w\left| A(s,t) \right| ^2}\,A(s,t). $$

• Set $\hat{x}(s,t)=x((s,t)+\tau (s,t))$. If $\mathcal {K}(\hat{x})=k$, the iteration has been successful. Otherwise repeat with x replaced by $\hat{x}$.

Figure 16 shows an example of a correctly classified image and its adversarially deformed counterpart.

Fig. 16

An image correctly classified as a redfox in (a) and a deformed version in (b) incorrectly classified as a shopping cart. The deformation is depicted in (c) and has size $\Vert \tau \Vert _T=1.178$. This example has been created using the ADef algorithm on the ImageNet dataset with the Inception-v3 model

First experiments suggest that networks trained against small perturbations using the celebrated projected gradient descent (PGD) algorithm [35] are less vulnerable to adversarial deformations than standard networks that have not been adversarially trained. However, the rate of incorrectly classified images when attacked with adversarial deformations is still considerably high, thus suggesting that these adversarially trained networks are far from being robust.

Creating DNNs that are truly robust with respect to all types of invariances that we expect (such as rotations, translations, small perturbations, small deformations, etc.) is important, but still an open problem.