Efficient Graph Learning From Noisy and Incomplete Data

doi:10.1109/TSIPN.2020.2964249

Efficient Graph Learning From Noisy and Incomplete Data

2020-01-01

32

PRE

AI

DOI：10.1109/TSIPN.2020.2964249

Original

Original request for help

Save

Abstract

En 中文

We consider the problem of learning a graph from a given set of smooth graph signals. Our graph learning approach is formulated as a constrained quadratic program in the edge weights. We provide an implicit characterization of the optimal solution and propose a tailored ADMM algorithm to solve this problem efficiently. Several nearest neighbor and smoothness based graph learning methods are shown to be special cases of our approach. Specifically, our algorithm yields an efficient but extremely accurate approximation to $b$-matched graphs. We then propose a generalization of our scheme that can deal with noisy and incomplete data via joint graph learning and signal inpainting. We compare the performance of our approach with state-of-the art methods on synthetic data and on real-world data from the Austrian National Council.

Keywords:

Graph signal processing

topology identification

nearest neighbor graphs

signal inpainting

ADMM

Efficient Graph Learning From Noisy and Incomplete Data

Abstract

AI Summary

Journal

Organization