CIF: Medium: Signal representation, sampling and recovery on graphs

在物理和工程应用以及社会、生物分子、商业、安全和许多其他领域中收集的数据集正变得越来越大和复杂。在许多情况下，这些数据是手动分析的，或者使用只提取表面信息的方法，可能导致主观和不可重现的结论。因此，迫切需要制定方法，正式分析复杂的数据。图提供了一种自然的形式主义来捕获在许多应用程序中控制数据结构的复杂交互。然而，一直缺乏一个严格的框架，信号和数据处理的图形。该建议旨在发展信号表示，采样和恢复的图形的基础。信号和数据处理一直是主要研究人员的重点？工作多年。在这个项目中，该团队将开发一个数学上严格的框架，用于图形信号处理，为分析具有复杂，非规则结构的高维数据提供了一个新的范例。通过将基本的信号处理概念，如滤波、傅立叶和小波分析扩展到一般图上的数据，该框架将为许多数据分析问题提供原则性的解决方案，如数据压缩、恢复、定位、检测等。具体来说，该团队将1）为图上的信号开发高效简洁的表示，2）设计有效的策略，利用图结构对图上的信号进行采样，3）开发接近最佳和计算效率高的估计器，用于从样本中恢复图信号。

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.