Shuai Huang, University of Illinois, Urbana-Champaign

Abstract

Previous approaches to solve the unassigned distance geometry problem (uDGP) were often based on backtracking and build-up algorithms. Being a combinatorial optimization problem in nature, the uDGP can be quadratically formulated as 0-1 integer programming with the points locations represented by a 0-1 vector x. The unassigned distance distribution can then be computed from the autocorrelation of x. We further relax the 0-1 integer programming into a constrained nonconvex optimization problem, and propose to solve it using projected gradient descent with spectral initialization. The unknown view tomography problem arising from applications such as cryo-electron microscopy can be connected to uDGP under the 3D point-source model and Gaussian-source model. It can also be formulated as a constrained nonconvex problem and solved using the proposed approach.

Video