A great tool

December 30, 2009

I’ve started using latex2wp to convert my lecture notes to wordpress format, and it is great.  I spend far less time futzing with wordpress, and I get nicer looking posts. I also get to write in standard LaTeX,  and can produce pdfs from the same document I use to produce blog posts. In that mythical future when I have free time, I may start seeing if I can tweak it or contribute a bit.

In the mean time, I hope to rewrite all of the earlier posts using this tool to get a more consistent look and an easier to manage set of source documents.  In other news: next week brings a new quarter, and a set of lectures on electrical impedance tomography.

Posted in Uncategorized | 1 Comment »

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

December 30, 2009

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. Read the rest of this entry »

Tags:
Posted in Inverse Problems | Leave a Comment »

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

December 4, 2009

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} Read the rest of this entry »

Tags:
Posted in Inverse Problems | Leave a Comment »

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

November 30, 2009

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.)

Tags:
Posted in Inverse Problems | Leave a Comment »

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

November 23, 2009

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. Read the rest of this entry »

Tags:
Posted in Inverse Problems | 2 Comments »

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

November 19, 2009

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. Read the rest of this entry »

Tags:
Posted in Inverse Problems | Leave a Comment »

The Geometry of the Slice Theorems

November 19, 2009

When studying the Radon transform, we saw that we could reconstruct the Fourier transform of a function from its Radon Transform:

  • The Fourier Transform integrates the product of a function with “waves” that are constant on hyperplanes.
  • The Radon Transform computes the integral of a function over these hyperplanes.
  • So the Fourier Transform of a function is a sort of phase-weighted sum of integrals over hyperplanes, i.e. a phase-weighted sum of the Radon transform.

When evaluating the Fourier Transform of a function f at a point \rho\omega, the hyperplane x\cdot\omega = s appears with “weight” e^{-i\rho x\cdot\omega} = e^{-i\rho s}. So we can write the Fourier transform of f in terms of the Radon Transform as follows:

\hat{f}(\rho\omega) = \int_{-\infty}^{\infty}e^{-i\rho s}Rf(s, \omega) ds = \mathfrak{F}_sRf(\rho, \omega)

The same arguments apply to the X-Ray transform.  In fact, we can compute the Radon transform from the X-Ray transform at a hyperplane by integrating Xf over a set of parallel lines that covers the hyperplane (there is more than one way to do this!).

To compute the Fourier Transform directly from the X-Ray transform, consider the following.  Say we want to compute the Fourier Transform of f at a frequency vector \eta.  We can pick any orthogonal \theta, and have \eta \in \theta^\perp.  Now the “wave” with frequency \eta will be constant in direction \theta, so to compute the Fourier Transform of f at \eta we just need to add up the integrals of f along the lines in direction \theta — Xf(y, \theta) — weighted it by the value of the wave on these lines.  In other words

\hat{f}(\eta) = \int_{\theta^\perp}e^{-iy\cdot\eta}Xf(y,\theta)dH_{\theta^\perp}(y) = \mathfrak{F}_{\theta^\perp}Xf(\eta, \theta)

for \eta \in \theta^\perp.  Notice that our choice of \theta was arbitrary, so this really gives us a continuum of formulas, one for each \theta \in \eta^\perp.

Tags: , ,
Posted in Inverse Problems | 1 Comment »

Inverse Problems Course Notes — The X-Ray Transform

November 16, 2009

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. Read the rest of this entry »

Tags:
Posted in Inverse Problems | 2 Comments »

Inverse Problems Course Notes — The Paley-Wiener Theorem

November 13, 2009

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 Read the rest of this entry »

Tags:
Posted in Inverse Problems | Leave a Comment »

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

November 12, 2009

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 Read the rest of this entry »

Tags:
Posted in Inverse Problems | Leave a Comment »

« Older Entries
Follow

Get every new post delivered to your Inbox.