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

数据分析是科学和工程领域的中心任务之一。在许多数据分析应用中，处理后的数据具有自然的底层结构。在数学中，一族重要的结构被称为群结构。直观地说，组结构意味着不仅观测点是有效的数据点，而且是通过对观测点进行某种操作而产生的所有数据点。将这种结构融入到数据分析算法中，有可能显著提高其速度和精度，这是当今大数据分析中的根本挑战。特别是，所开发的方法具有取代数据增强等传统方法的潜力。在数据分析中利用群体结构在很大程度上被忽视了，特别是在基于图的方法的背景下，由于其对噪声和离群值的稳健性，这些方法是数据分析中的关键工具。这个NSF-BSF联合项目将研究基于群不变图的方法，该方法将数据的群结构解析地嵌入到处理算法中。该项目的理论价值包括对群不变方法的严格分析，从而将数学、统计学和计算联系在一起。该项目的影响在于其在高维数据分析中的广泛应用。在项目期间开发的软件将被公开共享。该项目的基本框架及其应用程序将向研究生和本科生开放，并适合作为学生项目，供不同STEM背景的学生使用。研究结果还将为开发数学、计算和数据科学交叉学科的课程提供新的教学材料。最后，NSF和BSF的这个联合项目为加强美国和以色列研究小组之间的合作提供了一个独特的机会，特别是在来自美国和以色列的年轻数学家职业生涯的早期阶段建立联系。联合研究项目的目标是开发一系列G不变图拉普拉斯方法，即图拉普拉斯方法，该方法被构造为在不增加任何数据的情况下分析地并入群不变。利用表象理论、调和分析、数值分析和统计学，本研究将建立这些方法的数学框架，对它们的性能进行理论分析，开发相关的实用计算算法，并在图像数据分析的几个应用中演示所得到的方法。研究议程包括四个综合活动：(1)构造一般紧群的G-不变图拉普拉斯算子；(2)证明G-不变图拉普拉斯算子对流形拉普拉斯算子的收敛；(3)利用G-不变图拉普拉斯算子推导出扩展和处理函数的有效计算工具；(4)应用G-不变图拉普拉斯算子进行数据去噪。这些目标的实现建立在计算调和分析领域十多年来发展起来的图拉普拉斯方法的分析和计算技术的基础上，并显著增强了这些技术。该项目的贡献在于为高维流形数据学习开发了一种新的范式，并填补了目前对基于图的方法的理解中的知识空白。具体地说，新的范式将显著扩展现有的高维数据分析工具集，无论是在数学理论上还是在实际算法中，都可能适用于包括度量学习、形状匹配和成像处理在内的一系列应用程序。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.