Linear Ill-Posed

Problems
Michael Moeller

Chapter 2
Linear Ill-Posed Problems
Observations from
previous chapter
Ill-Posed Problems in Image and Signal Processing Finite dimensional
WS 2014/2015 linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

Michael Moeller
Optimization and Data Analysis
Department of Mathematics
TU München
updated 30.10.2014
 Linear Ill-Posed
What we have seen so far... Problems

• Differentiation: Finding u(x) for given Michael Moeller

Z x
u(y )dy
0
is ill-posed. Observations from
previous chapter
• Inverse heat equation: Finding u(x, 0) for given
Finite dimensional
Z π linear operators

u(x, T ) = k (x, y, T )f (y ) dy , Some functional

analysis basics
0
∞ Linear operators in
2 X −n2 T infinite dimensions
k (x, y , T ) = e sin(nx) sin(ny ).
π Compact linear
operators
n=1
The singular value
is ill-posed. decomposition

• Deconvolution: Finding u(x) for given

Z
k (x − y )u(y )dy
Ω
with smoothing kernel k is ill-posed.
Question
Is the inversion of integral operators ill-posed in general?
updated 30.10.2014
 Linear Ill-Posed
Why are problems ill-posed? Problems
Michael Moeller

We want to study and understand our introductory examples in

Observations from
more detail. previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Why are problems ill-posed? Problems
Michael Moeller

We want to study and understand our introductory examples in

Observations from
more detail. previous chapter

Finite dimensional
linear operators

Some functional
Observation: Our introductory problems can be written as analysis basics

Linear operators in
infinite dimensions
f = Au Compact linear
operators

for linear operators A : X → Y between Hilbert spaces X , Y . The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Why are problems ill-posed? Problems
Michael Moeller

We want to study and understand our introductory examples in

Observations from
more detail. previous chapter

Finite dimensional
linear operators

Some functional
Observation: Our introductory problems can be written as analysis basics

Linear operators in
infinite dimensions
f = Au Compact linear
operators

for linear operators A : X → Y between Hilbert spaces X , Y . The singular value

decomposition

Strategy: Understand finite dimensional case first!

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Linear operators between two finite dimensional Hilbert

spaces: Matrices.
Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Linear operators between two finite dimensional Hilbert

spaces: Matrices.
Observations from
previous chapter

Finite dimensional
Making our life easier: Consider a linear operator from a finite linear operators

dimensional Hilbert space into itself: A ∈ Rn×n . Some functional

analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Linear operators between two finite dimensional Hilbert

spaces: Matrices.
Observations from
previous chapter

Finite dimensional
Making our life easier: Consider a linear operator from a finite linear operators

dimensional Hilbert space into itself: A ∈ Rn×n . Some functional

analysis basics

Linear operators in
infinite dimensions

Compact linear
Corresponding finite dimensional linear inverse problem: Find operators

u from given The singular value

decomposition
f = Au

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Linear operators between two finite dimensional Hilbert

spaces: Matrices.
Observations from
previous chapter

Finite dimensional
Making our life easier: Consider a linear operator from a finite linear operators

dimensional Hilbert space into itself: A ∈ Rn×n . Some functional

analysis basics

Linear operators in
infinite dimensions

Compact linear
Corresponding finite dimensional linear inverse problem: Find operators

u from given The singular value

decomposition
f = Au

Making our life even easier: A is symmetric and positive

definite.

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Symmetric positive definite A ∈ Rn×n : Observations from

previous chapter

A = VSV T , Finite dimensional

linear operators

Some functional
with analysis basics

Linear operators in
• diagonal matrix S, Si,i = λi eigenvalues, infinite dimensions

• λ1 ≥ ... ≥ λn > 0, Compact linear

operators

• V orthonormal matrix of eigenvectors. The singular value

decomposition

1
Assume scaling: λ1 = 1. Condition number κ = λn .

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Assume f = Au, f δ = Au δ , with kf δ − f k ≤ δ:

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Assume f = Au, f δ = Au δ , with kf δ − f k ≤ δ:

u δ − u = VS −1 V T (f δ − f )
⇒ ku δ − uk = kVS −1 V T (f δ − f )k Observations from
previous chapter

= kS −1 V T (f δ − f )k Finite dimensional
linear operators

1 Some functional
≤ kV T (f δ − f )k analysis basics

λn Linear operators in
infinite dimensions
δ
= = κδ Compact linear
λn operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Assume f = Au, f δ = Au δ , with kf δ − f k ≤ δ:

u δ − u = VS −1 V T (f δ − f )
⇒ ku δ − uk = kVS −1 V T (f δ − f )k Observations from
previous chapter

= kS −1 V T (f δ − f )k Finite dimensional
linear operators

1 Some functional
≤ kV T (f δ − f )k analysis basics

λn Linear operators in
infinite dimensions
δ
= = κδ Compact linear
λn operators

The singular value

decomposition
→ Noise amplification: reciprocal of smallest eigenvalue!

→ Continuous dependence on the data!

→ Well-posed, but for small λn ill-conditioned!
→ In infinite dimensions: infinitely many λn → 0!

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Question
What can we do against the instability? Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Finite dimensional linear operators Problems
Michael Moeller

Question
What can we do against the instability? Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics
Idea: Linear operators in
infinite dimensions
• Approximate A by Aα = A + αI with α > 0.
Compact linear
operators
• The smallest eigenvalue is λn + α > α.
The singular value
• Approximate the solution to Au = f for given noisy data f δ decomposition

by uα = A−1 δ
α f .

Computation on the board.

updated 30.10.2014
 Linear Ill-Posed
Problems
Michael Moeller

Observations from
previous chapter

Finite dimensional
linear operators
Linear inverse problems in Some functional
analysis basics

infinite dimensions. Linear operators in

infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Some basics... Problems
Michael Moeller

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Some basics... Problems
Michael Moeller

Definition: Banach space

A normed vector space X which is complete is called a Banach Observations from
previous chapter
space. Being complete means that every Cauchy sequence Finite dimensional
converges in X . linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Some basics... Problems
Michael Moeller

Definition: Banach space

A normed vector space X which is complete is called a Banach Observations from
previous chapter
space. Being complete means that every Cauchy sequence Finite dimensional
converges in X . linear operators

Some functional
analysis basics

Definition: Hilbert space Linear operators in

infinite dimensions

A vector space X equipped with a scalar product h·,

p·i which is
Compact linear
operators
complete with respect to the induced norm kxk = hx, xi is The singular value
decomposition
called a Hilbert space.

updated 30.10.2014
 Linear Ill-Posed
Some basics... Problems
Michael Moeller

Definition: Banach space

A normed vector space X which is complete is called a Banach Observations from
previous chapter
space. Being complete means that every Cauchy sequence Finite dimensional
converges in X . linear operators

Some functional
analysis basics

Definition: Hilbert space Linear operators in

infinite dimensions

A vector space X equipped with a scalar product h·,

p·i which is
Compact linear
operators
complete with respect to the induced norm kxk = hx, xi is The singular value
decomposition
called a Hilbert space.

Convention
Unless stated otherwise, X and Y are real Hilbert spaces.

updated 30.10.2014
 Linear Ill-Posed
Banach and Hilbert spaces Problems
Michael Moeller

Proposition: Closed subspaces

Observations from
A nonempty subspace M ⊂ X is closed if and only if (xn ) ⊂ M, previous chapter

limn→∞ xn = x implies x ∈ M. Finite dimensional

linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Banach and Hilbert spaces Problems
Michael Moeller

Proposition: Closed subspaces

Observations from
A nonempty subspace M ⊂ X is closed if and only if (xn ) ⊂ M, previous chapter

limn→∞ xn = x implies x ∈ M. Finite dimensional

linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
Definition: Closure operators

The singular value

The closure M of M ⊂ X is defined as decomposition

n o
M = M ∪ x | ∃(xn ) ∈ M with lim xn = x
n→∞

updated 30.10.2014
 Linear Ill-Posed
Banach and Hilbert spaces Problems
Michael Moeller

Definition: Orthogonal complemet

The orthogonal complement of the set M ⊂ X is Observations from
previous chapter

Finite dimensional
M ⊥ = {x ∈ X | hx, mi = 0 ∀m ∈ M}. linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Banach and Hilbert spaces Problems
Michael Moeller

Definition: Orthogonal complemet

The orthogonal complement of the set M ⊂ X is Observations from
previous chapter

Finite dimensional
M ⊥ = {x ∈ X | hx, mi = 0 ∀m ∈ M}. linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

Theorem: Direct sum decomposition

Let M ⊂ X be any closed subspace of X . Then

X = M + M ⊥.

updated 30.10.2014
 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Observations from
previous chapter
Definition: Linear operators
Finite dimensional
A mapping A : D(A) ⊂ X → Y is called a linear operator, if the linear operators

Some functional
domain D(A) is a subspace of X and for all x1 , x2 ∈ D(A), and analysis basics

all α ∈ R Linear operators in

infinite dimensions

Compact linear
A(x1 + x2 ) = Ax1 + Ax2 operators

The singular value

A(αx1 ) = α Ax1 decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Definition: Boundedness
We say that a linear operator A : D(A) ⊂ X → Y is bounded if
there exists a c ∈ R such that for all x ∈ D(A) Observations from
previous chapter

Finite dimensional
kAxkY ≤ ckxkX . linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Definition: Boundedness
We say that a linear operator A : D(A) ⊂ X → Y is bounded if
there exists a c ∈ R such that for all x ∈ D(A) Observations from
previous chapter

Finite dimensional
kAxkY ≤ ckxkX . linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
Examples operators

The singular value

decomposition
• If A : X → Y is a linear operator with dim(X ) < ∞, then A
is bounded.
• First lecture: The derivative operator
∂x : C 1 ([0, 1]) ⊂ L2 ([0, 1]) → L2 ([0, 1]) is unbounded.
(Example with sin(2πkx))

updated 30.10.2014
 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Theorem: Boundedness and Continuity

Let A : D(A) ⊂ X → Y be a linear operator. Then the following
three statements are equivalent: Observations from
previous chapter
• A is continuous. Finite dimensional
linear operators
• A is bounded. Some functional
analysis basics
• A is continuous at x = 0.
Linear operators in
infinite dimensions

Proof: Exercises Compact linear

operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Theorem: Boundedness and Continuity

Let A : D(A) ⊂ X → Y be a linear operator. Then the following
three statements are equivalent: Observations from
previous chapter
• A is continuous. Finite dimensional
linear operators
• A is bounded. Some functional
analysis basics
• A is continuous at x = 0.
Linear operators in
infinite dimensions

Proof: Exercises Compact linear

operators

The singular value

decomposition

Notation

• L(X , Y ) set of all continuous linear operators from X to Y .

• N (A) := {x ∈ X | Ax = 0} nullspace of A
• R(A) := {y ∈ Y | ∃x ∈ X with Ax = y } range of A

updated 30.10.2014
 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Definition: Open Observations from

previous chapter

An operator A : X → Y is called open, if for every open set Finite dimensional

linear operators
M ⊂ X in X the set A(M) ⊂ Y is open in Y . Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

1 See D. Werner, Funktionalanalysis. Springer 2005. updated 30.10.2014

 Linear Ill-Posed
Linear operators Problems
Michael Moeller

Definition: Open Observations from

previous chapter

An operator A : X → Y is called open, if for every open set Finite dimensional

linear operators
M ⊂ X in X the set A(M) ⊂ Y is open in Y . Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

Theorem: Open mapping theorem The singular value

decomposition

1
If A ∈ L(X , Y ) is surjective, then A is open.

1 See D. Werner, Funktionalanalysis. Springer 2005. updated 30.10.2014

 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller
Question
The previous analysis was done for symmetric positive definite
matrices A ∈ Rn×n . What can we do for a general A ∈ L(X , Y )?

What could happen? Observations from

previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller
Question
The previous analysis was done for symmetric positive definite
matrices A ∈ Rn×n . What can we do for a general A ∈ L(X , Y )?

What could happen? Observations from

previous chapter
• If A is not surjective, Au = f might not have a solution. Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller
Question
The previous analysis was done for symmetric positive definite
matrices A ∈ Rn×n . What can we do for a general A ∈ L(X , Y )?

What could happen? Observations from

previous chapter
• If A is not surjective, Au = f might not have a solution. Finite dimensional
linear operators

Definition Some functional

analysis basics

We call u a least-squares solution of Au = f if Linear operators in

infinite dimensions

Compact linear
kAu − f k = inf{kAv − f k | v ∈ X } operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller
Question
The previous analysis was done for symmetric positive definite
matrices A ∈ Rn×n . What can we do for a general A ∈ L(X , Y )?

What could happen? Observations from

previous chapter
• If A is not surjective, Au = f might not have a solution. Finite dimensional
linear operators

Definition Some functional

analysis basics

We call u a least-squares solution of Au = f if Linear operators in

infinite dimensions

Compact linear
kAu − f k = inf{kAv − f k | v ∈ X } operators

The singular value

decomposition

• If A is not injective, the least-squares solution might not be

unique.

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller
Question
The previous analysis was done for symmetric positive definite
matrices A ∈ Rn×n . What can we do for a general A ∈ L(X , Y )?

What could happen? Observations from

previous chapter
• If A is not surjective, Au = f might not have a solution. Finite dimensional
linear operators

Definition Some functional

analysis basics

We call u a least-squares solution of Au = f if Linear operators in

infinite dimensions

Compact linear
kAu − f k = inf{kAv − f k | v ∈ X } operators

The singular value

decomposition

• If A is not injective, the least-squares solution might not be

unique.
Definition
We call u a minimal-norm solution of Au = f if

kuk = inf{kv k | v is least-squares solution of Au = f }

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

Question
Observations from
Can we define a linear operator that computes minimal norm previous chapter

solutions? Finite dimensional

linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

Question
Observations from
Can we define a linear operator that computes minimal norm previous chapter

solutions? Finite dimensional

linear operators

Some functional
analysis basics
Definition (Moore-Penrose inverse)
Linear operators in
Let A ∈ L(X , Y ) and let à : N (A)⊥ → R(A) denote its infinite dimensions

restriction. Then the Moore-Penrose generalized inverse A† is Compact linear

operators

defined as the unique linear extension of Ã−1 to The singular value

decomposition

D(A† ) := R(A) ⊕ R(A)⊥

with N (A† ) = R(A)⊥ .

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

The Moore-Penrose inverse is well-defined.

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

The Moore-Penrose inverse is well-defined.

Observations from
previous chapter

Theorem: Moore-Penrose equations Finite dimensional

linear operators

The Moore-Penrose generalized inverse A† meets the following Some functional

analysis basics
four Moore-Penrose equations Linear operators in

1 AA† A = A infinite dimensions

Compact linear
2 A† AA† = A† operators

The singular value

3 A† A = I − P decomposition

4 AA† = Q|D(A† )
where P : X → N (A) and Q : Y → R(A) are the orthogonal
projectors onto the nullspace of A, N (A), and onto the closure
of the range of A, R(A), respectively.

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

Observations from
previous chapter
Theorem: Minimal-norm solutions
Finite dimensional
For a given f ∈ D(A† ), the equation Ax = f has a unique linear operators

Some functional
minimal-norm solution given by analysis basics

Linear operators in

x † := A† f . infinite dimensions

Compact linear
operators
†
The set of all least-squares solutions is given by {x } + N (A). The singular value
decomposition

Proof: Board.

updated 30.10.2014
 Linear Ill-Posed
Gaussian normal equation Problems
Michael Moeller

A word about adjoint operators... Observations from

previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Gaussian normal equation Problems
Michael Moeller

A word about adjoint operators... Observations from

previous chapter

Finite dimensional
linear operators

Some functional
Theorem: Gaussian normal equation analysis basics

Linear operators in
For a given f ∈ D(A† ), x ∈ X is a least-squares solution of infinite dimensions

Ax = f if and only if x satisfies the Gaussian normal equation Compact linear

operators

The singular value

A∗ Ax = A∗ f . decomposition

Proof: Board.

updated 30.10.2014
 Linear Ill-Posed
Gaussian normal equations Problems
Michael Moeller

Observations:

• x † = A† y is the minimal-norm solution, i.e. the Observations from

previous chapter
least-squares solution with minimal norm.
Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Gaussian normal equations Problems
Michael Moeller

Observations:

• x † = A† y is the minimal-norm solution, i.e. the Observations from

previous chapter
least-squares solution with minimal norm.
Finite dimensional
• All least-squares solutions meet linear operators

Some functional
analysis basics
A∗ Ax = A∗ y (1) Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Gaussian normal equations Problems
Michael Moeller

Observations:

• x † = A† y is the minimal-norm solution, i.e. the Observations from

previous chapter
least-squares solution with minimal norm.
Finite dimensional
• All least-squares solutions meet linear operators

Some functional
analysis basics
A∗ Ax = A∗ y (1) Linear operators in
infinite dimensions

Compact linear
operators
† ∗ †
• A y = (A A) A y. ∗ The singular value
decomposition

updated 30.10.2014
 Linear Ill-Posed
Gaussian normal equations Problems
Michael Moeller

Observations:

• x † = A† y is the minimal-norm solution, i.e. the Observations from

previous chapter
least-squares solution with minimal norm.
Finite dimensional
• All least-squares solutions meet linear operators

Some functional
analysis basics
A∗ Ax = A∗ y (1) Linear operators in
infinite dimensions

Compact linear
operators
† ∗ †
• A y = (A A) A y. ∗ The singular value
decomposition
∗
• Possible to approximate A A instead of A.

(cf. Landweber iteration!)

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

For any linear operator equation f = Au, A ∈ L(X , Y ), we now Observations from
previous chapter
have a (possibly naive) way of finding a solution via u = A† f . Finite dimensional
linear operators

Some functional
When is this approach naive? analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Linear operator equations Problems
Michael Moeller

For any linear operator equation f = Au, A ∈ L(X , Y ), we now Observations from
previous chapter
have a (possibly naive) way of finding a solution via u = A† f . Finite dimensional
linear operators

Some functional
When is this approach naive? analysis basics

Linear operators in
infinite dimensions

Compact linear
Proposition: Discontinuity of A† operators

The singular value

A† is continuous if and only if R(A) is closed. decomposition

Proof: Board.

updated 30.10.2014
 Linear Ill-Posed
Compact linear operators Problems
Michael Moeller

Observations from
previous chapter
Definition: Compact linear operator
Finite dimensional
linear operators
A ∈ L(X , Y ) is said to be compact if for every bounded
Some functional
sequence {xn } ⊂ X , {Axn } has a convergent subsequence. analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Compact linear operators Problems
Michael Moeller

Observations from
previous chapter
Definition: Compact linear operator
Finite dimensional
linear operators
A ∈ L(X , Y ) is said to be compact if for every bounded
Some functional
sequence {xn } ⊂ X , {Axn } has a convergent subsequence. analysis basics

Linear operators in
infinite dimensions

Compact linear
Remark: Be careful with the dimensions of your space! operators

The singular value

decomposition
Example: Identity operator on X for finite and infinite
dimensional X .

updated 30.10.2014
 Linear Ill-Posed
Compact linear operators Problems
Michael Moeller

Observations from
previous chapter

Finite dimensional
linear operators
Theorem: Ill-posedness of compact linear operators Some functional
analysis basics
Let A ∈ L(X , Y ) be compact, and let the dimension of R(A) be Linear operators in
infinite. Then A† is discontinuous. infinite dimensions

Compact linear
operators
Proof: Board.
The singular value
decomposition

updated 30.10.2014
 Linear Ill-Posed
Compact linear operators Problems
Michael Moeller

What kind of operators are compact?

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Compact linear operators Problems
Michael Moeller

What kind of operators are compact?

Observations from
previous chapter
Theorem: Operators with Hilbert-Schmidt kernel are compact
Finite dimensional
linear operators
Let Z
Some functional
Au(x) = k (x, y)u(y) dy analysis basics

Ω Linear operators in
infinite dimensions
2 2 2
with kernel k ∈ L (Ω × Ω). Then A ∈ L(L (Ω), L (Ω)) is Compact linear
operators
compact.
The singular value
decomposition
Proof: Board.

A kernel k ∈ L2 (Ω × Ω) is called a Hilbert-Schmidt kernel from

Ω × Ω → R.

updated 30.10.2014
 Linear Ill-Posed
Examples for compact linear operators Problems
Michael Moeller
• Differentiation: Finding u(x) for given
Z x
u(y )dy
0
Observations from
previous chapter
is ill-posed.
Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Examples for compact linear operators Problems
Michael Moeller
• Differentiation: Finding u(x) for given
Z x
u(y )dy
0
Observations from
previous chapter
is ill-posed.
Finite dimensional
• Inverse heat equation: Finding u(x, 0) for given linear operators

Some functional
Z π analysis basics

u(x, T ) = k (x, y, T )f (y ) dy , Linear operators in

infinite dimensions
0
Compact linear
∞
2 X −n2 T operators
k (x, y , T ) = e sin(nx) sin(ny ). The singular value
π decomposition
n=1

is ill-posed.

updated 30.10.2014
 Linear Ill-Posed
Examples for compact linear operators Problems
Michael Moeller
• Differentiation: Finding u(x) for given
Z x
u(y )dy
0
Observations from
previous chapter
is ill-posed.
Finite dimensional
• Inverse heat equation: Finding u(x, 0) for given linear operators

Some functional
Z π analysis basics

u(x, T ) = k (x, y, T )f (y ) dy , Linear operators in

infinite dimensions
0
Compact linear
∞
2 X −n2 T operators
k (x, y , T ) = e sin(nx) sin(ny ). The singular value
π decomposition
n=1

is ill-posed.
• Deconvolution: Finding u(x) for given
Z
k (x − y )u(y )dy
Ω

with smoothing kernel k is ill-posed.

updated 30.10.2014
 Linear Ill-Posed
Compact linear operators Problems
Michael Moeller

What kind of operators are compact?

Facts about compact operators

Observations from
previous chapter
• Let A : X → Y be a compact linear operator. Finite dimensional
linear operators
Then A is bounded, i.e. A ∈ L(X , Y ).
Some functional
analysis basics

• Let A ∈ L(X , Y ) be compact and B ∈ L(Z , X ). Linear operators in

infinite dimensions
Then AB is compact. Compact linear
operators

• Let A ∈ L(X , Y ) and B ∈ L(Z , X ) be compact. The singular value

decomposition
Then AB is compact.

• Let A ∈ L(X , Y ) be compact.

Then A∗ is compact.

X , Y , Z Hilbert spaces.

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique
Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above Linear operators in

infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness? operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition
†
• A continuous

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition
†
• A continuous ⇔ R(A) closed.

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition
†
• A continuous ⇔ R(A) closed.

• A compact, R(A) infinite dimensional

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition
†
• A continuous ⇔ R(A) closed.

• A compact, R(A) infinite dimensional ⇒ A† not continuous.

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition
†
• A continuous ⇔ R(A) closed.

• A compact, R(A) infinite dimensional ⇒ A† not continuous.

• Integral equation with H.S. kernel

updated 30.10.2014
 Linear Ill-Posed
A little summary Problems
Michael Moeller

What did we learn so far?

Observations from
• No solution exists → least squares solution. previous chapter

Finite dimensional
linear operators
• Solution not unique → minimal norm solution.
Some functional
analysis basics

• Linear operator for the above → Moore-Penrose inverse. Linear operators in

infinite dimensions

Compact linear
• Third criterion for well posedness?→ A† continuous. operators

The singular value

decomposition
†
• A continuous ⇔ R(A) closed.

• A compact, R(A) infinite dimensional ⇒ A† not continuous.

• Integral equation with H.S. kernel ⇒ A compact

updated 30.10.2014
 Linear Ill-Posed
Problems
Michael Moeller

Observations from
previous chapter

Finite dimensional
linear operators
Study compact lin. operators A! Some functional
analysis basics

How does A† look like? Linear operators in

infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Eigendecomposition Problems
Michael Moeller

Theorem: Eigendecomposition2 Observations from

previous chapter

Finite dimensional
Let A ∈ L(X , X ) be self-adjoint and compact. Then there exist linear operators

at most countably many nonzero eigenvalues {λn }, n ∈ I, of A. Some functional

analysis basics
All eigenvalues are real and for a set of orthonormal
Linear operators in
eigenvectors {un } with kun k = 1 one has infinite dimensions

Compact linear
X operators
Ax = λi hx, un iun The singular value
decomposition
n∈I

2 See D. Werner, Funktionalanalysis. Springer 2005. Thm VI.3.2 pp 265. updated 30.10.2014
 Linear Ill-Posed
Eigendecomposition Problems
Michael Moeller

Requirements for the eigendecomposition:

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Eigendecomposition Problems
Michael Moeller

Requirements for the eigendecomposition:

• A is a compact linear operator. (OK!)

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Eigendecomposition Problems
Michael Moeller

Requirements for the eigendecomposition:

• A is a compact linear operator. (OK!)
• A ∈ L(X , X ) is self-adjoint. (Too restrictive!) Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Eigendecomposition Problems
Michael Moeller

Requirements for the eigendecomposition:

• A is a compact linear operator. (OK!)
• A ∈ L(X , X ) is self-adjoint. (Too restrictive!) Observations from
previous chapter

Finite dimensional
Ideas: If A ∈ L(X , Y ) is compact ... linear operators

Some functional
• ... then B := A∗ A is compact and self-adjoint. analysis basics

Linear operators in
X infinite dimensions
Bx = σn2 un hx, un i ∀x ∈ X Compact linear
operators
n∈I
The singular value
decomposition

updated 30.10.2014
 Linear Ill-Posed
Eigendecomposition Problems
Michael Moeller

Requirements for the eigendecomposition:

• A is a compact linear operator. (OK!)
• A ∈ L(X , X ) is self-adjoint. (Too restrictive!) Observations from
previous chapter

Finite dimensional
Ideas: If A ∈ L(X , Y ) is compact ... linear operators

Some functional
• ... then B := A∗ A is compact and self-adjoint. analysis basics

Linear operators in
X infinite dimensions
Bx = σn2 un hx, un i ∀x ∈ X Compact linear
operators
n∈I
The singular value
decomposition

• ... then C := AA∗ is compact and self-adjoint.

X
Cy = σ˜n 2 vn hy , vn i ∀y ∈ Y
n∈Ĩ

Further computations on the board.

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Singular value decomposition (SVD)
Any compact linear operator A ∈ L(X , Y ) has a representation
X
Ax = σn hx, un ivn Observations from
previous chapter
n∈I
X Finite dimensional

A∗ y = σn hy, vn iun linear operators

Some functional
n∈I analysis basics

Linear operators in
with the orthonormal singular vectors un and vn , and singular infinite dimensions

Compact linear
values σn > 0. operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Singular value decomposition (SVD)
Any compact linear operator A ∈ L(X , Y ) has a representation
X
Ax = σn hx, un ivn Observations from
previous chapter
n∈I
X Finite dimensional

A∗ y = σn hy, vn iun linear operators

Some functional
n∈I analysis basics

Linear operators in
with the orthonormal singular vectors un and vn , and singular infinite dimensions

Compact linear
values σn > 0. operators

The singular value

Convention: σ1 ≥ σ2 ≥ σ3 ≥ ... decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Singular value decomposition (SVD)
Any compact linear operator A ∈ L(X , Y ) has a representation
X
Ax = σn hx, un ivn Observations from
previous chapter
n∈I
X Finite dimensional

A∗ y = σn hy, vn iun linear operators

Some functional
n∈I analysis basics

Linear operators in
with the orthonormal singular vectors un and vn , and singular infinite dimensions

Compact linear
values σn > 0. operators

The singular value

Convention: σ1 ≥ σ2 ≥ σ3 ≥ ... decomposition

Sanity check:
N
X N
X N
X
k σn hx, un ivn k2 = σn2 hx, un i2 ≤ σ1 hx, un i2 ≤ σ1 kxk2
n=1 n=1 n=1

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Can we use the SVD for the Moore-Penrose inverse?

Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Can we use the SVD for the Moore-Penrose inverse?

Some considerations yield

Singular value representation of A† Observations from

previous chapter
†
For y ∈ D(A ) it holds that Finite dimensional
linear operators
X 1 Some functional
A† y = hy , vn iun . analysis basics
σn Linear operators in
n∈I infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Can we use the SVD for the Moore-Penrose inverse?

Some considerations yield

Singular value representation of A† Observations from

previous chapter
†
For y ∈ D(A ) it holds that Finite dimensional
linear operators
X 1 Some functional
A† y = hy , vn iun . analysis basics
σn Linear operators in
n∈I infinite dimensions

Compact linear
operators

The singular value

Proof that compact linear operators yield ill-posed problems: decomposition

kA† vn k = σ1n .

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller
Can we use the SVD for the Moore-Penrose inverse?

Some considerations yield

Singular value representation of A† Observations from

previous chapter
†
For y ∈ D(A ) it holds that Finite dimensional
linear operators
X 1 Some functional
A† y = hy , vn iun . analysis basics
σn Linear operators in
n∈I infinite dimensions

Compact linear
operators

The singular value

Proof that compact linear operators yield ill-posed problems: decomposition

kA† vn k = σ1n .

Theorem: Singular values of compact operators

Let A ∈ L(X , Y ) be compact. The zero is the only possible
accumulation point for the singular values σn .

Proof: Exercise. updated 30.10.2014

 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

From
X 1
A† y = hy, vn iun
σn Observations from
previous chapter
n∈I
Finite dimensional
we can see linear operators

Some functional
analysis basics

• errors corresponding to vn are amplified by 1

σn ,
Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

From
X 1
A† y = hy, vn iun
σn Observations from
previous chapter
n∈I
Finite dimensional
we can see linear operators

Some functional
analysis basics

• errors corresponding to vn are amplified by 1

σn ,
Linear operators in
infinite dimensions

Compact linear
operators
• errors corresponding to large n (“high frequencies”) are The singular value
decomposition
amplified much stronger,

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

From
X 1
A† y = hy, vn iun
σn Observations from
previous chapter
n∈I
Finite dimensional
we can see linear operators

Some functional
analysis basics

• errors corresponding to vn are amplified by 1

σn ,
Linear operators in
infinite dimensions

Compact linear
operators
• errors corresponding to large n (“high frequencies”) are The singular value
decomposition
amplified much stronger,

• the faster σn decays, the more severe the error

amplification.

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

Definition: Classification of ill-posedness

A problem Au = f with a compact linear operator A ∈ L(X , Y )
with infinite dimensional range is called
Observations from
previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

Definition: Classification of ill-posedness

A problem Au = f with a compact linear operator A ∈ L(X , Y )
with infinite dimensional range is called
Observations from
previous chapter

Finite dimensional
• Mildly ill-posed if there exist a γ ≤ 1 and C > 0, such linear operators

that σn ≥ Cn−γ for all n. Some functional

analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

Definition: Classification of ill-posedness

A problem Au = f with a compact linear operator A ∈ L(X , Y )
with infinite dimensional range is called
Observations from
previous chapter

Finite dimensional
• Mildly ill-posed if there exist a γ ≤ 1 and C > 0, such linear operators

that σn ≥ Cn−γ for all n. Some functional

analysis basics

Linear operators in
infinite dimensions
• Moderately ill-posed if it is not midly ill-posed but there Compact linear

exist a γ > 1 and C > 0, such that σn ≥ Cn−γ for all n. operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Singular value decomposition Problems
Michael Moeller

Definition: Classification of ill-posedness

A problem Au = f with a compact linear operator A ∈ L(X , Y )
with infinite dimensional range is called
Observations from
previous chapter

Finite dimensional
• Mildly ill-posed if there exist a γ ≤ 1 and C > 0, such linear operators

that σn ≥ Cn−γ for all n. Some functional

analysis basics

Linear operators in
infinite dimensions
• Moderately ill-posed if it is not midly ill-posed but there Compact linear

exist a γ > 1 and C > 0, such that σn ≥ Cn−γ for all n. operators

The singular value

decomposition

• Severly ill-posed if the singular values decay faster than

with polynomial speed.

Example: Differentiation
updated 30.10.2014
 Linear Ill-Posed
Summary Problems
Michael Moeller

What we have learned so far:

• Inversion of compact A ∈ L(X , Y ), dim(R(A)) = ∞, is Observations from
ill-posed! previous chapter

Finite dimensional
linear operators

Some functional
analysis basics

Linear operators in
infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Summary Problems
Michael Moeller

What we have learned so far:

• Inversion of compact A ∈ L(X , Y ), dim(R(A)) = ∞, is Observations from
ill-posed! previous chapter

Finite dimensional
• We have linear operators
∞
X 1 Some functional
A† y = hy , vn iun analysis basics
σn Linear operators in
n=1 infinite dimensions

Compact linear
operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Summary Problems
Michael Moeller

What we have learned so far:

• Inversion of compact A ∈ L(X , Y ), dim(R(A)) = ∞, is Observations from
ill-posed! previous chapter

Finite dimensional
• We have linear operators
∞
X 1 Some functional
A† y = hy , vn iun analysis basics
σn Linear operators in
n=1 infinite dimensions

Compact linear
• The decay of σn causes the ill-posedness. operators

The singular value

decomposition

updated 30.10.2014
 Linear Ill-Posed
Summary Problems
Michael Moeller

What we have learned so far:

• Inversion of compact A ∈ L(X , Y ), dim(R(A)) = ∞, is Observations from
ill-posed! previous chapter

Finite dimensional
• We have linear operators
∞
X 1 Some functional
A† y = hy , vn iun analysis basics
σn Linear operators in
n=1 infinite dimensions

Compact linear
• The decay of σn causes the ill-posedness. operators

The singular value

• In finite dimensions, small σn → ill-conditioned problem. decomposition

updated 30.10.2014
 Linear Ill-Posed
Summary Problems
Michael Moeller

What we have learned so far:

• Inversion of compact A ∈ L(X , Y ), dim(R(A)) = ∞, is Observations from
ill-posed! previous chapter

Finite dimensional
• We have linear operators
∞
X 1 Some functional
A† y = hy , vn iun analysis basics
σn Linear operators in
n=1 infinite dimensions

Compact linear
• The decay of σn causes the ill-posedness. operators

The singular value

• In finite dimensions, small σn → ill-conditioned problem. decomposition

Next chapter: Can we modify the σn to obtain stability?

updated 30.10.2014