A Caltech Library Service

Extending classical multirate signal processing theory to graphs

Teke, Oguzhan and Vaidyanathan, Palghat P. (2017) Extending classical multirate signal processing theory to graphs. In: Wavelets and Sparsity XVII. Proceedings of SPIE. No.10394. Society of Photo-Optical Instrumentation Engineers , Bellingham, WA, Art. No. 103941R. ISBN 9781510612457.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


A variety of different areas consider signals that are defined over graphs. Motivated by the advancements in graph signal processing, this study first reviews some of the recent results on the extension of classical multirate signal processing to graphs. In these results, graphs are allowed to have directed edges. The possibly non-symmetric adjacency matrix A is treated as the graph operator. These results investigate the fundamental concepts for multirate processing of graph signals such as noble identities, aliasing, and perfect reconstruction (PR). It is shown that unless the graph satisfies some conditions, these concepts cannot be extended to graph signals in a simple manner. A structure called M-Block cyclic structure is shown to be sufficient to generalize the results for bipartite graphs on two-channels to M-channel filter banks. Many classical multirate ideas can be extended to graphs due to the unique eigenstructure of M-Block cyclic graphs. For example, the PR condition for filter banks on these graphs is identical to PR in classical theory, which allows the use of well-known filter bank design techniques. In order to utilize these results, the adjacency matrix of an M-Block cyclic graph should be given in the correct permutation. In the final part, this study proposes a spectral technique to identify the hidden M-Block cyclic structure from a graph with noisy edges whose adjacency matrix is given under a random permutation. Numerical simulation results show that the technique can recover the underlying M-Block structure in the presence of random addition and deletion of the edges.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Teke, Oguzhan0000-0002-1131-5206
Vaidyanathan, Palghat P.0000-0003-3003-7042
Additional Information:© 2017 Society of Photo-Optical Instrumentation Engineers (SPIE). This work was supported in parts by the ONR grant N00014-15-1-2118, the NSF grant CCF-1712633, and the Electrical Engineering Carver Mead Research Seed Fund of the California Institute of Technology. The authors would like to thank Dr. Pierre Borgnat for the invitation to write this article.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-15-1-2118
Subject Keywords:Multirate processing, graph signals, block-cyclic graphs, spectral approximation
Series Name:Proceedings of SPIE
Issue or Number:10394
Record Number:CaltechAUTHORS:20171220-142223215
Persistent URL:
Official Citation:Oguzhan Teke, Palghat P. Vaidyanathan, "Extending classical multirate signal processing theory to graphs", Proc. SPIE 10394, Wavelets and Sparsity XVII, 103941R (24 August 2017); doi: 10.1117/12.2272362;
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:83992
Deposited By: George Porter
Deposited On:20 Dec 2017 22:53
Last Modified:15 Nov 2021 20:15

Repository Staff Only: item control page