NSF-BSF: Group Invariant Graph Laplacians: Theory and Computations

NSF-BSF：群不变图拉普拉斯算子：理论与计算

• 批准号: 2007040
• 负责人: Xiuyuan Cheng
• 金额: $ 27.92万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-15 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007040&HistoricalAwards=false
• 关键词: NSF; BSF; Group; Invariant; Graph

Data analysis is one of the central tasks in science and engineering. In many data analysis applications, the processed data enjoy a natural underlying structure. An important family of structures is known in mathematics as group structures. Intuitively, a group structure means that not only the observed points are valid data points, but also all data points generated by applying some operation to the observed points. Incorporating this structure into data analysis algorithms has the potential to significantly improve their speed and accuracy, which are fundamental challenges in today’s Big Data analysis. In particular, the developed methods have the potential to replace traditional approaches like data augmentation. Exploiting group structure in data analysis has been largely overlooked, especially in the context of graph-based methods, which are pivotal tools in data analysis due to their robustness to noise and outliers. This NSF-BSF joint project will study group-invariant graph-based methods, which embed the group structure of the data into the processing algorithms analytically. The theoretical merit of the project includes a rigorous analysis of group invariant methods, thus bridging mathematics, statistics, and computations. The impact of the project lies in its applicability to a wide range of applications in high dimensional data analysis. Software developed during the project will be shared publicly. The basic framework of the project and its applications will be made accessible to graduate and undergraduate students, and are suitable as student projects for students from various STEM backgrounds. The results will also provide fresh pedagogical materials for developing courses at the intersection of mathematics, computation and data science. Finally, this joint NSF-BSF project provides a unique opportunity for enhancing collaboration between U.S. and the Israeli research groups, and in particular, establishing connections between young mathematicians from the US and Israel at an early stage of their careers.The goal of the joint research project is to develop a family of G-invariant graph Laplacian methods, namely, graph Laplacians that are constructed to incorporate group invariance analytically without any data augmentation. Using representation theory, harmonic analysis, numerical analysis, and statistics, the research will develop the mathematical framework for such methods, pursue the theoretical analysis of their performance, develop their associated practical computational algorithms, and demonstrate the resulting methods on several applications in image data analysis. The research agenda consists of four integrated activities: (1) Construct the G-invariant graph Laplacian for general compact groups; (2) Prove the convergence of G-invariant graph Laplacians to the manifold Laplace operator; (3) Derive efficient computational tools for expanding and processing functions using G-invariant graph Laplacians; (4) Apply G-invariant graph Laplacians for data de-noising. The implementation of these goals builds upon and significantly enhances the analytical and computational techniques of graph Laplacian methods that have been developed in the field of computational harmonic analysis for more than a decade. The contribution of the project lies in developing a new paradigm for high-dimensional manifold data learning, and fills the knowledge gap in the current understanding of graph-based methods. Specifically, the new paradigm will significantly extend the existing set of tools for high-dimensional data analysis, both in mathematical theories and in practical algorithms, and is potentially applicable in a range of applications including metric learning, shape matching, and imaging processing.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-BSF联合项目将研究基于组不变图的方法，该方法将数据的组结构嵌入到分析处理算法中。该项目的理论价值包括对组不变方法的严格分析，从而桥接数学，统计学和计算。该项目的影响在于其适用于高维数据分析的广泛应用。项目期间开发的软件将公开共享。该项目的基本框架及其应用程序将提供给研究生和本科生，并适合来自不同STEM背景的学生作为学生项目。研究结果还将为数学、计算和数据科学交叉领域的课程开发提供新的教学材料。最后，这个联合项目为加强美国和以色列研究小组之间的合作提供了一个独特的机会，特别是在美国和以色列的年轻数学家之间建立联系，在他们职业生涯的早期阶段。联合研究项目的目标是开发一个G不变图拉普拉斯方法家族，即，图拉普拉斯算子，被构造为在没有任何数据增强的情况下分析地结合群不变性。使用表示理论，谐波分析，数值分析和统计，研究将开发这些方法的数学框架，追求其性能的理论分析，开发其相关的实际计算算法，并在图像数据分析的几个应用程序上演示所产生的方法。研究议程由四个综合活动组成：（1）构造一般紧群的G-不变图拉普拉斯算子;（2）证明G-不变图拉普拉斯算子收敛于流形拉普拉斯算子;（3）推导出使用G-不变图拉普拉斯算子展开和处理函数的有效计算工具;（4）将G-不变图拉普拉斯算子应用于数据去噪。这些目标的实现建立在图拉普拉斯方法的分析和计算技术的基础上，并大大增强了该方法在计算谐波分析领域已经发展了十多年。该项目的贡献在于为高维流形数据学习开发了一种新的范式，并填补了目前对基于图的方法的理解中的知识空白。具体而言，新范式将在数学理论和实际算法方面显着扩展现有的高维数据分析工具集，并可能适用于一系列应用，包括度量学习，形状匹配，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响进行评估，被认为值得支持审查标准。

项目成果

Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

• DOI: 10.1016/j.acha.2022.06.003
• 发表时间: 2022-07-08
• 期刊: APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS
• 影响因子: 2.5
• 作者: Cheng, Xiuyuan;Wu, Nan
• 通讯作者: Wu, Nan

SpecNet2: Orthogonalization-free spectral embedding by neural networks

• DOI: 10.48550/arxiv.2206.06644
• 发表时间: 2022-06
• 作者: Ziyu Chen;Yingzhou Li;Xiuyuan Cheng

Convergence of graph Laplacian with kNN self-tuned kernels

图拉普拉斯算子与 kNN 自调整核的收敛

• DOI: 10.1093/imaiai/iaab019
• 发表时间: 2021
• 期刊: Information and Inference: A Journal of the IMA
• 作者: Cheng, Xiuyuan;Wu, Hau-Tieng
• 通讯作者: Wu, Hau-Tieng

Scaling positive random matrices: concentration and asymptotic convergence

缩放正随机矩阵：集中和渐近收敛

• DOI: 10.1214/22-ecp502
• 发表时间: 2022
• 期刊: Electronic Communications in Probability
• 影响因子: 0.5
• 作者: Landa, Boris