Collaborative Research: CIF: Small: Hypergraph Signal Processing and Networks via t-Product Decompositions

该合作研究项目旨在开发一种基于张量表示的新超图信号处理框架，以利用来自复杂关系的数据中的多路交互。简单图只能对数据之间的两两关系进行建模，这阻碍了它们对具有高阶关系的网络的建模。另一方面，超图信号处理技术更强大，因为它们可以解释数据节点之间潜在的多向关系。超图信号处理工具可用于不同领域，包括数据科学、通信网络、流行病学和社会学，以及从机器人和自动驾驶导航到遥感和网络物理系统的众多应用。例如，遥感中的点云三维成像是一项新兴的关键技术，可以应用本项目正在开发的工具。为了配合该项目的科学目标，研究团队将开发关于图和超图信号处理的教育模块，向本国机构的广大学生介绍这一新兴领域。研究工作从根本上背离了以前依赖于对称正则多进张量分解的工作。相反，理论基础是基于最近在张量代数中引入的t积运算，它允许类似于矩阵分解和特征分解的张量分解。采用t特征分解的优点是引人注目的——它们保留了张量的固有结构和它们的信号的高维性质；最重要的是，由该公式导出的正交特征基允许无损失的傅立叶分解和计算效率的计算。因此，新的框架将允许传统图信号处理技术的泛化，同时保持由超图表示的复杂系统的维数特征。为此，将介绍新的超图信号处理框架的核心元素，包括移位算子、卷积和各种超图信号的定义。超图傅里叶空间也将被定义，然后是带限信号，采样和学习的概念。新框架的优点将在光谱聚类、去噪和分类等应用中得到证明。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This collaborative research project aims to develop a new hypergraph signal-processing framework based on tensor representations to exploit multi-way interactions in data from complex relations. Simple graphs can model only pairwise relationships among data, which prevents their application to modeling networks with higher-order relationships. Hypergraph signal-processing techniques, on the other hand, are more powerful since they can account for the underlying polyadic relationships among data nodes. Hypergraph signal-processing tools can be used in different areas, including data science, communication networks, epidemiology, and sociology, and in numerous applications - from robotics and self-driving navigation to remote sensing and cyber-physical systems. Point-cloud 3D imaging in remote sensing, for instance, is an emerging and critical technology wherein the tools under development in this project can be applied. In concert with the scientific goals of the project, the team of researchers will develop educational modules on graph and hypergraph signal processing to introduce this emerging field to a broad set of students at their home institutions. The research effort radically departs from prior work that relied on symmetric canonical polyadic tensor decompositions. Instead, the theoretical underpinnings are based on the more recently introduced t-product operation in tensor algebra, which allows tensor factorizations that are analogous to matrix factorizations and eigendecompositions. The advantages of adopting t-eigendecompositions are compelling - they preserve the intrinsic structure of tensors and the high-dimensional nature of their signals; most importantly, the orthogonal eigenbasis derived from this formulation allows for a loss-free Fourier decomposition and computationally efficient calculations. The new framework will thus allow for the generalization of traditional graph signal-processing techniques while keeping the dimensionality characteristic of the complex systems represented by hypergraphs. To this end, core elements of the new hypergraph signal-processing framework will be introduced, including shifting operators, convolutions, and the definition of various hypergraph signals. The hypergraph Fourier space will also be defined, followed by the concepts of bandlimited signals, sampling, and learning. The benefits of the new framework will be demonstrated in applications such as spectral clustering, denoising, and classification.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.