CIF: Small: Graph Signal Sampling: Theory and Applications

现代社会越来越依赖于大规模、分布式、互联和复杂的系统，如互联网、智能电网、智能建筑或高速公路。此外，现在产生的许多信息也以复杂的方式相互连接（例如，WEB）。 虽然可以通过记录相关数据来监测这些系统和数据集，但这些数据的数量使得难以及时解决关键任务，例如异常检测。这些数据集通常表现出自然的图形结构，其中图形节点表示测量或信息（例如，传感器的温度或来自网页的数据），以及表示节点之间的关系的图形边缘（例如，传感器之间的距离或网页之间的链接）。该项目开发了用于对超大规模图形数据集进行采样的新方法，目标是仅测量精心选择的一小部分节点，同时保留分析整个系统的能力。采样理论是信号处理理论和应用的一个重要组成部分，但直到最近才被考虑用于图形信号。虽然最近的进展已经取得的假设下，图是完全已知的，这些技术是昂贵的实际数据集的利益。该项目解决了只有部分图形信息可用时采样的挑战性问题的基本问题（例如，基于连接节点的较小子集的决策）。例如，给定局部图连接性信息和关于感兴趣的图信号的假设，诸如它们的频率局部化，目标是识别要局部采样的顶点的最佳集合，以便获得对应的全局图信号的可靠估计。

Modern society is increasingly reliant on large scale, distributed, interconnected, and complex systems, such as the Internet, smart grids, intelligent buildings or highways. Furthermore, much of the information now being generated is also interconnected in complex ways (e.g., the Web). While these systems and datasets can be monitored by recording relevant data, the volumes of such data make it difficult to address critical tasks, such as anomaly detection, in a timely manner. These datasets often exhibit a natural graph structure, with graph nodes representing measurements or information (e.g., the temperature of a sensor or data from a web page), and graph edges representing the relationships between nodes (e.g., distance between sensors or links between webpages). This project develops novel methods for sampling of very large scale graph datasets, with the goal of making it possible to measure only a small fraction of carefully selected nodes, while preserving the ability to analyze the whole system. Sampling theory is a major element of signal processing theory and applications, but has only recently been considered for graph signals. While recent progress has been made under the assumption that the graph is fully known, these techniques are prohibitively expensive for practical datasets of interest. This project addresses fundamental questions for the challenging problem of sampling when only partial graph information is available (e.g., decisions based on smaller subsets of connected nodes). For example, given local graph connectivity information and assumptions about the graph signals of interest, such as their frequency localization, the goal is to identify the best set of vertices to sample locally in order to obtain a reliable estimate of the corresponding global graph signals.