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}


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


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


\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

The Geometry of the Slice Theorems

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 \thetaXf(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.

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

Expressing Exponential-Type Conditions in Terms of Derivative Growth Rates

When I talked about my alternative proof of Helgason’s support theorem in class, I  asserted that our function \hat{f} had compact support in B_A(0) if and only if its partial derivatives satisfied |\partial^{\alpha}_\xi\hat{f}(0)| \leq CA^{|\alpha|} for any multi-index \alpha.

In other words, a function is of exponential type if its partial derivatives grow like those of an exponential function.

This is true, but the claims I stated on the board were not correct — I did not mention the fact that we needed to use extra information about f, in particular the fact that f \in \mathcal{S}(\mathbb{R}^n) is all we need to complete our proof.

It is possible to state much more general results, but to get the idea across let me state the following result  in one dimension:

Claim Assume f \in \mathcal{S}(\mathbb{R})  then \text{supp} f \subset [-A, A] if and only if \hat{f} is entire analytic and for all n

\big |\frac{d^n\hat{f}}{dz^n}(0) \big | \leq C A^n

for some constant C. 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