A Fast Newton Method for Solving the Entropy Maximization Problems in X-ray Crystallography Phase Estimation

Zhijun Wu
Math, Bioinformatics, & Computational Biology, Iowa State University

(February 2, 2005 3:30 PM - 4:30 PM)

A Fast Newton Method for Solving the Entropy Maximization Problems in X-ray Crystallography Phase Estimation

Abstract

A long-standing issue in statistical approaches to X-ray crystallography phase estimation is to solve a set of entropy maximization problems efficiently during the estimation. Each of these entropy maximization problems is a semi-infinite convex program and can be solved in a finite dual space by using a standard Newton method. However, the Newton method is too expensive since it requires O (n3) floating-point operations per iteration, where n corresponds to the number of the phases to be estimated. Other less expensive methods have been used but they cannot guarantee fast convergence. In this talk, I will describe a fast Newton method my colleagues and I have recently developed for solving the entropy maximization problems. The method uses the Sherman-Morrison-Woodbury Formula and the Fast Fourier Transform to compute the Newton step and requires only O (n log n) floating-point operations per iteration. On the other hand, it can converge in the same rate as the standard Newton. I will show how the method works and present some numerical results.