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

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

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.