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

Duke University, Durham NC

Investigators

Abstract

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.