CIF: Small: Combinatorial Inverse Problems in Distance Geometry

从航海到重建蛋白质的形状，远距离推理是文明的核心。在许多应用中，人们有一个距离列表，但没有将它们分配给对象的标签信息。例如，当通过多路径在建筑物中导航时，来自不同墙壁的回声看起来都相同；当通过粉末衍射求解纳米结构材料的几何形状时，不同原子对之间的距离都总结为单对分布函数。该项目的目标是推进潜在数学问题“无标记距离几何问题”的算法和理论，有可能影响室内测绘和定位、纳米科学和基因组学。无标记距离几何问题位于信号处理、计算机科学、声学和实验纳米科学的交叉点。在这个项目中，研究人员建议开发具有可证明保证的未标记距离几何问题的算法，以及在主要应用中使用这些算法的实用方法。该团队将特别强调与信号处理领域最先进的发展的联系，特别是相位检索、矩阵完成和非凸问题的半定松弛，通过开发在典型实例上具有高概率的计算有效的松弛。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.