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.