Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Doing Business As Name:Duke University
  • Xiuyuan Cheng
  • (203) 843-6364
Award Date:07/11/2020
Estimated Total Award Amount: $ 279,169
Funds Obligated to Date: $ 139,912
  • FY 2020=$139,912
Start Date:07/15/2020
End Date:06/30/2024
Transaction Type:Grant
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.049
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:NSF-BSF: Group Invariant Graph Laplacians: Theory and Computations
Federal Award ID Number:2007040
DUNS ID:044387793
Parent DUNS ID:044387793
Program Officer:
  • Eun Heui Kim
  • (703) 292-2091

Awardee Location

Street:2200 W. Main St, Suite 710
Awardee Cong. District:01

Primary Place of Performance

Organization Name:Duke University
Street:2200 W. Main St.Suite 710
Cong. District:01

Abstract at Time of Award

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.

For specific questions or comments about this information including the NSF Project Outcomes Report, contact us.