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.

从航行到海洋到重建蛋白质的形状，距离的推理是文明的核心。在许多应用程序中，一个人都有距离列表，但没有标签信息将其分配给对象。例如，当通过Multipath浏览建筑物时，来自不同墙壁的回声看起来都一样。当通过粉末衍射求解纳米结构材料的几何形状时，在单对分布函数中总结了不同原子对之间的距离。该项目的目的是推进基础数学问题“未标记的距离几何问题”的算法和理论，并可能影响室内映射和定位，纳米科学和基因组学。计算机科学，声学和实验纳米科学。在该项目中，研究人员建议开发具有可证明的保证的未标记距离几何问题的算法，以及用于在主要应用中使用这些算法的实用食谱。该团队将特别强调与信号处理的最先进发展的联系，尤其是相位检索，矩阵完成，以及通过开发有效的计算有效放松，以使其具有很高的可能性，以使其具有高概率典型实例。该奖项反映了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ć