Circulant structures and graph signal processing

Linear shift-invariant processing of graph signals rests on circulant graphs and filters. The spatial features of circulant structures also permit shift-varying operations such as sampling. Their spectral features-as described by their Graph Fourier Transform profiles-enable novel multiscale signal processing systems and methods. To extend the reach of circulant structures, we present a method to decompose an arbitrary graph or filter into a combination of circulant structures. Our decomposition is analogous to resolving a linear time-varying system into a bank of linear time-invariant systems. As an application, we perform multiscale decomposition on temperature data spanning the continental United States.

1. INTRODUCTION

Numerous modern applications present graph-structured data. Examples include social media (e.g., Facebook and Twitter [1]), wireless sensors (e.g., temperature measurements [2]), power networks [3], computer graphics [4], [5], and finite-element meshes [6]. Researchers in machine learning and computer graphics have spent considerable effort developing techniques to tackle data from large-scale networks. The signal processing community, too, has witnessed a surge of interest in a unified theory for the analysis and processing of graph signals-signals measured at, or otherwise defined on, the vertices of a graph. Traditional signal processing deals with signals measured over regular or well-ordered structures, such as time lines or Cartesian grids. Graph signals, however, present a substantially more nuanced paradigm.