ADMM-based Bipartite Graph Approximation
Aimin Jiang, Jiaan Wan, Yibin Tang, Beilu Ni, Yanping Zhu
Abstract
Because the spectrum folding phenomenon affects the down-sampling of graph signals, both critically sampled and oversampled graph filter banks with down-sampling operations can only be applied to bipartite graphs. However, general graph signals may not reside on bipartite graph structures. In this paper, we present a novel bipartite graph approximation algorithm, which aims to find a bipartite graph sufficiently close to the original graph. To tackle this problem, we first show that, if the non-negativity constraint of adjacency matrices is removed, closed-form solutions can be readily obtained by the eigenvalue decomposition. Based on this fact, an alternating direction method of multipliers (ADMM) is further developed to achieve a real adjacency matrix. Experimental results show that the proposed algorithm outperforms the other proposals in terms of approximation accuracy.
BibTeX
@inproceedings{icassp2019_admmbasedbiparti,
title = {ADMM-based Bipartite Graph Approximation},
author = {Aimin Jiang and Jiaan Wan and Yibin Tang and Beilu Ni and Yanping Zhu},
booktitle = {ICASSP 2019},
year = {2019}
}