Stable and Robust Graph Embedding, and Related Problems

该项目解决了与推断一个或几个物体在太空中的位置有关的重要问题。这些问题与广泛的重要应用有关，例如在机器人(例如自动驾驶汽车、自动驾驶汽车)、地理空间信息系统或地理信息系统(例如传感器网络本地化)等方面。与通常的情况一样，关于这些主题的文献绝大多数是特定于应用程序的。贡献理论和更有原则的方法可以帮助建立一个基础，使研究界能够以一种共同的、更严格的(数学)语言向前迈进，并对问题本身及其分支有更深的理解。特别关注的是了解最先进的方法对输入中的严重错误(在应用程序中普遍存在)的健壮性，以及对于某些任务，开发比现有方法更健壮的新方法。图形嵌入问题是许多研究领域的十字路口的基本问题，包括统计学、机器学习、度量几何、机器人学等领域的多变量分析和可视化。关于这个主题的文献很多，但缺乏关键的理论元素，特别是关于噪声稳定性和对异常值的稳健性。虽然有一些稳健的方法可用，但通过利用关于稳健矩阵完成问题的现有研究，仍有改进的潜力。在更基本的层面上，还有一个问题是确定哪些图是唯一可嵌入的。这在刚性理论文献中进行了研究。这个问题在很大程度上得到了解决，并归结为存在一个称为应力矩阵的矩阵，该矩阵包括由图(如果存在)在其零空间中的嵌入所定义的坐标向量，并且具有该性质的最大秩。然而，这种情况是定性的，而不是定量的，因为排名在数字上是不稳定的。这需要发展一种刚性的量化理论，以及具有绩效保证的新方法。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.