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

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

• 批准号: RGPIN-2017-06266
• 负责人: Rabbat, Michael
• 金额: $ 3.42万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=689574
• 关键词: 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)我们将开发用于在高维非线性/非高斯状态空间模型中进行跟踪的方法，并利用图结构对图信号进行采样/滤波以提高计算效率。