Inverse Problems Course Notes — Numerical Methods for X-Ray Transform Reconstruction

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.

The X-Ray transform is particularly interesting because we can use it for tomography. We can send X-Rays through a patient, over many different lines, and measure the accumulated attentuation. Once this is done, we know the X-Ray transform of our object, so we can simply pass this in to the inversion formula and reconstruct a three-dimensional model. There are two substantial problems with this:

  • We cannot collect data for every line, we can only sample a finite number of lines.
  • Our measurements will have error.

There are in fact even more complications — beam hardening comes to mind — but these two must be dealt with first. Loosely speaking, the solution to the first problem relies on the stability estimates for the X-Ray Transform, and the solution to the second problem depends on the range characterization. In this post we will discuss the first problem, finite sample size, in detail. The second problem is manageable too: the range characterization of the X-Ray Transform lets us find the image function most likely to have produced the error-filled data. It turns out that the filtered backprojection algorithm we introduce below is an important step in this process. The rest of this post is organized as follows: we will start by showing that for an infinite, discrete set of samples we have unique reconstruction. Then we will consider finite sets of samples and see that reconstruction is hopeless without a priori assumptions. From there we will introduce the Filtered Backprojection algorithm and state and Natterer’s theorem about filtered backprojection error estimates. Continue reading

Advertisements

Inverse Problems Course Notes — The Range of the X-Ray Transform

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.

Now we are prepared to study the range of the X-Ray Transform. We will will look at the image of {\mathcal{S}({\mathbb R}^n)} in detail — once we understand this we can easily use our understanding of the Radon transform to characterize the image of {X} for smooth, compactly supported functions.

So let {f \in \mathcal{S}({\mathbb R}^n)}. Recall that

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

It will be convenient to extend {Xf} to all of {{\mathbb R}^n\times({\mathbb R}^n - \{0\})} as follows

\displaystyle  \begin{array}{rcl}  Xf(x,\xi) &=& \int_{\mathbb R} f(x + t\xi) dt, \quad \xi \in {\mathbb R}^n - \{0\}) \\ \\ &=& \frac{1}{|\xi|}\int_{{\mathbb R}}f(x + t\frac{\xi}{|\xi}) dt \\ \\ &=& \frac{1}{|\xi|} \int_{\mathbb R} f(x - \langle x, \frac{\xi}{|\xi|}\rangle\frac{\xi}{|\xi|} + t\frac{\xi}{|\xi|}) dt \\ \\ &=& \frac{1}{|\xi|}Xf(x-\langle x, \frac{\xi}{|\xi|}\rangle\frac{\xi}{|\xi|}, \frac{\xi}{|\xi|}) \end{array}

So {Xf} is said to be positive homogeneous of degree -1 in {\xi}.

Claim 1 For {x \in {\mathbb R}^n}, {\xi \in {\mathbb R}^n - \{0\}} The partial differential equations

\displaystyle  \frac{\partial^2}{\partial x_i\partial \xi_j}Xf - \frac{\partial^2}{\partial x_j\partial \xi_i}Xf = 0

hold for all {1 \leq i, j \leq n}.

To show this, check the following

\displaystyle  \begin{array}{rcl}  \frac{\partial^2}{\partial x_i\partial \xi_j}Xf &=& \int_{\mathbb R} \frac{\partial^2}{\partial x_i\partial \xi_j} f(x + t\xi) dt \\ &=& t\int_{\mathbb R} \partial^2_{ij}f(x + t\xi) dt \end{array}

which is symmetric in {i} and {j}.

These equations are called John’s Equations, named for Fritz John who was the first to point this fact out. The main result is that these are the only conditions we need to characterize the range of {X} Continue reading

Inverse Problems Coruse Notes — Stability Estimates for the X-Ray Transform

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.

With an inversion formula in hand, we are ready to state and prove the basic stability estimates for the X-Ray Transform. They are almost identical to the estimates for the Radon transform, the only difference coming from the fact that {X} smoths by {1/2} of a derivative, where {R} smooths by {n/2} derivatives.

Theorem 1 For all {K \subset {\mathbb R}^n}, {K} compactly supported, and {f \in H^s(K)}, the following estimates hold

\displaystyle  \|f\|^2_{H^s({\mathbb R}^n)} \leq C_s\|Xf\|^2_{H^{s + 1/2}(T)} \leq C_s(K)\|f\|^2_{H^s({\mathbb R}^n)}

The first inequality holds even when {f} does not have compact support.

In other words X-Ray inversion is stable, and so is the X-Ray transform itself, as long as you measure errors with the right norms.

Proof: Step 1. {\|f\|_{H^s} \leq c\|Xf\|_{H^{s + 1/2}}}Let’s start by proving the first inequality — stability, or boundedness, of X-Ray inversion — in the {L^2} case ({s = 0}). The argument goes as follows: use the inversion formula to rewrite the formula for the norm of {f}, then use Plancherel’s Theorem and the Fourier Slice Theorem to move everything to the frequency domain. Here are the details.

\displaystyle  \begin{array}{rcl}  \|f\|^2_{L^2({\mathbb R}^n)} = \langle f,f\rangle_{L^2({\mathbb R}^n)} &=& \langle({(-\bigtriangleup)^{1/2}} X^tXf,f\rangle_{L^2({\mathbb R}^n)} \\ &=& \langle Xf, X{(-\bigtriangleup)^{1/2}} f\rangle_{L^2(T)} \\ &=& \langle \mathfrak{F}_{{\theta^\perp}}Xf, \mathfrak{F}_{{\theta^\perp}}X{(-\bigtriangleup)^{1/2}} f\rangle_{L^2(T)} \\ &=& \langle \hat{f}, |\eta|\hat{f}\rangle_{L^2({\mathbb R}^n)} \\ &=& \int_{{\mathbb R}^n}|\eta||\hat{f}(\eta)|^2 d\eta \\ &\leq& \int_{{\mathbb R}^n}(1 + |\eta|^2)^{1/2}|\hat{f}(\eta)|^2 d\eta \\ &=& \|f\|_{H^{1/2}({\mathbb R}^n)} \end{array}

Now we can extend this to general {s} by replacing {f} with {(I-\bigtriangleup)^{s/2}}. Then

\displaystyle  \begin{array}{rcl}  \|f\|_{H^s} = \|(I-\bigtriangleup)^{s/2}f\|_{L^2} &\leq& c_n\|X(I-\bigtriangleup)^{s/2}f\|_{H^{1/2}} \\ &=& c_n\|(I-\bigtriangleup_{{\theta^\perp}})^{s/2}Xf\|_{H^{1/2}} = c_n\|Xf\|_{H^{s+1/2}} \end{array}

Proving the first inequality. Here we relied on the following result, an easy generalization of the intertwining results for {X}, {\bigtriangleup} and {\mathfrak{F}} we used before.

Claim 1

\displaystyle  X(I-\bigtriangleup)^{s/2}f = (I-\bigtriangleup_{{\theta^\perp}})^{s/2}Xf

The proof is left as an exercise.

Step 2. {\|Xf\|_{H^{s + 1/2}} \leq C_s(K)\|f\|_{H^s}} Again, we will start with the {L^2} case.

\displaystyle  \begin{array}{rcl}  \|Xf\|_{H^{1/2}(T)} &=& \int_{S^{n-1}}\int_{{\theta^\perp}} |\mathfrak{F}_{{\theta^\perp}}Xf|^2(\eta,\theta)(1 + |\eta|^2)^{1/2} dH_{{\theta^\perp}}d\theta \\ &=& \int_{S^{n-1}}\int_{{\theta^\perp}} |\hat{f}(\eta)|^2(1 + |\eta|^2)^{1/2} dH_{{\theta^\perp}}d\theta \end{array}

To go forward we need a result that relates the measure {dH_{{\theta^\perp}}d\theta} to standard Lebesgue measure. As {\theta} varies over {S^{n-1}}, {H_{{\theta^\perp}}} clearly covers all of {{\mathbb R}^n}, but it covers it more than once and points close to the origin are covered “more densely” than points far away. The following claim makes this intuition precise, and the proof can be found in the appendix of Natterer’s book.

Lemma 2

\displaystyle  \begin{array}{rcl}  \int_{S^{n-1}}\int_{{\theta^\perp}} g(\eta) dH_{{\theta^\perp}}d\theta &=& \frac{1}{\text{Vol}(S^{n-2})}\int_{{\mathbb R}^n}\frac{g(y)}{|y|}dy \end{array}

This lets us continue, writing

\displaystyle  \|Xf\|_{H^{1/2}(T)} = c_n\int_{{\mathbb R}^n}\frac{|\hat{f}(\eta)|^2}{|\eta|}(1 + |\eta|^{2})^{1/2} d\eta

We have not used the compact support of {f} yet, but now it appears in a move that should seem familiar. We will split the integral into a sum of two integrals, one over the low fequencies, and the other over the high frequencies. Define

\displaystyle  \begin{array}{rcl}  \text{I} &=& c_n\int_{|\eta| \geq 1}\frac{|\hat{f}(\eta)|^2}{|\eta|}(1 + |\eta|^2)^{1/2} d\eta \\ \text{II} &=& c_n\int_{|\eta| \leq 1}\frac{|\hat{f}(\eta)|^2}{|\eta|}(1 + |\eta|^2)^{1/2} d\eta \end{array}

Then

\displaystyle  \|Xf\|_{H^{1/2}(T)} = {\text{I}} + {\text{II}}

But

\displaystyle  \text{I}\quad \leq \quad c\int_{|\eta| \geq 1} |\hat{f}(\eta)|^2d\eta \leq c\|f\|^2_{L^2}

And

\displaystyle  \text{II}\quad \leq \quad \sup_{|\eta| \leq 1}|\hat{f}(\eta)|^2 \cdot \int_{|\eta| \leq 1}\frac{(1 + |\eta|^2)^{1/2}}{|\eta|} d\eta \leq C(\text{Vol } K)^{1/2}\|f\|_{L^2}

We can repeat this argument for any {s} with the usual modifications (pick smooth compactly supported {\varphi \equiv 1} on {K} and use {\langle \varphi, f\rangle_{L^2} \leq \|\varphi\|_{H^{-s}}\|f\|_{H^s}}). \Box

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

Inverse Problems Course Notes — The X-Ray Transform for Distributions

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.

We have studied the X-Ray transform on very restricted domains — {C_0^\infty} and {\mathcal{S}} — and found an inversion formula there. Now we want to move to our next basic question: is the inversion stable?

As with the Radon transform, we will see that it is stable: small errors in the X-Ray transform lead to small errors in the reconstructed function, and vice versa, when errors are measured in an appropriate norms.

Sobolev spaces provide one family of norms that will work, but to use these we need to extend the domain of {X} to distributions, and prove the inversion formula on the broader domain. Continue reading

Inverse Problems Course Notes — An Alternative Development of the X-Ray Transform

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.

Now that we’ve sketched the basic facts about the X-Ray transform, let’s look at it from a different perspective. When we developed the theory of the Radon transform, we made extensive use of the Fourier Slice Theorem — something we did not mention at all for the X-Ray transform. We also notice that our inversion formula looked different from the one we developed for {R}.

In this post we will see that these differences are superficial. We will find the analog for the Fourier Slice Theorem and use it to redevelop our X-Ray transform results, mimicking our theory of the Radon transform. Continue reading

Inverse Problems Course Notes — The X-Ray Transform

We motivated the study of the Radon transform with a tomographic problem: given the change in intensity of X-rays along all lines through a region, can we reconstruct the attenuation (think of this as density) in the region?

For our purposes in this problem, light travels along straight lines and in two dimensions, those lines are hyperplanes.  So inverting the Radon transform — which sums functions over hyperplanes — solves our problem in 2-D.  But in higher dimensions this is not what we need.  We need to integrate along lines, not hyperplanes.

So we introduce the X-ray transform.

Definition Given a function f: \mathbb{R}^n \rightarrow \mathbb{C}, the X-ray transform of f is defined as

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

where x\in \mathbb{R}^n, \theta \in S^{n-1}.

The first thing to notice is that there is some redundancy here. Continue reading

Inverse Problems Course Notes — The Paley-Wiener Theorem

Having seen the support theorem for the Radon transform, and seeing how much we rely on the Fourier transform as a tool, it is natural to ask an analogous question for the Fourier transform.

The Easy Pieces: L^2 and \mathcal{S}

For some important spaces, the Fourier transform is very well behaved.  In particular

\mathfrak{F}: \mathcal{S}(\mathbb{R}^n) \rightarrow \mathcal{S}(\mathbb{R}^n)

\mathfrak{F}: \mathcal{S}^{\prime}(\mathbb{R}^n) \rightarrow \mathcal{S}^{\prime}(\mathbb{R}^n)

\mathfrak{F}: L^2(\mathbb{R}^n) \rightarrow L^2(\mathbb{R}^n)

and it is an isomorphism in each case.  But what about C_0^{\infty}(\mathbb{R}^n)\mathcal{E}^{\prime}(\mathbb{R}^n)?

A Harder Piece: f \in C_0^{\infty}(\mathbb{R}^n)

Say f \in C_0^{\infty}(\mathbb{R}^n), and specificallyr,  say A \leq |x| \implies f(x) = 0.  Then we can write

\hat{f}(\xi) = \int_{|x| < A} e^{-ix\cdot\xi}f(x)dx

for all \xi in \mathbb{R}^n.  It can be extended to \mathbb{C}^n:

\hat{f}(z) = \int_{|x| < A} e^{-ix\cdot z}f(x)dx Continue reading

Inverse Problems Course Notes — Motivating the Range Characterization for the Radon Transform

With the proofs of the range characterization and support theorems for the radon transform complete, let’s take a step back and look at the intuition behind these results again.  In particular, let’s try to understand the moment conditions (It might be good to read this post before reading the full proofs).  It was easy to directly verify that the moment conditions were necessary, so

R(\mathcal{S}(\mathbb{R}^n) \subset \mathcal{S}_H(\mathbb{R}\times S^{n-1})

We need to show it is sufficient — that \mathcal{S}_H(\mathbb{R}\times S^{n-1}) \subset R(\mathcal{S}(\mathbb{R}^n).  Take $g \ in \mathcal{S}_H(\mathbb{R}\times S^{n-1})$, we need to find f \in \mathcal{S}(\mathbb{R}^n) with Rf = g Continue reading

Inverse Problems Course Notes — The Support Theorem for the Radon Transform

In the last two posts we proved that when the Radon transform acts on Schwartz functions, its range is a subspace of Schwartz functions characterized by a set of moment conditions.  Now we will look at R on an even more restricted domain: functions with compact support.

Clearly if f has compact support, so does Rf, so  R: C_0^{\infty}(\mathbb{R}^n) \rightarrow \mathcal{S}_H(\mathbb{R}\times S^{n-1}) \cap C_0(\mathbb{R}\times S^{n-1}) is injective.  We want to show that there are no other restrictions on the range, i.e. this map is onto.

Thanks to our work on \mathcal{S} we already know that for any g \in \mathcal{S}_H(\mathbb{R}\times S^{n-1}) \cap C_0(\mathbb{R}\times S^{n-1}) there exists some f \in \mathcal{S}(\mathbb{R}^n) with Rf = g.  If we can prove that this f must have compact support we will have our result.

Actually, we’ll prove an apparently stronger statement.

Theorem [The Support Theorem] If f \in C(\mathbb{R}^n) satisfies

(i) [Rapid decrease] |x|^k|f(x)| is bounded for all k > 0

(ii) [Compact support] \exists A > 0 such that |\rho| > A \implies Rf(\rho,\omega) = 0

Then f(x) = 0 for all |x| > A.

The first condition seems strange — is this really needed?

In fact, there are counterexamples. Continue reading

Inverse Problems Course Notes — Proof of Helgason-Ludwig’s Range Characterization

In the last post we stated and motivated a theorem characterizing the image of the Schwartz space under the Radon transform:

Theorem [Helgason-Ludwig] The Radon transform is a bijective linear map from \mathcal{S}(\mathbb{R}^n) onto \mathcal{S}_H(\mathbb{R}\times S^{n-1}), where \phi \in \mathcal{S}_H(\mathbb{R}\times S^{n-1}) if and only if

  1. \phi \in \mathcal{S}(\mathbb{R}\times S^{n-1}) , i.e. it is smooth and all of its derivatives decay faster than any polynomial.
  2. It is even: \phi(-s, -\omega) = \phi(s,\omega)
  3. It satisfies the “moment conditions”: \mu_k\phi(\omega) = \int_{\mathbb{R}}\phi(s, \omega)s^kds is a homogeneous polynomial of degree k in \omega.

Proof We need to prove the following:

  1. R is linear.  This is trivial
  2. R is injective.  This is a direct corollary of the Fourier Slice Theorem.
  3. f \in \mathcal{S}(\mathbb{R}^n) \implies Rf \in \mathcal{S}_H(\mathbb{R}\times S^{n-1})$.  This was largely done in earlier posts, but we will consolidate the argument below.
  4. g \in \mathcal{S}_H(\mathbb{R}\times S^{n-1}) \implies \exists f \in \mathcal{S}(\mathbb{R}^n), Rf = g, i.e. the map is surjective. Continue reading