Spatio–Spectral Limiting on Replacements of Tori by Cubes

Abstract

A class of graphs is defined in which each vertex of a discrete torus is replaced by a Boolean hypercube in such a way that vertices in a fixed subset of each replacement cube are adjacent to corresponding vertices of a neighboring replacement cube. Bases of eigenvectors of the Laplacians of the resulting graphs are described in a manner suitable for quantifying the concentration of a low-spectrum vertex function on a single vertex replacement. Functions that optimize this concentration on these graphs can be regarded as analogues of Slepian prolate functions that optimize concentration of a bandlimited signal on an interval in the classical setting of the real line. Comparison to the case of a simple discrete cycle shows that replacement allows for higher concentration.

Keywords

• Boolean cube
• discrete torus
• replacement graph
• spatio–spectral limiting
• spectral graph theory