Efficient multidimensional signal decorrelation through Cayley graphs

Abstract

In this work, we generate Cayley graphs to obtain spectra corresponding to orthogonal eigenvectors that efficiently decorrelate multidimensional signals. Optimal signal decorrelation information is commonly obtained from the Karhunen-Loeve transform. However, whereas the traditional KL-transform autocovariance matrix is generated using multiple products between signal components, generating the Cayley graph only requires memory access operations for assigning weights to the graph edges. The graph is generated by coloring the edges between different vertices, where the vertices represent symmetry group elements, and the weight values are accessed from the discrete multidimensional functions. The efficiency from avoiding product calculations allows the use of spectral information for a wide variety of applications, as the sparsity of the spectra indicates the degree to which a function can be maximally decorrelated. For real-world applications, we begin by demonstrating how Cayley graph spectra can be used for one-dimensional signal classification. We extend our theory to multiple dimensions, allowing us to develop higher-dimensional applications. We obtain the Cayley graph representation of multiple two-dimensional image patches, which demonstrates that the spectra at each window patch can be used to match key points between transformed images. As another multidimensional example, we apply the method to a three-dimensional image patch; this is then used for boundary edge detection of three-dimensional scans. Thus, our method is useful for extracting valuable decorrelation information from signals of any number of dimensions, and it can outperform common signal processing techniques for a diverse set of tasks.