CIF: Small: Graph Signal Sampling: Theory and Applications

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

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.