CIF: Small: Combinatorial Inverse Problems in Distance Geometry

CIF：小：距离几何中的组合反问题

• 批准号: 1817577
• 负责人: Ivan Dokmanic
• 金额: $ 15.71万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2020-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1817577&HistoricalAwards=false
• 关键词: CIF; Small; Combinatorial; Inverse; Problems

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.

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

项目成果

3D Unknown View Tomography Via Rotation Invariants

• DOI: 10.1109/icassp40776.2020.9053170
• 发表时间: 2020-03
• 期刊: ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 作者: Mona Zehni;Shuai Huang;Ivan Dokmani'c;Zhizhen Zhao

Reconstructing Point Sets From Distance Distributions

从距离分布重建点集

• DOI: 10.1109/tsp.2021.3063458
• 发表时间: 2021
• 期刊: IEEE Transactions on Signal Processing
• 影响因子: 5.4
• 作者: Huang, Shuai;Dokmanic, Ivan
• 通讯作者: Dokmanic, Ivan

Geometric Invariants for Sparse Unknown View Tomography

• DOI: 10.1109/icassp.2019.8682401
• 发表时间: 2018-11
• 期刊: ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 作者: Mona Zehni;Shuai Huang;Ivan Dokmanić;Zhizhen Zhao

Permutations Unlabeled Beyond Sampling Unknown

• DOI: 10.1109/lsp.2019.2908505
• 发表时间: 2018-12
• 期刊: IEEE Signal Processing Letters
• 影响因子: 3.9
• 作者: Ivan Dokmanić

Solving Complex Quadratic Equations with Full-rank Random Gaussian Matrices

• DOI: 10.1109/icassp.2019.8683280
• 发表时间: 2019-05
• 期刊: ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
• 作者: Shuai Huang;Sidharth Gupta;Ivan Dokmanić