Collaborative Research: Dynamical Sampling on Graphs: Mathematical Framework and Algorithms

Effective methods for analyzing data that evolve in time are crucial for solving some of the most relevant problems of society today. Such methods help identify the source and track the spread of a virus, detect and monitor dangerous pollutants, study neurological and other biomedical interactions, and design transportation networks for data, energy, or goods.

In many applications, such as the ones mentioned above, data are often modeled by time-evolving functions on graphs. In this project, a diverse group of Ph.D. students, postdoctoral fellows, and senior researchers will develop novel mathematical techniques and algorithms for designing cost-effective space-time sampling, processing, and reconstruction strategies for such functions.

The algorithms will analyze and manage various time-evolving processes that are sampled under realistic conditions and corrupted by noise. The project will study the optimal spatial placement of sensors for data collection, space-time trade-off between the number of sensors and the frequency of their activation, and ways of identifying various types of parameters of an evolution process driving the data.

The research is expected to have a significant impact on sensing network design and implementation as well as other applications where signals on graphs are utilized. Broader impacts of the project will include developing and mentoring a diverse working group of junior researchers from several institutions and engagement in various outreach activities.

The project focuses on the development of a mathematical framework, tools, and algorithms for sampling and reconstruction of time-evolving functions on graphs. The investigators will solve several inverse problems such as the recovery of an initial state, an evolution operator, and/or a forcing source term of a dynamical system from space-time samples on graphs.

For this purpose, they will extend the dynamical sampling framework for functions in graph Paley-Wiener spaces, set up and solve several optimization problems for finding robust and cost-effective sampling patterns, and create and study computationally efficient algorithms that implement the solutions of the above theoretical problems. The researchers will use and combine results from sampling theory, dynamical systems, Fourier analysis, functional analysis, numerical linear algebra, and discrete optimization to create and sustain a fertile environment for theoretical and applied research.

The project will enhance existing approaches and provide new mathematical tools and computational schemes that offer practical solutions to basic inverse problems in signal processing and system identification on graphs. Some of the results of this investigation will also contribute to the understanding of several challenging and fundamental issues in optimization, frames, and graph theory.

For example, the investigators will create fast algorithms for approximating solutions of certain NP-hard discrete optimization problems on graphs and provide theoretical guarantees for their performance.

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.