CIF: Small: Combinatorial Inverse Problems in Distance Geometry

点击翻译按钮获取中文摘要

From navigating the seas to reconstructing the shape of proteins, reasoning from distances is at the heart of civilization. In many applications one has a list of distances but no labeling information to assign them to objects. For example, when navigating buildings by multipath, echoes coming from different walls all look the same; when solving the geometry of nanostructured materials by powder diffraction, distances between different pairs of atoms are all summarized in a single pair distribution function. The goal of this project is to advance algorithms and theory for the underlying mathematical problem "the unlabeled distance geometry problem" with potential to impact indoor mapping and positioning, nanoscience, and genomics.The unlabeled distance geometry problem lies at the intersection of signal processing, computer science, acoustics, and experimental nanoscience. In this project the investigator proposes to develop algorithms for the unlabeled distance geometry problem with provable guarantees, as well as practical recipes for using those algorithms in major applications. The team will place particular emphasis on the connections with the state-of-the-art developments in signal processing, especially phase retrieval, matrix completion, and semidefinite relaxations for non-convex problems, by developing computationally efficient relaxations that work with high probability over typical instances.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.