Spring 2008

 CONTENTS:

 From the Director

 In this issue:

 Recent Programs

 Upcoming Programs

 Upcoming Opportunities

 Publications/Preprints

 Subscribe/Unsubscribe

 Other issues

 IMA Home

IMA Outcomes

Outcomes, impacts, highlights, nuggets... whatever name they go by, these short, novice-friendly research descriptions are just one of the ways the IMA shares the achievements of its visitors with the scientific community and strives to increase public appreciation of applied mathematics. The links to some of our most intriguing stories can be found on our homepage to give visitors a glimpse of the fascinating research connected with the IMA. If your research has been influenced by a visit to the IMA, whether as a workshop participant, long-term visitor, or postdoc, please share your story with us!

Travel Time Tomography

Inverse Problems are problems where causes for a desired or observed effect are to be determined. They arise in all fields of science and technology. An important example is to determine the density distribution inside a body from measuring the attenuation of X-rays sent through this body, the problem of "X-ray tomography."

Two types of inverse problems have intimate connections with a Riemannian manifold with boundary in differential geometry. For the first type of problem one considers solutions of the Laplace equation on the manifold. One imposes a function f everywhere on the boundary. Then there is a unique solution u of the Laplace equation with these values on the boundary and this determines the normal derivative of the solution at the boundary. The question is how to determine the metric at each interior point in the manifold if we know the normal derivative on the boundary for all boundary values f. This problem was solved by Matti Lassas and Gunther Uhlmann in 2001. An example application is Electrical Impedance Tomography (EIT) which has been proposed recently as a useful diagnostic tool. In this case the question is to determine the internal conductivity of a body by making voltage and current measurements at the boundary. EIT might be an useful inverse technique for early breast cancer detection since the conductivity of breast tumor is significantly higher than of normal tissue.

The second, seemingly unrelated inverse problem is to determine the metric at each interior point in the manifold if we know the geodesic distance I(x,y) between any pair of points x,y on the boundary. This is called the boundary rigidity problem. For example, our knowledge of the Earth's interior is indirectly derived from surface measurements. Scientists use the information provided by earthquakes to penetrate deeply into its interior. Mathematically, this is an inverse problem: Can one determine the sound speed of the Earth from travel times of seismic waves? In this case the sound speed depends on direction as well as position and is modeled as a Riemannian metric. Finding the sound speed at each interior point is just the boundary rigidity problem.

A connection between these two quite different inverse problems was proposed, as a conjecture, at the lecture by Uhlmann at the IMA summer school on on "Geometrical Methods in Inverse Problems and PDE Control" in the summer of 2001. Leonid Pestov and Uhlmann started to work on this problem at the IMA workshop and in 2005 solved it for two-dimensional manifolds. They showed that the geodesic distance data on the boundary from the second problem enables one to to determine the map relating the function f and its normal derivative on the boundary from the first problem, hence to determine the metric. The result has now been extended to manifolds in higher dimensions.

Shedding Light on Optics

What you see is what you get... except when the thing you are looking at is either very small or very far away (all a matter of perspective). Take, for instance, the light from a street lamp projected through a hole the size of a fork tine in a screen. If you place another screen just behind the hole what you will see is an image of the hole. But as you move the second screen further and further away, the image of the hole starts to blur. Move the second screen far enough away, and — if your eyes are sensitive enough — you will see light and dark rings appear. These rings are the diffraction pattern of the hole in the first screen, known to mathematicians as the Fourier transform of the hole, or at least the amplitude thereof. Not many people can look at a diffraction pattern and recognize what the original object is. Watson, Crick and Franklin famously "decoded" xray diffraction patterns to reveal the true structure of DNA. Thanks to the Fast Fourier Transform — and fast microprocessors — Fourier transforms are easy to invert, so that today, in principle, anyone could recover the image of the original hole by simply inverting the diffraction pattern, but for one problem: the observation is of the amplitude of the Fourier transform, not the Fourier transform itself. This is a central problem facing crystallographers and anyone else that uses diffraction imaging to infer the structure of the things through which light passes.

Long-term IMA visitor Russell Luke (University of Delaware) has been fascinated by mathematical algorithms for solving this problem (known as the phase retrieval problem) ever since his PhD thesis on the theory and practice of wavefront reconstruction for NASA's James Webb Space Telescope, Hubble's replacement. The phase retrieval problem is a vexing instance of a nonconvex feasibility problem, for which there is scant theory, though recent work by Luke and collaborators is beginning to shed some light on this issue.

While at the IMA Luke attended as series of lectures by organizer David Brady (Duke University) on optical imaging. At one of the lectures Brady gave to the audience plastic glasses which made the letters "DUKE" appear to the wearer whenever Brady used his laser pointer to emphasize important items in his talk on the overhead screen. Brady's glasses were patented and mass-produced by a manufacturer with a high-tech printer, but Luke was confident that he could produce a less glamorous version of the glasses with nothing more than an ordinary laser printer, transparency film, and mathematical software such as Matlab. With the help from an instructional grant from the University of Delaware, and space provided in the Mathematical Sciences' Modeling Experiment and Computation Lab at UD, Luke built a diffraction optical bench with which students can design their own glasses. Following a very nicely-written recipe by Thad Walker (University of Wisonsin), the student starts with the image she want to appear through the glasses and then, with software written by Luke, computes a binary mask that will produce the desired image as the diffraction pattern of the mask. The image is a very simple version of a hologram. Luke uses the bench to teach mathematics students about the physical nature of Fourier transforms, and to teach science/engineering students about the mathemetical nature of diffraction. On a deeper level, the lab provides a very tangible instance of some of the frontiers of mathematical computation.

Figure 1: Grating (actual size) printed on transparency film with ordinary laser printer.



Figure 2:Diffraction image (magnified) of grating

References

J.V. Burke and D.R. Luke, "Variational analysis applied to the problem of optical phase retrieval," SIAM J. Contr. Optim., 42 (2003), pp. 576-595.

D.R. Luke, "Relaxed averaged alternating reflections for diffraction Imaging," Inverse Problems, 21 (2005), pp. 37-50.

D.R. Luke, J.V. Burke, and R.J. Lyon, "Optical wavefront reconstruction: Theory and numerical methods", SIAM Rev, 44 (2002), pp. 169-224.

T. Walker, "Holography Without Photography," University of Wisconsin, Department of Physics Technical Report (1998)

Voronoi Diagram of Ellipses

Innumerable scientific and engineering applications from geology to telecommunications lead to the same problem: given a set of objects, find which object is nearest to any particular point. The Voronoi diagram answers this question for every point on the plane by dividing the plane into cells containing the points nearest each object. Because this question arises in so many applications, highly efficient algorithms and codes for computing Voronoi diagrams have been developed in the case the objects are idealized as simple points. I. Emiris and E. Tsigaridas of the National University of Athens visited the IMA during the 2006-2007 program on Algebraic Geometry and focused on the problem of extending efficient algorithms for computing exact Voronoi diagrams to the case of more general objects which can be described algebraically, such as ellipses.

The hardest module to extend was something called the InCircle predicate, which decides the relative position of a query ellipse with respect to a circle externally tangent to three other ellipses. Emiris, Tsigarides, and Ph.D. student G. Tzoumas reduced this query to calculations on algebraic numbers of degree 184. To make these calculations rapidly, they figured out an approach combining certified numerical algorithms with algebraic computations.

The work of Emiris, Tsigarides, and Tzoumas provides the first complete implementation for the exact computation of the Voronoi diagram of ellipses. It is targeted for inclusion in the open source computational geometry library, CGAL, and so will join the toolbox available to mathematicians and scientists.

Related material