Extending Classical Multirate Signal Processing Theory to Graphs - Part II: M-Channel Filter Banks

Abstract

This paper builds upon the basic theory of multirate systems for graph signals developed in the companion paper (Part I) and studiesM-channel polynomial filter banks on graphs. The behavior of such graph filter banks differs from that of classical filter banks in many ways, the precise details depending on the eigenstructure of the adjacency matrix A. It is shown that graph filter banks represent (linear and) periodically shift-variant systems only when A satisfies the noble identity conditions developed in Part I. It is then shown that perfect reconstruction graph filter banks can always be developed when A satisfies the eigenvector structure satisfied by M-block cyclic graphs and has distinct eigenvalues (further restrictions on eigenvalues being unnecessary for this). If A is actually M-block cyclic then these PR filter banks indeed become practical, i.e., arbitrary filter polynomial orders are possible, and there are robustness advantages. In this case the PR condition is identical to PR in classical filter banks – any classical PR example can be converted to a graph PR filter bank on an M-block cyclic graph. It is shown that for M-block cyclic graphs with all eigenvalues on the unit circle, the frequency responses of filters have meaningful correspondence with classical filter banks. Polyphase representations are then developed for graph filter banks and utilized to develop alternate conditions for alias cancellation and perfect reconstruction, again for graphs with specific eigenstructures. It is then shown that the eigenvector condition on the graph can be relaxed by using similarity transforms.