Inverse Problems Course Notes — Introduction and Overview

These notes are based on Gunther Uhlmann’s lectures for MATH 581 taught at the University of Washington in Autumn 2009.

An index to all of the notes is available here.

This course is about solving inverse problems. What are inverse problems? It is difficult to define them precisely, let’s just say “I’ll know one when I see one”, but we can give a rough idea.

We have a medium we’re trying to understand — say a patient’s internal organs — and we probe it with waves as in this figure:

We can measure the outgoing waves. Then the “inverse problem” is this:

Problem 1 (General Inverse Problem) Can you recover the internal parameters of the medium by measuring outside the medium its response to incident waves?

Remember that none of these terms are defined precisely. What is a wave?

1. 1st Quarter

In this quarter we will consider the case when waves are X-rays that we can send in different directions and measure the attenuation in intensity as the x-rays pass through the medium. X-rays are high energy electromagnetic waves that travel (almost) in a straight line through media like human tissue. This is the mathematical setup behind the CT scan.

2. Beer’s Law

Beer’s Law is an experimental fact. Let {I(x)} denote the intensity of a wave on line {L} at point {x}, and let {f(x)} denote the attenuation at the point (this is related to the density). Then

\displaystyle  \frac{dI}{dx} = f(x)I(x)

We can solve this differential equation to get

\displaystyle  I(x) = exp[{\int_{L}f(x)dx}]

We can measure the intensity of an outgoing ray, {I_1}, with a detector. Let {I_0} denote the intensity at the source. This gives us our inverse problem:

Problem 2 (IP 1) If we know {I_0, I_1} for all lines {L}, can we recover {f(x)} (in some open set {\Omega \subset \mathbb{R}^n})?

in other words, if we know {\int_{L}f(x)dx} for all lines {L}, can we recover {f(x)}? This was solved in 1917 by Radon. It was rediscovered in the 1960’s by Cormack. Pure and applied mathematicians should talk more.

Also in the 1960’s, Hornsfeld developed the first tomograph. He and Cormack won a Nobel prize for their work in the 1970’s. It seems if you want a Nobel prize in Medicine, work on imaging — they’ve been given for CT, MRI, and PET (which we’ll talk about more later).

3. Mathematical setup

Now let’s get precise, and consider the case {n=2}. First we need to parameterize the set of lines. We will do this by specifying a line’s normal vector, {\omega}, and its distance from the origin, {s} as in the picture below.

This gives us

\displaystyle  L_{\omega,s} = \{\mathbf{x} \in \mathbb{R}^2 |\mathbf{x}\cdot\omega = s \}

With this we can define the Radon Transform:

\displaystyle  Rf(s, \omega) = \int_{\bf{x}\cdot\omega = s} f(\mathbf{x} ) dH

where {dH} is the standard Lebesgue measure.

Note that

\displaystyle  Rf(s, \omega) = Rf(-s, -\omega)

These definitions allow us to state our inverse problem more precisely:

Problem 3 (IP 2) Can we recover {f} from {Rf(s,\omega)} if we know {Rf} for all {(s,\omega) \in \mathbb{R}\times S^1}?

This is still not precise enough. When we face problems like this there will be some basic questions we always need to answer.

4. The Basic Questions

  1. What is the domain? (Which {f}‘s will we consider?) Call the domain {D}.
  2. Uniqueness. Does {Rf_1 = Rf_2 \implies f_1 = f_2}?
  3. Stability. How do errors affect the answer? In other words, does {Rf_1 \approx Rf_2 \implies f_1 \approx f_2}?
  4. Reconstruction formula or procedure. Can we compute {f} from {Rf}? How? For the Radon transform this is solved: {f = c_2 p.v. \int_{S^1}\int \frac{Rf(s,\omega)}{x\cdot\omega - s}ds d\omega}. (This is a singular integral, we’ll talk more about that later.)
  5. Can you develop a numerical algorithm based on the reconstruction procedure in (4)? For example, how do you position the lines for the best possible reconstruction? This leads to the filtered back-propagation algorithm in current use.
  6. What is the range of {R}? Why is this important? When we observe our (error prone, discretized data), we’ll want to find the closest possible {Rf} in the range to match work with — we know {Rf} must be in the range of {R}!

5. Other Questions

There are a few other questions we’ll want to answer too.

We want to know what to do with incomplete or partial data. So many rays have nothing to do with {f(x)}. What happens if we don’t use all lines? E.g., we only use lines through a given region.

Example 1 only take lines through the heart

Example 2 (The exterior problem) . Take all lines outside an object. You may need to do this if there is an opaque object inside the region you need to study.

Example 3 (Local tomography, cone beam tomography) . Only take lines within a finite aperture, not all angles.

6. Reconstructions in 3-D. X-ray tomography

Now we’ll consider the case {n=3}. Here we can parameterize lines by taking a base point {x \in \mathbb{R}^3} and a direction {\theta \in S^2}, and we have the X-ray transform:

\displaystyle  Xf(x,\theta) = \int_{\mathbb{R}}f(x + t\theta)dt

We have overcounted the lines here, we really only need to consider {x \in \theta^{\perp}}, more about this later.

It turns out here are many more lines in 3 dimensions than there were in 2 dimensions. Let’s make a rough count:

  • The dimension of the set of lines in 2-D is 2. It is parameterized by {(s,\omega) \in \mathbb{R}\times S^1}.
  • In 3-D the dimension of the set of lines is 4. It is parameterized by {\theta \in S^2, x \in \theta^{\perp}}.
  • In n dimensions, the dimension of the set of lines is 2n – 2

So,

  • In n = 2 {Rf} depends on two variables, and we are trying to recover two variables. The problem is formally determined.
  • In {n \geq 3} {Xf} depends on {2n - 2} variables, and we’re trying to recover a function on {n} variables. The system is formally overdetermined.

The qualifier “formally” is important here!

Since the system in 3-D is formally overdetermined, we need to ask

Problem 4 Can we find a 3-dimensional set of lines for which one can recover {f} well (in the sense described by the basic questions above)?

We’ll see that we can. Helical tomography, where X-rays have sources on a helix, will be an example. To see that helical tomography is formally determined, count the dimensions:

1 dimension from the curve + 2 dimensions from the angle = 3 dimensions

This is how CT scans really work, you may have seen a patient sliding through a circular piece of equipment. A point moving around a sliding circular source traces out a helix.

(A pdf version of these notes is available here.)

Advertisements

2 thoughts on “Inverse Problems Course Notes — Introduction and Overview

  1. Pingback: Inverse Problems Course Notes — Extending the Domain of R to Distributions « Constrained Rationality

  2. Pingback: Inverse Problems Course Notes — The X-Ray Transform « Rolfe's Lecture Notes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s