Russell Luke research (inverse problems, scattering, optics, nonsmooth optimization, nonconvex programming)

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. This work has been supported in part by grants from the National Science Foundation (grant Numbers 0712796 and 0852454) and more recently from the German Research Foundation (Collaborative Research Center 755 and Graduiertenkolleg 1023).

Variational Analysis and Optimization

General

" Duality and Convex Optimization ", with Jonathan Borwein in Handbook of Imaging (to appear).

We survey Fenchel duality theory with applications to imaging and inverse scattering.

Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. Bauschke, R. Burachick, P. Combettes, V. Elser, R. Luke, H. Wolkowicz, ed. Springer Verlag (2011).

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 Linear Convergence of Approximate Projections onto Regularized Sets '', D. R. Luke, Nonlinear Analysis, DOI: 10.1016/j.na.2011.08.027. (2011). (preprint: arXiv:1108.2243v3)

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.

`` Local convergence for alternating and averaged nonconvex projections ", A.S. Lewis, D.R. Luke and J.M. Malick. Foundations of Computational Mathematics 9(4):485--513 (2009).

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 (2008)

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.

`` MUSIC for extended scatterers as an instance of the Factorization Method.'', with Tilo Arens and Armin Lechleiter. SIAM J. Appl. Math. 70(4):1283-1304 (2009).

Recent work of Luke and Devaney showed that there exists an implementation of a modified linear sampling method that is equivalent to a MUSIC algorithm for scattering from sound soft obstacles. The correspondence is independent of the size of the scatterer or the wavelength of the incident field. As the proof was not constructive, an explicit implementation could not be justified. In the present work, we show that MUSIC is an instance of the factorization method applied to any nonabsorbing scatterer, thus providing a justification for the MUSIC algorithm at arbitrary illuminating frequency for arbitrary nonabsorbing scatterers. These results are also extended to scattering from cracks. With explicit constructions in hand, we are also able to provide error and stability estimates for practical implementations in noisy environments with limited data and to explain a curious behavior of the factorization method in the case of noisy data.

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

top

Software

SAMSARA a reverse communication optimization toolbox for MATLAB. A Fortran90 version is on the way.

WIEN2k DFT calculations of solids by P. Blaha, K. Schwarz, G. Madsen, D. Kvasnicka and J. Luitz (I have contributed to the "mixer")

Dirichlet scattering data (June 15, 2006)

Projection Algorithm tools (last updated August, 2011)

Word Counter thanks to JavaScript Kit

top

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

I have had the priviledge to collaborate with the following researchers over the years:
Tilo Arens
David Bailey
Heinz Bauschke
Jonathan Borwein
Regina Burachik
Jim Burke
Neil Calkin
Patrick Combettes
Roland Girgensohn
Tony Devaney
Thorsten Hohage
Armin Lechleiter
Adrian Lewis
Laurie Marks
Victor Moll
Axel Munk
Roland Potthast
Henry Wolkowicz

top

(main page)

Continuous Optimization, Variational Analysis,

and Inverse Problems

Experimental Mathematics