CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20161020-135015457

[img] PDF - Accepted Version
See Usage Policy.

8Mb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161020-135015457

Abstract

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
http://dx.doi.org/10.1109/TSP.2016.2617833 DOIArticle
http://ieeexplore.ieee.org/document/7590120/PublisherArticle
ORCID:
AuthorORCID
Teke, Oguzhan0000-0002-1131-5206
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.
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1-0676
Office of Naval Research (ONR)N00014-15-1-2118
CaltechUNSPECIFIED
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:https://resolver.caltech.edu/CaltechAUTHORS:20161020-135015457
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7590120&isnumber=7748608
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71323
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Oct 2016 21:46
Last Modified:03 Oct 2019 16:06

Repository Staff Only: item control page