Stable and Robust Graph Embedding, and Related Problems

该项目解决了与推断空间中一个或几个物体的位置有关的重要问题。这些问题与广泛的重要应用相关，例如机器人技术（例如，自动驾驶汽车，自动驾驶汽车），地理空间信息系统或GIS（例如，传感器网络定位）等等。通常情况下，关于这些主题的文献绝大多数是特定于应用程序的。贡献理论和更有原则的方法可以帮助建立一个基础，使研究界能够以一种通用的、更严格的（数学）语言和对问题本身及其分支的更深入的理解向前发展。一个特别的重点将是理解最先进的方法在处理输入错误（在应用程序中无处不在）方面的健壮性，以及对于某些任务，开发比现有方法更健壮的新方法。图嵌入问题是许多研究领域交叉点上的一个基本问题，包括统计学中的多元分析和可视化、机器学习、度量几何、机器人等。关于该主题的文献大量，但缺乏关键的理论要素，特别是关于噪声的稳定性和对异常值的鲁棒性。虽然一些鲁棒方法是可用的，但利用现有的鲁棒矩阵补全问题的研究仍有改进的潜力。在更基本的层面上，有一个问题是，哪些图是唯一可嵌入的。这在刚性理论文献中得到了研究。这个问题在很大程度上得到了解决，并简化为存在一个特定的矩阵，称为应力矩阵，它包括由图的嵌入（当存在时）在其零空间中定义的坐标向量，并且具有该性质的最大秩。然而，这个条件是定性的，而不是定量的，因为排名在数值上是不稳定的。这就要求发展一种定量的刚性理论，以及有性能保证的新方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The project addresses important problems having to do with inferring the position of one or several objects in space. Such problems are relevant to a wide range of important applications, such as in robotics (e.g., autonomous vehicles, self-driving cars), geospatial information systems or GIS (e.g., sensor network localization), and more. As is often the case, the literature on these topics is overwhelmingly application-specific. Contributing theory and more principled methodology can help build a foundation that enables the research community to move forward with a common, more rigorous (mathematical) language and a deeper understanding of the problem itself and its ramifications. A particular focus will be on understanding how robust state-of-the-art methods are to gross errors in the input (ubiquitous in applications) and, for some tasks, on developing new methods that are more robust than existing ones.The problem of graph embedding is a fundamental problem at the crossroads of a number of research areas including multivariate analysis and visualization in statistics, machine learning, metric geometry, robotics, and more. The literature on the topic is vast, and yet lacks crucial elements of theory, in particular in regards to the stability to noise and robustness to outliers. Although some robust methods are available, there is potential for improvement by leveraging existing research on the problem of robust matrix completion. At an even more fundamental level, there is the problem of characterizing which graphs are uniquely embeddable. This is studied in the rigidity theory literature. The problem is largely solved and reduces to the existence of a certain matrix, called stress matrix, that includes the coordinate vectors defined by an embedding of the graph (when one exists) in its null space, and has maximum rank with that property. However, this condition is qualitative, rather than quantitative, in that the rank is numerically unstable. This calls for the development of a quantitative theory of rigidity, as well as new methodology with performance guarantees.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.