Continuous Optimization, Variational Analysis,
and Inverse Problems
Job Openings:
Research Projects:
The unifying focus of our work is algorithms,
and our approach is best described
by the experimental mathematics philosophy discussed below.
Our research in variational analysis, optimization and inverse problems
is motivated by applications in three areas: image processing,
inverse scattering, and
computational quantum chemistry.
I have grouped my publications into two principal mathematical disciplines,
variational analysis/optimization
and scattering theory.
This grouping represents the distinct phases and interests during my research career,
though the two areas overlap to some degree.
A third category, experimental and scientific mathematics,
characterizes my broader vision of
mathematics, the practice of mathematical research and the role these have in the empirical sciences.
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. Almost all 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 (Nahost Kooperation, Graduiertenkolleg 2088, Collaborative Research Center 755 and Graduiertenkolleg 1023), the
Bundesministerium fuer Bildung und Forschung, the German Israeli Foundation and the Australian Research Council.
Active Research Projects:
-
Mathematics of atomic orbital tomography
with Stefan Mathias (CRC1456 TPB01)
-
Stochastic computed tomography:
theory and algorithms for single-shot X-FEL imaging
with
Helmut Grubmueller (CRC1456 TPC02)
- Nonconvex Quadratic Composite Minimization: Theory and Algorithms,
with Marc Teboulle and
Shoham Sabach. (DFG, 2020-2022)
- Probabilistic Analysis and Stochastic Algorithms in Fixed Point Theory with Anja Sturm (GRK2088 TPB5)
- Discrete Topological Optimization Techniques for the Statistical Analysis of Tree Structures with Stephan Huckemann (GRK2088 TPA4)
A selection of expired research projects:
Conferences: I have been involved in the organization of the following events:
- International Conference on Continuous Optimization, Berlin, August, 2019
- Modern Maximal Monotone Operator Theory: From Nonsmooth Optimization to Differential Inclusions, Erwin Schroedinger International Institute for Mathematics and Physics, Vienna, January-March, 2019
- International Symposium on Mathematical Processing, Bordeaux, July, 2018
- Splitting Algorithms, Modern Operator Theory and Applications, Oaxaca, September 2017.
- Central European Set-Valued and Variational Analysis Meeting, Göttingen, Oct. 24, 2015
Experimental and Scientific 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. Much of this experimental exploration uses computers as a descriptive medium to
inspire and motivate formal proofs of abstract results, but I am also interested in the extent to
which bits and bytes really can approximate the ``Truth". Although computers are finite machines,
I do think that it is possible to
provide, with mathematical precision, quantitative statements about how close a numerical result
is to the solution of a given model problem. What the solution to a model problem has to do with
reality is beyond the reach of mathematical certainty, except, of course, where the model is demonstrably wrong.
-
``
Symbolic Computation with Monotone Operators
'', F. Lauster, D. R. Luke and M. K. Tam,
J. Set Valued and Variational Analysis, (to appear),
DOI 10.1007/s11228-017-0418-7
(arXiv:1703.05946).
We consider a class of monotone operators which are appropriate for symbolic representation and manipulation within a computer algebra system. Various structural properties of the class (e.g., closure under taking inverses, resolvents) are investigated as well as the role played by maximal monotonicity within the class. In particular, we show that there is a natural correspondence between our class of monotone operators and the subdifferentials of convex functions belonging to a class of convex functions deemed suitable for symbolic computation of Fenchel conjugates which were previously studied by Bauschke and von Mohrenschildt and by Borwein and Hamilton. A number of illustrative examples utilizing the introduced class of operators are provided including computation of proximity operators, recovery of a convex penalty function associated with the hard thresholding operator, and computation of superexpectations, superdistributions and superquantiles with specialization to risk measures.
-
``A Globally Linearly Convergent Method for Pointwise Quadratically Supportable Convex-Concave Saddle Point Problems'', D. R. Luke and R. Shefi, J. Math. Anal. and Appl. 457(2), 1568--1590 (2018).
We study the Proximal Alternating Predictor-Corrector (PAPC) algorithm introduced recently by Drori, Sabach and Teboulle to solve nonsmooth structured convex-concave saddle point problems consisting of the sum of a smooth convex function, a finite collection of nonsmooth convex functions and bilinear terms. We introduce the notion of pointwise quadratic supportability, which is a relaxation of a standard strong convexity assumption and allows us to show that the primal sequence is R-linearly convergent to an optimal solution and the primal-dual sequence is globally Q-linearly convergent. We illustrate the proposed method on total variation denoising problems and on locally adaptive estimation in signal/image deconvolution and denoising with multiresolution statistical constraints.
-
"Linear Convergence of the ADMM/Douglas Rachford Algorithms for Piecewise Linear-Quadratic Functions and Application to Statistical Imaging",
Timo Aspelmeier, C. Charitha and D. R. Luke SIAM J. Imaging Sci., 9(2):842-868, 2016. .
We prove that the alternating directions method of multipliers (ADMM) applied to convex, piecewise linear-quadratic objectives converges (eventually)
linearly to a global solution to the model problem. Our proof technique uses duality between the ADMM method and the
Douglas-Rachford algorithm applied to a dual problem. We actually prove eventual linear convergence of Douglas-Rachford for
convex piecewise linear quadratic objectives when the fixed point is isolated with respect to the affine hull of the iterates. The theory is
applied to the problem of image denoising and deconvolution with multi-resolution statistical side constraints that allow one to quantify,
in terms of standard deviations, the distance of the recovered/denoised image to the "true" image. We demonstrate the theory on
Stimulated Emission Deletion (STED) images obtained from the Laser-Laboratorium Göttingen .
-
"Local Linear Convergence of Approximate Projections onto Regularized Sets",
Nonlinear Analysis, 75(2012):1531--1546. DOI: 10.1016/j.na.2011.08.027. (preprint: arXiv:1108.2243v3).
In this solo publication I examine rates of convergence of a simple projection algorithm for nonconvex feasibility when only
approximate projections are computed. Extrapolation is also considered in this framework. The theory is applied to the
phase retrieval problem (see below). As far as I know, this is the
first time that local linear convergence of inexact alternating projections for consistent phase retrieval with nonnegativity
constraints has been proved. The theory is also applied to regularized phase retrieval where the diffraction images
have been corrupted by Poisson noise. The paper provides practitioners with a practical stopping rule with
guarantees of the distance of the final iterate to the model solution.
-
Fixed-Point Algorithms for Inverse Problems in Science and Engineering,
edited with , H. Bauschke, R. Burachik, P. Combettes, V. Elser, R. Luke, H. Wolkowicz, ed. Springer Verlag (2011).
This is a collection of articles on the state of the art (circa 2011) for, mostly, first-order methods. The volume
was a follow-up of a workshop organized by the editors in 2009 at the Banff International Research Station for
Mathematical Innovation and Discovery (BIRS).
-
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 (2008).
This is the first paper we submitted on this topic, though
the Ramanujan Journal took 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
General
-
``
Quantitative convergence analysis of iterated expansive,
set-valued mappings
'', D. R. Luke, and Nguyen T.H. and M. K. Tam,, Mathematics
of Operations Research (to appear).
arXiv:1605.05725.
We develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. There are two key components of the analysis. The first is a natural generalization of single-valued averaged mappings to expansive, set-valued mappings that characterizes a type of strong calmness of the fixed point mapping. The second component to this analysis is an extension of the well-established notion of metric subregularity ¿ or inverse calmness ¿ of the mapping at fixed points. Convergence of expansive fixed point iterations is proved using these two properties, and quantitative estimates are a natural byproduct of the framework. To demonstrate the application of the theory, we prove for the first time a number of results showing local linear convergence of nonconvex cyclic projections for inconsistent (and consistent) feasibility problems, local linear convergence of the forward-backward algorithm for structured optimization without convexity, strong or otherwise, and local linear convergence of the Douglas¿Rachford algorithm for structured nonconvex minimization. This theory includes earlier approaches for known results, convex and nonconvex, as special cases.
-
``Set Regularities and Feasibility
Problems
'', A. Y. Kruger, D. R. Luke, and Nguyen T.,
Mathematical Programming B (online 2016). DOI:10.1007/s10107-016-1039-x.
We synthesize and unify notions of regularity, both of individual sets and of collections of sets, as they appear in the convergence theory of projection methods for consistent feasibility problems. Several new characterizations of regularities are presented which shed light on the relations between seemingly different ideas and point to possible necessary conditions for local linear convergence of fundamental algorithms.
-
``About Subtransversality of Collections of Sets
'', A. Y. Kruger, D. R. Luke, and Nguyen T.,
Set-Valued and Variational Analysis, 25(4), 701-729 (2017).
In this paper the authors compare the uniform regularity property of collections of sets by A. S. Lewis, D. R. Luke and J. Malick in [Found. Comput. Math. 9(2009),no. 4, 485¿513] and relaxed regularity properties given by H. H. Bauschke, Luke, H. M. Phan and X. Wang (BLPW) in [Set-Valued Var. Anal.21 (2013), no. 3,431¿473 and 475-501] D. Drusvyatskiy, A. D. Ioffe and Lewis (DIL) in [Found. Comput. Math. 15 (2015),no. 6, 1637¿1651], and D. Noll and A. Rondepierre (NR) in [Found. Comput. Math.16(2016), no. 2, 425¿455]. Equivalent characterizations of these regularity properties in terms of metric, dual normal cone, and angle are provided. Two examples are provided to show that BLPW-DIL-restricted regularity and DIL-restricted regularity are different. They study inexact alternating projections for two possibly nonconvex sets. Under the assumptions of DIL-restricted regularity and uniform regularity together with the super-regularity of one set, respectively, the authors establish R-linear convergence rates.
-
"Lagrange Multipliers, (Exact) Regularization and Error Bounds for Monotone Variational Inequalities",
C. Charitha, J. Dutta and D. R. Luke Mathematical Programming A, 161(1):519-549, 2017..
We examine two central regularization strategies for monotone variational inequalities,
the first a direct regularization of the operative monotone mapping, and the second via
regularization of the associated dual gap function. A key link in the relationship between the
solution sets to these various regularized problems is the idea of exact regularization, which,
in turn, is fundamentally associated with the existence of Lagrange multipliers for
the regularized variational inequality. A regularization is said to be exact if a solution to the
regularized problem is a solution to the unregularized problem for all parameters
beyond a certain value. The Lagrange multipliers corresponding to a particular
regularization of a variational inequality, on the other hand, are defined via the dual gap function.
Our analysis suggests various conceptual, iteratively regularized
numerical schemes, for which we provide error bounds, and hence stopping criteria, under the
additional assumption that the solution set to the unregularized problem is what we call
weakly sharp of order greater than one.
-
"Linear Convergence of the ADMM/Douglas Rachford Algorithms for Piecewise Linear-Quadratic Functions and Application to Statistical Imaging",
Timo Aspelmeier, C. Charitha and D. R. Luke SIAM J. Imaging Sci., 9(2):842-868, 2016. .
We prove that the alternating directions method of multipliers (ADMM) applied to convex, piecewise linear-quadratic objectives converges (eventually)
linearly to a global solution to the model problem. Our proof technique uses duality between the ADMM method and the
Douglas-Rachford algorithm applied to a dual problem. We actually prove eventual linear convergence of Douglas-Rachford for
convex piecewise linear quadratic objectives when the fixed point is isolated with respect to the affine hull of the iterates. The theory is
applied to the problem of image denoising and deconvolution with multi-resolution statistical side constraints that allow one to quantify,
in terms of standard deviations, the distance of the recovered/denoised image to the "true" image. We demonstrate the theory on
Stimulated Emission Deletion (STED) images obtained from the Laser-Laboratorium Göttingen .
-
"Restricted normal cones and the method of alternating projections: theory '',
H. H. Bauschke, D. R. Luke, H. M. Phan and X. Wang, J. Set-Valued and Variational Analysis
21:431--473 (2013) DOI 10.1007/s11228-013-0239-2.
In this paper, we introduce and develop the theory of restricted normal
cones which generalize the classical Mordukhovich normal cone.
We thoroughly study these objects from the viewpoint of
constraint qualifications and regularity. Numerous examples are provided
to illustrate the theory. This work provides the theoretical underpinning
for a subsequent article in which these tools are applied to obtain a
convergence analysis of the method of alternating projections for nonconvex
sets.
-
"Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems '',
R. Hesse and D. R. Luke, SIAM J. Optim. 23(4), 2397-2419, 2013. arXiv:1212.3349.
We consider projection algorithms for solving (nonconvex) feasibility problems in Euclidean spaces.
Of special interest are the Method of Alternating Projections (MAP) and the Douglas-Rachford algorithm (DR).
In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields
global convergence of MAP and for consistent problems DR.
A notion of local sub-firm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems.
This, together with a coercivity condition that relates to the regularity of the collection of sets at points in the intersection,
yields local linear convergence of MAP for a wide class of nonconvex problems,
and even local linear convergence of nonconvex instances of the Douglas-Rachford algorithm.
-
"Prox-regularity of rank constraint sets and implications for algorithms '',
D. R. Luke, J. Math. Imaging and Vision, 47(3):231--328 (2013). DOI: 10.1007/s10851-012-0406-3
We present an analysis of sets of matrices with rank less than or equal to a specified number s.
We provide a simple formula for the normal cone to such sets, and use this to show that these sets
are prox-regular at all points with rank exactly equal
to s. The normal cone formula appears to be new.
This allows for easy application of prior results guaranteeing local linear convergence of
the fundamental alternating projection algorithm between sets, one of which is a rank constraint set.
We apply this to show local linear convergence of another fundamental algorithm,
approximate steepest descent.
Our results apply not only to linear systems with rank constraints, as has been treated extensively in the
literature, but also nonconvex systems with rank constraints.
-
"Local Linear Convergence of Approximate Projections onto Regularized Sets",
Nonlinear Analysis, 75(2012):1531--1546. DOI: 10.1016/j.na.2011.08.027. (preprint: arXiv:1108.2243v3).
In this solo publication I examine rates of convergence of a simple projection algorithm for nonconvex feasibility when only
approximate projections are computed. Extrapolation is also considered in this framework. The theory is applied to the
phase retrieval problem (see below). As far as I know, this is the
first time that local linear convergence of inexact alternating projections for consistent phase retrieval with nonnegativity
constraints has been proved. The theory is also applied to regularized phase retrieval where the diffraction images
have been corrupted by Poisson noise. The paper provides practitioners with a practical stopping rule with
guarantees of the distance of the final iterate to the model solution.
-
"Entropic Regularization of the l_0 Function '', J. M. Borwein and D. R. Luke, in
Fixed-Point Algorithms for Inverse Problems in Science and Engineering,
H. Bauschke, R. Burachik, P. Combettes, V. Elser, R. Luke, H. Wolkowicz, ed. Springer Verlag (2011).
Many problems of interest where more than one solution is possible seek,
among these, the one that is sparsest. The objective that most directly accounts for
sparsity, the counting function, is usually avoided since this leads to a combinatorial optimization problem. The counting function
is often viewed as the limit of the p-metrics.
Naturally, there have been some attempts to use this as an objective for
p small,
though this is a nonconvex function for p less than 1. We propose instead a scaled and
shifted Fermi-Dirac entropy with two parameters, one controlling the smoothness
of the approximation and the other the steepness of the metric. Our proposed metric
is a convex relaxation for which a strong duality theory holds, yielding dual methods
for metrics approaching the desired function. Without smoothing, we propose
a dynamically reweighted subdifferential descent method with "exact" line search
that is finitely terminating for constraints that are well-separated. This algorithm is
shown to recapture in a special case certain well-known "greedy" algorithms. Con-
sequently we are able to provide an explicit algorithm whose fixed point, under the
appropriate assumptions, is the sparsest possible solution. The variational perspec-
tive yields general strategies to make the algorithm more robust.
- "Duality and Convex Optimization ",
with Jonathan Borwein in Handbook of Imaging (2015).
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).
Nonconvex Feasibility
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 Britisch Columbia, Okanogan) and
Patrick Combettes (Université Pierre et Marie Curie - Paris 6), and more recently Adrian Lewis,
Hung Phan and Shawn Wang. I have continued this work independently with students
students Robert Hesse and Patrick Neumann to develop a fix point theoretic approach to nonconvex feasibility that extends more generally to first-order methods for nonsmooth/nonconvex
minimization.
-
``
Quantitative convergence analysis of iterated expansive,
set-valued mappings
'', D. R. Luke, and Nguyen T.H. and M. K. Tam,, Mathematics
of Operations Research (to appear).
arXiv:1605.05725.
We develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. There are two key components of the analysis. The first is a natural generalization of single-valued averaged mappings to expansive, set-valued mappings that characterizes a type of strong calmness of the fixed point mapping. The second component to this analysis is an extension of the well-established notion of metric subregularity ¿ or inverse calmness ¿ of the mapping at fixed points. Convergence of expansive fixed point iterations is proved using these two properties, and quantitative estimates are a natural byproduct of the framework. To demonstrate the application of the theory, we prove for the first time a number of results showing local linear convergence of nonconvex cyclic projections for inconsistent (and consistent) feasibility problems, local linear convergence of the forward-backward algorithm for structured optimization without convexity, strong or otherwise, and local linear convergence of the Douglas¿Rachford algorithm for structured nonconvex minimization. This theory includes earlier approaches for known results, convex and nonconvex, as special cases.
-
``Set Regularities and Feasibility
Problems
'', A. Y. Kruger, D. R. Luke, and Nguyen T.,
Mathematical Programming B (online 2016). DOI:10.1007/s10107-016-1039-x.
We synthesize and unify notions of regularity, both of individual sets and of collections of sets, as they appear in the convergence theory of projection methods for consistent feasibility problems. Several new characterizations of regularities are presented which shed light on the relations between seemingly different ideas and point to possible necessary conditions for local linear convergence of fundamental algorithms.
-
``About Subtransversality of Collections of Sets
'', A. Y. Kruger, D. R. Luke, and Nguyen T.,
Set-Valued and Variational Analysis, 25(4), 701-729 (2017).
In this paper the authors compare the uniform regularity property of collections of sets by A. S. Lewis, D. R. Luke and J. Malick in [Found. Comput. Math. 9(2009),no. 4, 485¿513] and relaxed regularity properties given by H. H. Bauschke, Luke, H. M. Phan and X. Wang (BLPW) in [Set-Valued Var. Anal.21 (2013), no. 3,431¿473 and 475-501] D. Drusvyatskiy, A. D. Ioffe and Lewis (DIL) in [Found. Comput. Math. 15 (2015),no. 6, 1637¿1651], and D. Noll and A. Rondepierre (NR) in [Found. Comput. Math.16(2016), no. 2, 425¿455]. Equivalent characterizations of these regularity properties in terms of metric, dual normal cone, and angle are provided. Two examples are provided to show that BLPW-DIL-restricted regularity and DIL-restricted regularity are different. They study inexact alternating projections for two possibly nonconvex sets. Under the assumptions of DIL-restricted regularity and uniform regularity together with the super-regularity of one set, respectively, the authors establish R-linear convergence rates.
-
"Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility",
R. Hesse, D. R. Luke and P. Neumann.
IEEE Transactions on Signal Processing , 62(18):4868--4881, 2014. (preprint: arXiv:1108.2243v3).
The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved nonconvex relaxations. In this work we consider elementary methods based on projections for solving a sparse feasibility problem without employing convex heuristics. It has been shown recently that, locally, the fundamental method of alternating projections must converge linearly to a solution to the sparse feasibility problem with an affine constraint. In this paper we apply different analytical tools that allow us to show
global linear convergence of alternating projections under familiar constraint qualifications. These analytical tools can also be applied to other algorithms. This is demonstrated with the prominent Douglas-Rachford algorithm where we establish
local linear convergence of this method applied to the sparse affine feasibility problem.
-
"Restricted normal cones and the method of alternating projections: applications ", H. H. Bauschke, D. R. Luke, H. M. Phan, and X. Wang.
J. Set-Valued and Variational Analysis , 21:475--501 (2013) DOI 10.1007/s11228-013-0238-3.
The method of alternating projections (MAP) is a common method for solving feasibility prob-
lems. While employed traditionally to subspaces or to convex sets, little was known about
the behavior of the MAP in the nonconvex case until 2009, when Lewis, Luke, and Malick de-
rived local linear convergence results provided that a condition involving normal cones holds
and at least one of the sets is superregular (a property less restrictive than convexity). How-
ever, their results failed to capture very simple classical convex instances such as two lines in a three-dimensional space.
In this paper, we extend and develop the Lewis-Luke-Malick framework so that not only
any two linear subspaces but also any two closed convex sets whose relative interiors meet
are covered. We also allow for sets that are more structured such as unions of convex sets.
The key tool required is the restricted normal cone, which is a generalization of the classical
Mordukhovich normal cone. Numerous examples are provided to illustrate the theory
-
"Restricted normal cones and the method of alternating projections: theory ", H. H. Bauschke, D. R. Luke, H. M. Phan, and X. Wang.
J. Set-Valued and Variational Analysis , 21:431--473 (2013) DOI 10.1007/s11228-013-0239-2.
In this paper, we introduce and develop the theory of restricted normal cones which gener-
alize the classical Mordukhovich normal cone. We thoroughly study these objects from the
viewpoint of constraint qualifications and regularity. Numerous examples are provided to il-
lustrate the theory. This work provides the theoretical underpinning for a subsequent article
in which these tools are applied to obtain a convergence analysis of the method of alternating
projections for nonconvex sets
-
"Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems '',
R. Hesse and D. R. Luke, SIAM J. Optim. 23(4), 2397-2419, 2013. arXiv:1212.3349.
We consider projection algorithms for solving (nonconvex) feasibility problems in Euclidean spaces. Of special interest are the Method of Alternating Projections (MAP) and the Douglas-Rachford algorithm (DR). In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields global convergence of MAP and for consistent problems DR. A notion of local sub-firm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems. This, together with a coercivity condition that relates to the regularity of the collection of sets at points in the intersection, yields local linear convergence of MAP for a wide class of nonconvex problems, and even local linear convergence of nonconvex instances of the Douglas-Rachford algorithm.
-
"Local Linear Convergence of Approximate Projections onto Regularized Sets",
Nonlinear Analysis, 75(2012):1531--1546. DOI: 10.1016/j.na.2011.08.027. (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.
I 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.
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.
-
``Phase Retrieval. What's New?
'', D. R. Luke,
SIAG/OPT Views and News, 25(1):1--5 (2017).
Ask an engineer to solve a problem and she will come back in a day or so with something that seems to work well enough most of the time. Ask a mathematician to solve the same problem and he will return many months later with an exact but unimplementable solution to a different problem. I'm sure most readers of this newsletter have heard some variation of that joke. But a true story lies somewhere in there, a story that is writ large with the phase retrieval problem.
-
"Proximal Heterogeneous Block Implicit-Explicit Method and Application to Blind Ptychographic Diffraction Imaging '',
R. Hesse, D. R. Luke, S. Sabach and M. K. Tam, SIAM J. on Imaging Sciences, 8(1):426--457 (2015).
We propose a general alternating minimization algorithm for nonconvex optimization problems with separable
structure and nonconvex coupling between blocks of variables.
To fix our ideas, we apply the methodology to the problem of blind ptychographic imaging.
Compared to other schemes in the literature, our approach differs in two ways: (i) it is
posed within a clear mathematical framework with practically verifiable assumptions, and
(ii) under the given assumptions, it is provably convergent to critical points. A numerical
comparison of our proposed algorithm with the current state-of-the-art on simulated and
experimental data validates our approach and points toward directions for further improvement.
-
"Reconstruction of wave front and object for inline holography from a set of detection planes '',
J. Hagemann, A.-L. Robisch, D. R. Luke, C. Homann, T. Hohage, P. Cloetens, H. Suhonen and T. Salditt, Optics Express 22(2014): 11552-11569.
Primarily the work of Johannes Hagemann, we use alternating projection algorithms to recover the phase and amplitude of an object using near-field on-axis diffraction data.
-
"Local Linear Convergence of Approximate Projections onto Regularized Sets",
Nonlinear Analysis, 75(2012):1531--1546. DOI: 10.1016/j.na.2011.08.027. (preprint: arXiv:1108.2243v3).
In this solo publication I examine rates of convergence of a simple projection algorithm for nonconvex feasibility when only
approximate projections are computed. Extrapolation is also considered in this framework. The theory is applied to the
phase retrieval problem (see below). As far as I know, this is the
first time that local linear convergence of inexact alternating projections for consistent phase retrieval with nonnegativity
constraints has been proved. The theory is also applied to regularized phase retrieval where the diffraction images
have been corrupted by Poisson noise. The paper provides practitioners with a practical stopping rule with
guarantees of the distance of the final iterate to the model solution.
- "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).
top
Sparsity/Rank Optimization and Computational Chemistry
The remainder of the applications I have been interested in concern optimization
with sparsity or rank constraints and computational quantum chemistry (not necessarily related
problems). The computational chemistry 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
initially relatively small, it grows superlinearly with the number of
unknowns. The work in spasity and rank optimization concerns problems with many unknowns
but an underlying sparse or low-dimensional structure that is not known. The popular
compressed sensing problem seeks to solve a nonconvex problem with sparsity constraints
via convex relaxations, or nonconvex relaxations that perform similarly to convex
relaxations. Our approach is rather to solve the nonconvex sparse affine feasibility
problem directly via simple methods. Under conditions that are not unlike
the well-known restricted isometry problem, we are able to prove global convergence of
simple algorithms (alternating projections) to the unique global solution. This
work continues to be an great source of inspiration for nonconvex convergence theory.
-
"Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility",
R. Hesse, D. R. Luke and P. Neumann.
IEEE Transactions on Signal Processing , 62(18):4868--4881, 2014. (preprint: arXiv:1108.2243v3).
The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved nonconvex relaxations. In this work we consider elementary methods based on projections for solving a sparse feasibility problem without employing convex heuristics. It has been shown recently that, locally, the fundamental method of alternating projections must converge linearly to a solution to the sparse feasibility problem with an affine constraint. In this paper we apply different analytical tools that allow us to show
global linear convergence of alternating projections under familiar constraint qualifications. These analytical tools can also be applied to other algorithms. This is demonstrated with the prominent Douglas-Rachford algorithm where we establish
local linear convergence of this method applied to the sparse affine feasibility problem.
-
"Prox-regularity of rank constraint sets and implications for algorithms '',
D. R. Luke, J. Math. Imaging and Vision, 47(3):231--328 (2013). DOI: 10.1007/s10851-012-0406-3
We present an analysis of sets of matrices with rank less than or equal to a specified number s.
We provide a simple formula for the normal cone to such sets, and use this to show that these sets
are prox-regular at all points with rank exactly equal
to s. The normal cone formula appears to be new.
This allows for easy application of prior results guaranteeing local linear convergence of
the fundamental alternating projection algorithm between sets, one of which is a rank constraint set.
We apply this to show local linear convergence of another fundamental algorithm,
approximate steepest descent.
Our results apply not only to linear systems with rank constraints, as has been treated extensively in the
literature, but also nonconvex systems with rank constraints.
-
"Restricted normal cones and sparsity optimization with affine contraints",
H. H. Bauschke, D. R. Luke, H. M. Phan and X. Wang, J. Foundations of Computational Mathematics
14(1):63--83 (2014). DOI 10.1007/s10208-013-9161-0.
The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved non convex relaxations. In this paper we consider the elementary method of alternating projections (MAP) for solving the sparsity optimization problem without employing convex heuristics. In a parallel paper we recently introduced the restricted normal cone which generalizes the classical Mordukhovich normal cone and reconciles some fundamental gaps in the theory of sufficient conditions for local linear convergence of the MAP algorithm. We use the restricted normal cone together with the notion of superregularity, which is naturally satisfied for the affine sparse optimization problem, to obtain local linear convergence results with estimates for the radius of convergence of the MAP algorithm applied to sparsity optimization with an affine constraint.
-
"Entropic Regularization of the l_0 Function '', J. M. Borwein and D. R. Luke, in
Fixed-Point Algorithms for Inverse Problems in Science and Engineering,
H. Bauschke, R. Burachik, P. Combettes, V. Elser, R. Luke, H. Wolkowicz, ed. Springer Verlag (2011).
Many problems of interest where more than one solution is possible seek,
among these, the one that is sparsest. The objective that most directly accounts for
sparsity, the counting function, is usually avoided since this leads to a combinatorial optimization problem. The counting function is often viewed as the limit of the p-metrics.
Naturally, there have been some attempts to use this as an objective for
p small, though this is a nonconvex function for p less than 1. We propose instead a scaled and
shifted Fermi-Dirac entropy with two parameters, one controlling the smoothness
of the approximation and the other the steepness of the metric. Our proposed metric
is a convex relaxation for which a strong duality theory holds, yielding dual methods
for metrics approaching the desired function. Without smoothing, we propose
a dynamically reweighted subdifferential descent method with "exact" line search
that is finitely terminating for constraints that are well-separated. This algorithm is
shown to recapture in a special case certain well-known "greedy" algorithms. Con-
sequently we are able to provide an explicit algorithm whose fixed point, under the
appropriate assumptions, is the sparsest possible solution. The variational perspec-
tive yields general strategies to make the algorithm more robust.
- "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, Tilo Arens of Karlsruhe Institute of Technilogy and Armin Lechleiter of University of Bremen.
I have also published two independent works in this area.
-
`` 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.
Software
- SAMSARA a
reverse communication optimization toolbox for MATLAB. A Fortran90
version is on the way.
- SCAT
The Symbolic Convex Analysis Toolkit (SCAT) is a Maple package for symbolic computation of various objects from convex anlysis including Fenchel conjugates and subdifferentials. We are actively working on further development of the package but the bulk of the source code is credited to Borwein and Hamilton. The archive also contains supplementary material for paper Symbolic computation with monotone operators.
- 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)
-
ProxToolbox set of projection algorithm tools
- Word Counter thanks to JavaScript Kit
top
Industry Cooperation
- "Optimal switching of hybrid motors"
for IAV GmbH , October 2012-February 2013.
- ``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)