权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Stable and Robust Graph Embedding, and Related Problems

稳定鲁棒的图嵌入以及相关问题

基本信息

批准号：
1916071
负责人：
Ery Arias-Castro
金额：
$ 14万
依托单位：
University of California-San Diego
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-08-15 至 2022-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1916071&HistoricalAwards=false
关键词：
Stable Robust Graph Embedding Related

项目摘要

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.

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