The unifying focus of my work is algorithms, and my approach is best described
by the experimental mathematics philosophy discussed below.
My research in variational analysis, optimization and inverse problems
is motivated by applications in three areas: image processing,
inverse scattering, and, more recently,
computational quantum chemistry.
I have grouped my publications into two principal mathematical disciplines,
variational analysis/optimization
and scattering theory.
This grouping represents the distinct theoretical
tools that I both use and seek to extend, though the two areas overlap to some degree.
A third category, experimental mathematics,
characterizes my broader vision of
mathematics and the practice of mathematical research. Within each discipline area
I have grouped papers by application and research thread.
I describe the content of each paper and how it relates to my own research
in the cases where the paper was a collaborative effort. All but three of my collaborative
papers follow the standard practice in mathematics of listing authors alphabetically to
reflect the fact that these are equally shared efforts. In the cases where alphabetical
ordering was not followed, the lead author is listed first.
See below for software
industry collaboration, and
my research collaborators.
I am grateful for the support of the
National Science Foundation.
Experimental Mathematics
The experimental
approach to pure mathematical research has been the topic of several books and
articles by my former postdoctoral adviser, Jonathan Borwein.
In my work, experimental mathematics involves formal results inspired by
experimentation, conjectures suggested by experiments, and algorithms and
software for mathematical
exploration.
-
Experimental Mathematics in Action, with David Bailey,
Jonathan Borwein, Neil Calkin, Roland Girgensohn, and Victor Moll. A. K. Peters (2007).
I edited the book and wrote the chapter on inverse scattering. There is a more practical
version of the no response test that yields a computable indicator function, unlike
my original no response paper with Potthast where the indicator function was the
solution to an infinite dimensional optimization problem.
-
`` Dynamics of a Ramanujan-type Continued Fraction with
Cyclic Coefficients"
with Jonathan Borwein, The Ramanujan Journal (to appear).
This is the first paper we submitted on this topic, though
the Ramanujan Journal has waited more than 3 years to bring this
to published form.
-
`` Dynamics of a Continued
Fraction of Ramanujan with Random Coefficients"
with Jonathan Borwein. Abstract and Applied Analysis 2005(5):449--467(2005).
My work with Borwein on
convergents of continued fractions grew out of a search for alternative strategies
that might be helpful in proving convergence of nonconvex projection algorithms.
Borwein originally posed the convergence problem
for cyclic coefficients (see above) and in the course of settling that question
I found a way to apply
Kolmogorov's Martingale Convergence Theorem to answer more generally the question
of convergence for random coefficients. The experimental nature of this research
stems from the fact that we had numerical evidence of convergence with
random coefficients before we could prove it.
top
Variational Analysis and Optimization
Phase Retrieval
The phase retrieval problem in its abstract form involves determining the
phase of a complex-valued function from magnitude measurements and other
a priori information. This is a well-known nonconvex optimization problem
with applications ranging from adaptive optics with the Hubble Space Telescope
and it's replacement, the James Webb Space Telescope, to electronic
structure determination in crystallography. As a high-profile instance of ill-posed
nonconvex optimization, I have sought to provide efficient algorithms together with
theory for how and why they work.
- "Relaxed
Averaged
Alternating Reflections for Diffraction Imaging", Inverse
Problems 21:37-50(2005).
The theory of
convex optimization is used to develop and to gain insight into counterparts for
the nonconvex problem of phase retrieval. We propose a relaxation of averaged
alternating reflectors and determine the fixed-point set of the related operator
in the convex case. The advantage of the method is that it has fixed points, where
the leading method does not. A numerical study supports our theoretical observations
and demonstrates the effectiveness of the algorithm compared to the current
state of the art.
- ``A New Generation of
Iterative Transform
Algorithms for Phase Contrast Tomography'',
D. R. Luke, H.H. Bauschke,
and P. L. Combettes. Proceedings
of the IEEE 2005 International
Conference on Acoustics, Speech and Signal Processing,
(Philadelphia, PA, 2005).
This is a distillation of our previous work introducing new projection
algorithms.
The rejection rate for this conference was over 50 percent.
- ``Variational
analysis applied to the problem of optical phase retrieval", J. V. Burke
and D.R. Luke. SIAM J. Control Opt. 42(2):576-595
(2003).
We apply nonsmooth analysis to the phase retrieval problem.
The state-of-the-art within the application literature for solving this problem
involves iterated projections. Despite
widespread use of these algorithms, mathematical theory could not explain
their success since the problem is a nonconvex, inconsistent feasibility problem. At the
heart of projection algorithms is a nonconvex, nonsmooth optimization problem.
We obtain some insight into these algorithms by applying techniques from
nonsmooth analysis. We show that the weak closure of the set of
directions toward the projection generate the subdifferential of the corresponding
squared set distance function. This result is generalized to provide conditions under which the
subdifferential of an integral function equals the integral of the subdifferential.
- "A
Hybrid
Projection Reflection Method for Phase Retrieval", H. H. Bauschke,
P.L. Combettes,
and D. R. Luke. J. Opt. Soc. Am. A , 20(6):1025-1034
(2003).
Following up on our 2002 paper, we introduce a new projection-based
method, termed the Hybrid Projection Reflection (HPR) algorithm,
for solving phase retrieval problems featuring
nonnegativity constraints in the object domain.
Motivated by properties of the HPR algorithm for convex constraints,
we recommend an error measure studied by Fienup more than twenty years ago.
This error measure, which has received little attention in the literature,
lends itself to an easily implementable stopping criterion.
In numerical experiments, we found the HPR algorithm to be a competitive
alternative to the HIO algorithm and the stopping criterion to be
reliable and robust.
- "
A Simple Multiresolution Technique for Diffraction Image
Recovery,'' in the Pacific
Institute for the Mathematical Sciences Newsletter, 7(2):17-20
(2003).
In this invited article I describe a technique for solving the phase problem on
a coarse grid in the pupil plane and using the coarse resolution solution as the
initialization of the higher-resolution problem. We reduce computation time
for the high-resolution problem by a factor of 17.
- ``Optical
Wavefront
Reconstruction: Theory and Numerical Methods'', D. R.
Luke, J.
V.
Burke
and R. G. Lyon. SIAM
Review 44:169-224 (2002).
This review provided a tutorial on the physical derivation of the phase problem,
a survey of problem statements and algorithmic approaches (line search versus
projection algorithms), and proposed a large-scale nonlinear optimization approach
introducing a dynamic weighting of different observations using a log-likelihood
functional in an extended least squares format, solved numerically using
a limited memory BFGS algorithm with an explicit trust region.
- Analysis
of Optical Wavefront Reconstruction and Deconvolution in Adaptive Optics,
Dissertation, Department of Applied Mathematics, University of
Washington,
June 2001.
Much of this thesis has been published in refereed journal articles.
- ``Fast
Algorithms for Phase Retrieval and Deconvolution'', in Proceedings
of the Workshop on Computational Optics and Imaging for Space
Applications pp.130-150 (NASA/Goddard Space Flight Center,
May 10-12,
2000).
Projection Algorithms
The most widely used numerical techniques
for solving the phase problem are projection algorithms. The theory for
these algorithms, however, is largely limited to convex, consistent problems,
neither of which characterizes the phase problem. My goal has been to extend the
theory of these algorithms to nonconvex and inconsistent problems, and to
explain why the current methods work so well.
Much of this work has been in collaboration with
Heinz Bauschke (University of Guelph, Canada) and
Patrick Combettes (Université Pierre et Marie Curie - Paris 6).
We have published 6 articles since 2002 on this topic
focusing mainly on identifying commonly
used algorithms in the optics community with convex analogs in the mathematics
community and using convex analysis to improve upon them. Together, this research
has over 38 citations, not including self-citations.
I have continued this work independently to develop a nonconvex extension of these algorithms.
This work, though newer, has generated over 4 non-self citations
so far. I have recently collaborated with Adrian Lewis at Cornell University
and Jeròme Malick of University of Grenoble to investigate rates of convergence
for some common iterative algorithms, and crucial notions of regularity of solutions.
- ``
Local convergence for alternating and averaged
nonconvex projections ", A.S. Lewis,
D.R. Luke and J.M. Malick. Preprint (submitted).
A classical result due to Gubin, Polyak and Raik is that alternating projections
between two closed convex sets with regular intersection converges linearly.
We show that, assuming strong regularity of the intersection, local
linear rates of convergence require certain regularity of only one of the
sets. We introduce the notion of super regularity of sets that includes,
but is not limited to, prox-regularity and show that alternating projections between
a closed set and a super regular set with strongly regular intersection converges locally
linearly. This result is extended to averaged projections between more than two sets
and improved rates of convergence in the presence of prox-regularity.
The characterization of strong regularity for intersections
of several sets and refinements of convergence of averaged projections in the presence
of prox-regularity is directly related to my independent work to appear in SIOPT
on the convergence of projection algorithms for nonconvex problems where the
solution is not metrically regular. There is a vexing theoretical gap between these
two papers: sets with metrically regular intersections need not generate
firmly nonexpansive compositions of projection mappings, and locally
firmly nonexpansive compositions of projection mappings need not
correspond to sets with metrically regular intersection.
- ``
Finding Best Approximation Pairs Relative to
a Convex and a Prox-regular Set in a Hilbert Space", D.R. Luke.
SIAM J. Opt 19(2): 714--739 (2008).
In this paper I establish local convergence of nonconvex, ill-posed instances of
the Relaxed Averaged Alternating Reflections
(RAAR) algorithm proposed in my 2005 Inverse Problems paper for solving the phase problem.
To place the RAAR algorithm in context, I unify this and more conventional
algorithms (alternating projections and steepest descents, in particular)
in the convex case as instances of
the Lions-Mercier algorithm applied to a sum of regularized maximal monotone mappings.
- "Finding
Best Approximation Pairs Relative to Two Closed Convex Sets in Hilbert
Spaces", with H. Bauschke and P. Combettes,
Journal of Approximation Theory 127:178-192(2004).
We consider the problem of finding a best approximation pair, i.e., two
points which achieve the minimum distance between two closed convex sets
in a Hilbert space. When the sets intersect, the method under consideration,
termed AAR for averaged Alternating reflections, is a special instance of an
algorithm due to Lions and Mercier for finding a zero of the sum of two
maximal monotone operators. We investigate systematically the asymptotic
behavior of AAR in the general case when the sets do not necessarily
intersect and show that the method produces best approximation pairs provided
they exist. Finitely many sets are handled in a product space,
in which case the AAR method is shown to coincide with a special case of
Spingarn's method of partial inverses.
My work on Theorem 3.5 of this paper lead to my subsequent development of
the Relaxed AAR method (RAAR) that first appeared in 2005 with
further theoretical detail to appear in 2008.
-
`` A Strongly Convergent Reflection Method for Finding the Projection
onto the Intersection of Two Closed Convex Sets in a Hilbert Space"
with H. H. Bauschke and P. L. Combettes, Journal of Approximation Theory
141(1):63-69 (2006).
This paper explores an extension to the Averaged Alternating Reflection algorithm studied
in our 2004 paper. The extension follows a strategy introduced in a
Ph.D. thesis in 1968 by French mathematician Haugazeau which yields strong convergence
in a Hilbert space as opposed to the more routine weak convergence.
The conventional wisdom is that a strongly convergent algorithm in infinite dimensions will
perform better than a weakly convergent algorithm when discretized.
- `` On the
structure of Some Phase Retrieval Algorithms'',
H.H. Bauschke,
P. L. Combettes,
and D. R. Luke. Proceedings of the IEEE
International Conference
on Image Processing, vol II, pp. 841-844 (Rochester, NY,
September 22-25, 2002).
This conference proceeding is a distillation of our previous work connecting
algorithms that are well-known in the optics community with more general
algorithms of Dykstra, Lions and Mercier.
- ``Phase
retrieval,
error reduction algorithm, and Fienup variants: A view from convex
optimization'',
H.H. Bauschke,
P.L. Combettes,
and D. R. Luke. J. Opt. Soc. Am. A, 19(7):1334-1345
(2002).
The purpose of this paper is to formulate the phase retrieval problem
with mathematical care and to establish new connections between well
established numerical phase retrieval schemes and classical convex
optimization methods. Specifically, it is shown that Fienup's basic
input-output algorithm corresponds to Dykstra's algorithm, and that
Fienup's hybrid input-output algorithm can be viewed as an instance of the
Douglas-Rachford algorithm. This work provides a theoretical framework to
better understand and improve existing phase recovery.
top
Computational Chemistry
This work concentrates on the forward problem
of simulating macro-properties of solid-state materials from scales at the
quantum level. Our first of a series of papers on this topic was recently submitted and
concerns the application of limited memory multisecant methods for solving
nonlinear eigenvalue problems (Schroedinger's equation) in density functional theory.
New numerical
techniques stemming from this work have been included in the latest release of the
WIEN2k computational chemistry toolbox out of T.U. Vienna. This software has
over 1000 registered users. Our code has improved upon the state of the art
by, on average, a factor of 2 to 3, though in many cases our method is the only one
that works without expert guidance. While our algorithm has not cracked any unsolved
problems yet, we have made solvable many hard problems that once were out of reach
for nonexperts. The majority of the computational complexity comes from function
evaluations, even though the dimensionality of the problem is
relatively small (1000-10000 unknowns). Future work will place greater emphasis on
numerical optimization to optimize less computationally complex objectives. For this
we will expand on the extended least squares framework described in our 2002
SIAM Review paper with Burke and Lyons with and extension of limited
memory BFGS updates to a multi-secant BFGS based on Broyden's second
method.
- "Robust Mixing for Ab-Initio Quantum
Mechanical Calculations", L. D. Marks
and D. R. Luke Phys. Rev. B (to appear)
We use a multi-secant generalization of Broyden's second method
to solve the nonlinear Schr\"odinger equation. The paper leaves open several
mathematical issues that will be explored in a more technical paper to follow. Among
these issues are the scaling of the diagonal matrix used to initialize the matrix secant
update, and the ordering of the memory elements. Our current implementation for the
computational chemistry problem has a natural extension to what we call Jacobian simplex
techniques for solving vector-valued equations.
top
Inverse Scattering Theory
This work has developed from a two-year postdoctoral research position
with Rainer Kress' group at the University of Goettingen.
My work has focused mainly on noniterative
integral equation techniques for obtaining qualitative information about
scattering obstacles from far field measurements.
This work is in collaboration with
Roland Potthast of the University of Goettingen
and more recently with Anthony Devaney of Northeastern University.
I have also published two independent works in this area.
Collectively, this work has received over 14 non-self citations so far.
-
`` Identifying scattering obstacles by the
construction of nonscattering waves'', with Tony Devaney.
SIAM J. Appl. Math. (2007).
I used the linear sampling method, together with the point source method of Potthast to
prove the existence of a wave with arbitrarily small scattered field on the exterior of
a Dirichlet obstacle. We use such an incident field to implement a MUSIC-type
algorithm for determining the shape and location of extended scatterers without
restrictions on the size of the obstacles or the frequency of the incident field.
Though our numerical experiments demonstrated a ``proof of concept'' the
theory for how one generates such a field was not resolved in this paper with
Devaney. Together with Tilo Arens and Armin Lechleiter of the University of Karlsruhe,
I have since come up with a constructive proof that also yields a theoretical
justification of the numerical experiments in the paper with Devaney.
-
`` The Point Source Method for Inverse
Scattering in the Time Domain'', with Roland Potthast.
Mathematical Methods in the Applied Sciences 29(3):
1501--1521(2006).
Our goal here is
twofold: first, to establish conditions on the time-dependent waves that provide a
correspondence between time domain and frequency domain inverse scattering via Fourier
transforms without recourse to the conventional limiting amplitude principle;
secondly, we apply the analysis in the first part of this work toward the extension of a particular
scattering technique, namely the point source method, to scattering from the requisite pulses.
Numerical examples illustrate the method and suggest that reconstructions from admissible
pulses deliver superior reconstructions compared to straight averaging of multi-frequency
data.
-
`` Image synthesis for inverse obstacle scattering using
the eigenfunction expansion theorem'',
Computing 75(2-3):181-196(2005).
Potthast's point source method and its relatives
determine the boundary of an unknown
obstacle by reconstructing the surrounding scattered field.
In the case of sound soft obstacles, the boundary is
usually found as the minimum contour of the total field.
In this work we derived a different approach for imaging the boundary
from the reconstructed fields based on a generalization of the
eigenfunction expansion theorem that is an extension to scattering
obstacles of work by Rose and Cheney (1988). The aim of this alternative
approach is the construction of higher contrast images than is
currently obtained with the minimum contour approach.
- ``Multifrequency
inverse obstacle scattering: the point source method and generalized
filtered backprojection'' Mathematics and Computers in Simulation
66:297-314(2004).
In this work I present Potthast's point source method for multifrequency data
as a nonlinear generalization of the filtered backprojection algorithm and compare this
generalization to the usual filtered backprojection technique based on the physical
optics approximation. The practical importance of the paper is to show how one should
average multifrquency data for reconstructions. This paper should get more attention
as essentially single frequency, time-harmonic inverse scattering techniques are
extended to time-domain inverse scattering.
- ``The
no response test - a sampling method for inverse scattering problems ",
D. R. Luke and R. Potthast.
SIAM J. App. Math. , 63(4):1292-1312 (2003).
The main theoretical interest of the paper is that this is a technique
for determining the shape of scatterers from a single incident wave.
- ``The
Point Source Method in Acoustic Scattering : numerical
reconstruction
of the scattered field from far field measurements of inhomogeneous
media'',
D. R. Luke and R. Potthast. Proceedings of the IEEE 2002
International
Conference on Acoustics, Speech and Signal Processing,
pp.IV-3541-IV-3544 (Orlando, FL, May 13-17, 2002).
This is an application of Potthast's point source method to inhomogeneous media.
Software
Industry Cooperation
- ``Entfaltung von Laserspektren'', D. R. Luke and R.
Potthast.
for Lambda Physik AG, September 2001.
- ``An Integration of Ellipsometry into Inverse Rough Surface
Scattering'', Klaus Erhard, D. Russell Luke and Roland Potthast.
for Nannofilm, GmBH,
April 2002.
top
Research Collaborators
top
(main page)
