Efficient Directed Graph Sampling via Gershgorin Disc Alignment

Abstract

Graph sampling is the problem of choosing a node subset via sampling matrix H \0,1\^K N to collect samples y = H x R^K, K < N, so that the target signal x R^N can be reconstructed in high fidelity. While sampling on undirected graphs is well studied, we propose the first sampling scheme tailored specifically for directed graphs, leveraging a previous undirected graph sampling method based on Gershgorin disc alignment (GDAS). Concretely, given a directed positive graph G^d specified by random-walk graph Laplacian matrix L_rw, we first define reconstruction of a smooth signal x^* from samples y using graph shift variation (GSV) \|L_rw x\|^2_2 as a signal prior. To minimize worst-case reconstruction error of the linear system solution x^* = C^-1 H^ y with symmetric coefficient matrix C = H^ H + L_rw^ L_rw, the sampling objective is to choose H to maximize the smallest eigenvalue _(C) of C. To circumvent eigen-decomposition entirely, we maximize instead a lower bound ^-_(SCS^-1) of _(C) -- smallest Gershgorin disc left-end of a similarity transform of C -- via a variant of GDAS based on Gershgorin circle theorem (GCT). Experimental results show that our sampling method yields smaller signal reconstruction errors at a faster speed compared to competing schemes.

Tasks

Reproductions