Chapter 1

Background

1.1 Overview ......................................................... 2

1.1.1 Fourier-Transform Data ................................. 2

1.1.2 Transmission Tomography ............................... 3

1.1.3 Emission Tomography ................................... 3

1.2 An Urns Model for Remote Sensing ............................. 4

1.3 Hidden Markov Models .......................................... 5

1.4 Measuring the Fourier Transform ................................ 6

1.4.1 The Discrete Fourier Transform ......................... 7

1.4.2 The Unknown Amplitude Problem ...................... 7

1.4.3 Limited Data ............................................ 9

1.4.4 Can We Get More Information? ......................... 9

1.4.5 Over-Sampling ........................................... 10

1.4.6 A Projection-Based View ................................ 11

1.4.7 Other Forms of Prior Knowledge ........................ 12

1.5 Transmission Tomography ....................................... 14

1.5.1 The ART and MART .................................... 14

1.5.2 The ART in Tomography ............................... 15

1.5.3 The ART in the General Case ........................... 16

1.5.3.1 When Ax = b Has Solutions ............... 18

1.5.3.2 When Ax = b Has No Solutions ........... 18

1.5.4 The MART .............................................. 19

1.5.4.1 A Special Case of MART .................. 19

1.5.4.2 The MART in the General Case ........... 20

1.5.4.3 Cross-Entropy .............................. 21

1.5.4.4 Convergence of MART ..................... 21

1.6 Emission Tomography ........................................... 22

1.6.1 The EMML Algorithm .................................. 22

1.6.2 Relating the ART and the EMML ...................... 23

1.7 A Unifying Framework ........................................... 24

1

2 Iterative Optimization in Inverse Problems

1.1 Overview

A fundamental inverse problem is the reconstruction of a function from

ﬁnitely many measurements pertaining to that function. This problem is

central to radar, sonar, optical imaging, transmission and emission tomog-

raphy, magnetic resonance imaging, and many other applications. Because

the measured data is limited, it cannot serve to determine one single correct

answer. In each of these applications some sort of prior information is incor-

porated in the reconstruction process in order to produce a usable solution.

Minimizing a cost function is a standard technique used to single out one

solution from the many possibilities. The reconstruction algorithms often

employ projection techniques to guarantee that the reconstructed func-

tion is consistent with the known constraints. Typical image reconstruc-

tion problems involve thousands of data values and iterative algorithms

are required to perform the desired optimization.

1.1.1 Fourier-Transform Data

We begin with an example of a common remote-sensing problem in

which the available data are values of the Fourier transform of the function

we wish to reconstruct. In our example the function we wish to reconstruct

is the amplitude function associated with a spatially extended object trans-

mitting or reﬂecting electromagnetic radiation. Problems of this sort arise

in a variety of applications, from mapping the sources of sunspot activity to

synthetic-aperture radar and magnetic-resonance imaging. Our example is

a somewhat simpliﬁed version of what is encountered in the real world, but

it serves to illustrate several key aspects of most remote-sensing problems.

From this example we see why it is that the data is limited, apart, of course,

from the obvious need to limit ourselves to ﬁnitely many data values, and

come to understand how resolution depends on the relationship between

the size of the object being imaged and the frequency of the probing or

transmitted signal.

Because our data is limited and the reconstruction problems are under-

determined, we are led to consider constrained optimization methods, such

as constraint-consistent minimum-norm reconstructions. Once we have set-

tled on an appropriate ambient space, usually a Hilbert space, in which to

place the function to be reconstructed, it is reasonable to take as the re-

construction the data-consistent member of the space having the smallest

norm. If we have additional constraints that we wish to impose, we can

use orthogonal projection onto convex sets to satisfy the constraints. A

key step, and one that is too often overlooked, is the choice of the ambient

space. As we shall see, soft constraints coming from prior information, such

Get *Iterative Optimization in Inverse Problems* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.