Signal processing on Cayley and nearly Cayley graphs

Abstract

Graph Signal Processing (GSP) is a dynamic and quickly growing field of study that is motivated by the continued increase in network-based data in today's world and the need for tools to analyze such data. In this dissertation, we address multiple questions arising in the mathematics of GSP and related areas, including Graph Limit Theory and Graphon Signal Processing. We focus on developing techniques for Cayley graphs, which are algebraically-defined and highly symmetric in nature, making them a rich class of graphs for applications. For instance, Cayley graphs appear in contexts such as ranked-choice voting, RNA folding, and small-world networks. This leads to the need for the further advancement of graph signal processing techniques for Cayley graphs. ☐ An important component in the design of GSP techniques is the spectral decomposition of graph adjacency matrices. The main tool in GSP, the graph Fourier transform, relies on an appropriate choice of eigenbasis for the asociated graph matrix. In order to better capture the symmetries in a Cayley graph, we present a spectral decomposition of the adjacency matrix of a weighted Cayley graph based on the representation theory of the underlying group. This representation-theoretic approach offers a significant benefit in that it provides a block-diagonalization of the graph Laplacian matrix resulting in much smaller block sizes than the original matrix. Moreover, the same block-diagonalizing matrix works for any Cayley graph over a given group. Based on this spectral decomposition, we give an explicit recipe for constructing the eigenvalues and eigenvectors of the graph. This leads us to a preferred choice of eigenbasis for the graph Fourier transform when applied to weighted Cayley graphs. ☐ Utilizing these eigenbases, we construct a class of frames for signal processing on weighted Cayley graphs called Frobenius-Schur and Cayley frames. Frames are over-complete spanning sets that are often a more advantageous choice for representing a signal rather than an orthonormal basis, as frames can provide redundancy and allow for the reconstruction of a signal, even if some of the signal information is lost in the process of transmission. We provide a characterization and detailed description for the construction of the Frobenius-Schur and Cayley frames. These frames are especially promising as a tool for GSP on Cayley graphs as they have been shown to provide meaningful interpretation of ranked voting data. ☐ We also address questions in the area of Graphon Signal Processing, which unifies Graph Limit Theory and Graph Signal Processing to provide an instance-independent framework for signal processing on graphs. Given a sequence of graphs of growing size, one possible limiting object is a symmetric, measurable function on [0,1]2, called a graphon. In order to analyze data on the sequence of graphs, one would have to compute a spectral decomposition of the associated matrix for each individual graph. Graph Limit Theory allows us to instead consider the limiting graphon and compute a spectral decomposition only once in order to analyze data on graphs sampled from the graphon. We present examples of Graphon Signal Processing on Cayley graphons, which are the appropriate analogue of Cayley graphs in the graphon setting. Moreover, we lay the foundation for the development of frames on Cayley graphons. ☐ So far, Graphon Signal Processing has only been developed in the context of dense graph sequences. Relying on the Lp theory for sparse graph sequences, we lay the foundation for the development of Graphon Signal Processing in the sparse setting. We present multiple results that, in the sparse setting, relate cut-norm convergence and p → q-norm convergence of graphons as well as establishing convergence for eigenfunctions of the graphon integral operator. These propositions bring us one step closer to defining the graphon Fourier transform for Lp graphons.