Joint Signal Interpolation / Time-Varying Graph Estimation Via Smoothness and Low-Rank Priors

A basic premise in graph signal processing (GSP) is the existence of an underlying graph capturing pairwise similarities/correlations between nodes, using which graph filtering tasks such as denoising and interpolation are performed. In practice, node-to-node similarities often evolve over time, and thus, ideally, the graph structure should adapt accordingly. In this paper, we model the temporal changes in the adjacency matrix between two consecutive time instants as a low-rank matrix. Specifically, given an initial graph structure, we jointly interpolate a partial signal and estimate a graph at later times using graph signal smoothness priors and a low-rank prior for the adjacency difference matrix. We alternate optimization steps: given a fixed graph, the signal is computed as a solution to a linear system using conjugate gradient (CG), and given a fixed signal, the adjacency matrix is optimized via a new variant of proximal gradient descent (PGD). Experiments show that our joint optimization produces better interpolation results than existing graph learning schemes.