A Caltech Library Service

Extending Classical Multirate Signal Processing Theory to Graphs - Part I: Fundamentals

Teke, Oguzhan and Vaidyanathan, P. P. (2017) Extending Classical Multirate Signal Processing Theory to Graphs - Part I: Fundamentals. IEEE Transactions on Signal Processing, 65 (2). pp. 409-422. ISSN 1053-587X. doi:10.1109/TSP.2016.2617833.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Signal processing on graphs finds applications in many areas. In recent years renewed interest on this topic was kindled by two groups of researchers. Narang and Ortega constructed two-channel filter banks on bipartitie graphs described by Laplacians. Sandryhaila and Moura developed the theory of linear systems, filtering, and frequency responses for the case of graphs with arbitrary adjacency matrices, and showed applications in signal compression, prediction, etc. Inspired by these contributions, this paper extends classical multirate signal processing ideas to graphs. The graphs are assumed to be general with a possibly non-symmetric and complex adjacency matrix. The paper revisits ideas such as noble identities, aliasing, and polyphase decompositions in graph multirate systems. Drawing such a parallel to classical systems allows one to design filter banks with polynomial filters, with lower complexity than arbitrary graph filters. It is shown that the extension of classical multirate theory to graphs is nontrivial, and requires certain mathematical restrictions on the graph. Thus, classical noble identities cannot be taken for granted. Similarly, one cannot claim that the so-called delay chain system is a perfect reconstruction system (as in classical filter banks). It will also be shown that M-partite extensions of the bipartite filter bank results will not work for M-channel filter banks, but a more restrictive condition called M-block cyclic property should be imposed. Such graphs are studied in detail. A detailed theory for M-channel filter banks is developed in a companion paper.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
Teke, Oguzhan0000-0002-1131-5206
Vaidyanathan, P. P.0000-0003-3003-7042
Additional Information:© 2016 IEEE. Manuscript received July 28, 2015; revised February 12, 2016 and June 6, 2016; accepted September 9, 2016. Date of publication October 13, 2016; date of current version November 17, 2016. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Pierre Borgnat. This work was supported in part by the ONR Grants N00014-11-1-0676 and N00014-15-1-2118, and in part by the California Institute of Technology.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1-0676
Office of Naval Research (ONR)N00014-15-1-2118
Subject Keywords:Multirate processing, graph signals, aliasing on graphs, bandlimited graph signals, block-cyclic graphs
Issue or Number:2
Record Number:CaltechAUTHORS:20161020-135015457
Persistent URL:
Official Citation:O. Teke and P. P. Vaidyanathan, "Extending Classical Multirate Signal Processing Theory to Graphs—Part I: Fundamentals," in IEEE Transactions on Signal Processing, vol. 65, no. 2, pp. 409-422, Jan.15, 15 2017. doi: 10.1109/TSP.2016.2617833 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71323
Deposited By: Tony Diaz
Deposited On:20 Oct 2016 21:46
Last Modified:11 Nov 2021 04:43

Repository Staff Only: item control page