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

分析随时间演变的数据的有效方法对于解决当今一些最相关的社会问题至关重要。这些方法有助于识别病毒的来源和跟踪病毒的传播，检测和监测危险污染物，研究神经和其他生物医学相互作用，并设计数据、能源或货物的运输网络。在许多应用中，例如上面提到的应用，数据通常由图上的时间演化函数来建模。在这个项目中，一群不同的博士后、博士后研究员和高级研究人员将开发新的数学技术和算法，为这些函数设计具有成本效益的时空采样、处理和重建策略。这些算法将分析和管理在现实条件下采样并受到噪声破坏的各种时间演变过程。该项目将研究用于数据收集的传感器的最佳空间位置，传感器数量与其激活频率之间的时空权衡，以及识别驱动数据的进化过程的各种类型参数的方法。这项研究有望对传感网络的设计和实现以及利用图上的信号的其他应用产生重大影响。该项目的更广泛影响将包括发展和指导来自几个机构的不同的初级研究人员工作组，并参与各种外联活动。该项目的重点是开发一个数学框架、工具和算法，用于在图形上采样和重建随时间演变的函数。研究人员将解决几个逆问题，如从图上的时空样本中恢复动力系统的初始状态、演化算子和/或强迫源项。为此，他们将扩展图Paley-Wiener空间中函数的动态采样框架，建立并解决几个寻找稳健且经济有效的采样模式的优化问题，并创建并研究实现上述理论问题解的计算高效算法。研究人员将使用和结合采样理论、动力系统、傅立叶分析、泛函分析、数值线性代数和离散优化的结果，为理论和应用研究创造和维持一个肥沃的环境。该项目将加强现有的方法，并提供新的数学工具和计算方案，为信号处理和图形上的系统识别中的基本逆问题提供实用的解决方案。这项研究的一些结果也将有助于理解最优化、框架和图论中的几个具有挑战性的基本问题。例如，研究人员将创建快速算法来逼近图上某些NP-Hard离散优化问题的解，并为其性能提供理论保证。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.