The phase retrieval problems that arise in X-ray crystallography are hard. The best known algorithms have time complexity that grows exponentially with problem size. Given the importance of the application, over the years heuristic algorithms have evolved to the point where solutions of structures up to thousands of atoms are within reach. Applied mathematicians have given these algorithms the cold shoulder because they do not guarantee solutions. On the other hand, they have not come up with algorithms that do. This talk aims to rehabilitate, for an audience of mathematicians, the heuristic algorithms used in crystallography. I will discuss a modern variant that has a 100% empirical success rate and is best described as a dynamical system that, thanks to ergodicity, manages to perform an exhaustive search. As in statistical mechanics, ergodicity is enabled by chaotic behavior and represents a strong departure from more disciplined modes of search (e.g. on trees). My take-away message will be that rather run from these algorithms mathematicians should try to understand them.

This presentation is part of Minisymposium “MS21 - Recent mathematical advances in phase retrieval and computational imaging (2 parts)”
organized by: Mahdi Soltanolkotabi (University of Southern California) , Tamir Bendory (Princeton University) .

Authors:

Veit Elser (Department of Physics, Cornell University)

Keywords:

image reconstruction, nonlinear optimization, phase retrieval