Signal Processing Over Networks: Graph-Based Methods for Data Analysis

网络信号处理：基于图的数据分析方法

• 批准号: RGPIN-2017-06266
• 负责人: Rabbat, Michael
• 金额: $ 3.42万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=712146
• 关键词: Signal; Processing; Over; Networks; Graph

Using data to benefit humanity is a grand challenge for today's engineers and data scientists (e.g., via environmental monitoring, improving public health, and sustainability). This research program aims to develop novel signal processing theory and methods to address challenges associated with processing and learning from unstructured or irregularly-sampled data. Existing signal processing techniques are well-suited for data such as time series and images which have a regular, well-ordered domain. Many contemporary applications produce data that is massive, complex, and unstructured. Graphs provide a principled formalism to capture complex relationships among variables and entities. In some applications the graph may capture a physical structure underlying the signal (e.g., traffic intensities on links of a road network, demand signals at nodes of the smart grid, or a measure of people's opinions in a social network). Graphs may also serve as a useful means to encode which data sampling locations we expect to produce similar values when signals are sampled irregularly in space and/or time (e.g., EEG and/or MRI signals sampled on the surface of the brain, or a network of sensors spread irregularly over a region). In other applications, where the graph is not directly apparent, it may encode logical relationships among entities (e.g., correlative, causal, or otherwise influential relationships). In this case it is often of interest to infer a graph from the observations in order to better understand the structure, organization, and function of a complex system. This research program will make contributions to the burgeoning field of graph signal processing. The specific objectives of the proposed program are organized along three thrusts. (1) We will develop novel theory and methods for inferring graphs from signals under models where the signals are assumed to be smooth over the graph. In cases where signals cannot be observed at every vertex, we will infer structural or statistical properties of the graph that may still be useful for other applications like sampling. (2) We will develop novel theory and methods for approximating and compressing graph signals. While the theories of sampling and filtering graph signals are becoming more mature, little is known about what conditions on the signal-generating process and the graph structure are necessary for the resulting signal to be smooth or otherwise parsimoniously representable. The theoretical results will facilitate quantifying the tradeoff between the number of coefficients used to represent (i.e., approximate or compress) a graph signal and the resulting error incurred, given a family of graphs and graph signals. (3) We will develop methods for tracking in high-dimensional non-linear/non-Gaussian state-space models and sampling/filtering graph signals that exploit graph structure to improve computational efficiency.

使用数据造福人类是当今工程师和数据科学家面临的巨大挑战(例如，通过环境监测、改善公共健康和可持续发展)。这项研究计划旨在开发新的信号处理理论和方法，以应对与处理和学习非结构化或不规则样本数据相关的挑战。现有的信号处理技术非常适合于具有规则、有序的域的数据，例如时间序列和图像。许多当代应用程序产生的数据是海量的、复杂的和非结构化的。图提供了一种原则性的形式主义来捕捉变量和实体之间的复杂关系。在一些应用中，该图可以捕捉信号背后的物理结构(例如，道路网络的链路上的交通强度、智能电网的节点处的需求信号、或社交网络中的人们意见的测量)。当在空间和/或时间上不规则地对信号进行采样时(例如，在大脑表面上采样的EEG和/或MRI信号，或者在一个区域上不规则分布的传感器网络)，图也可以用作编码我们期望产生相似值的数据采样位置的有用手段。在图不直接明显的其他应用中，它可以编码实体之间的逻辑关系(例如，相关的、因果的或其他有影响的关系)。在这种情况下，为了更好地理解复杂系统的结构、组织和功能，从观测中推断出图表通常是有意义的。 该研究项目将为图形信号处理这一新兴领域做出贡献。拟议方案的具体目标按照三条主线组织起来。(1)在假设信号在图上光滑的模型下，我们将发展从信号推断图的新理论和新方法。在不能在每个顶点都观察到信号的情况下，我们将推断图形的结构或统计特性，这些特性可能对其他应用(如采样)仍然有用。(2)提出了图形信号逼近和压缩的新理论和新方法。虽然采样和滤波图信号的理论正在变得越来越成熟，但对于信号产生过程和图结构的哪些条件才能使结果信号平滑或以其他方式简约地表示，人们知之甚少。理论结果将有助于在给定一族图和图信号的情况下，量化用于表示(即，近似或压缩)图信号的系数的数目与所产生的误差之间的权衡。(3)我们将开发高维非线性/非高斯状态空间模型中的跟踪方法，以及利用图结构来提高计算效率的图信号采样/滤波方法。