A Fast Newton's Algorithm for Entropy Maximization in Phase Determination
A long-standing problem in X-ray crystallography, known as the phase problem, is to determine the phases for a large set of complex variables, called the structure factors of the crystal, given their magnitudes obtained from X-ray diffraction experiments. We introduce a statistical phase estimation approach to the problem. This approach requires solving a special class of entropy maximization problems repeatedly to obtain the joint probability distribution of the structure factors. The entropy maximization problem is a semi-infinite convex program, which can be solved in a finite dual space by using a standard Newton's method. The Newton's method converges quadratically, but is costly in general, requiring O(n log n) floating point operations in every iteration, where n is the number of variables. We present a fast Newton's algorithm for solving the entropy maximization problem. The algorithm requires only O(n log n) floating point operations for each of its iterates, yet has the same convergence rate as the standard Newton. We describe the algorithm and discuss related computational issues. Numerical results on simple test cases will also be presented to demonstrate the behavior of the algorithm.
Citable link to this pagehttp://hdl.handle.net/1911/101919
MetadataShow full item record
- CAAM Technical Reports