M-Channel Perfect Recovery of Coarsened Graphs and Graph Signals With Spectral Invariance and Topological Preservation

摘要

In this paper, an M-channel perfect reconstruction filter bank based on a coarsening algorithm is proposed. Compared with most of the designs of graph filter banks that do not consider the graph reconstruction, our proposed design can provide the perfect graph reconstruction as well as perfect graph signal reconstruction. In the analysis part, the proposed filter bank provides a coarse version of the input graph as well as coarsened graph signal spectral invariant to the input signal. In the synthesis part, the filter bank perfectly reconstructs the input graph as well as input signal from their coarse version. The spirit of the proposed design is to partition the spectral information of the input graph and input graph signal into every channel. The partition method is adjustable and can be nonuniform. Two intuitive schemes named sort-by-eigenvalue and sort-by-intensity for uniform partition are introduced. In the proposed design, the coarsening operators are obtained through an existing coarsening algorithm, while the recovery operators are defined by taking the conjugate transpose of the coarsening operators. Besides, we address the relation between the proposed design and a framework of sampling graph signals based on the discrete sampling theory. It is shown that the coarsening operator in the proposed design is actually a special case of the sampling operator in the framework based on the discrete sampling theory. Experimental results are presented to demonstrate the effectiveness of the proposed design of filter banks.