Datasets that are collected in physical and engineering applications, as well as social, biomolecular, commercial, security, and many other domains, are becoming larger and more complex. In many cases, such data is analyzed manually or using methods that extract only superficial information and can lead to subjective and non-reproducible conclusions. There is thus an urgent need for the development of methodologies that formalize analysis of complex data. Graphs provide a natural formalism to capture complex interactions that govern the structure of the data in many applications. However, a rigorous framework for signal and data processing on graphs has been lacking. This proposal aims to develop the fundamentals of signal representation, sampling and recovery on graphs.
Signal and data processing has been the focus of the principal investigators? work for many years. In this project, the team will develop a mathematically rigorous framework for signal processing on graphs that offers a new paradigm for the analysis of high-dimensional data with complex, non-regular structure. By extending fundamental signal processing concepts such as filtering, Fourier and wavelet analysis to data residing on general graphs, the framework will offer principled solutions to a number of data analysis problems, such as data compression, recovery, localization, detection, and others. Specifically, the team will 1) develop efficient succinct representations for signals on graphs, 2) design efficient strategies that leverage the graph structure for sampling signals on graphs, and 3) develop near-optimal and computationally efficient estimators for recovering graph signals from samples.
