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

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.