Eigen-Decomposition-Free Directed Graph Sampling via Gershgorin Disc Alignment

Yuejiang Li; H. Vicky Zhao; Gene Cheung

ICASSP 2023accepted0 citations

Eigen-Decomposition-Free 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 = Hx ∈ℝ K , K < N, so that the target signal x ∈ ℝ N can be reconstructed in high fidelity. While sampling on undirected graphs is well studied, we propose the first eigen-decomposition-free 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 ${{\mathcal{G}}^d}$ specified by random-walk graph Laplacian matrix L <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">rw</inf> , we first define reconstruction of a smooth signal x ∗ from samples y using graph shift variation (GSV) $\left\| {{{\mathbf{L}}_{rw}}{\mathbf{x}}} \right\|_2^2$ as a signal prior. To minimize the worst-case reconstruction error of the linear system solution x ∗ = C −1 H ⊤ y with symmetric coefficient matrix${\mathbf{C}} = {{\mathbf{H}}^ \top }{\mathbf{H}} + \mu {\mathbf{L}}_{rw}^ \top {{\mathbf{L}}_{rw}}$, the E-optimality sampling objective is to choose H to maximize the smallest eigenvalue λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">min</inf> (C) of C. To circumvent eigen-decomposition, we maximize instead a lower bound $\lambda _{\min }^ - \left( {{\mathbf{SC}}{{\mathbf{S}}^{ - 1}}} \right)$ of λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">min</inf> (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 yielded smaller signal reconstruction errors at a faster speed compared to competing schemes.

BibTeX

@inproceedings{icassp2023_eigendecompositi,
  title = {Eigen-Decomposition-Free Directed Graph Sampling via Gershgorin Disc Alignment},
  author = {Yuejiang Li and H. Vicky Zhao and Gene Cheung},
  booktitle = {ICASSP 2023},
  year = {2023}
}