论文标题
通过gershgorin盘对齐的有效的定向图采样
Efficient Directed Graph Sampling via Gershgorin Disc Alignment
论文作者
论文摘要
图抽样是通过采样矩阵$ \ mathbf {h} \ in \ {0,1 \}^{k \ times n} $选择样品来收集样品$ \ mathbf {y} = \ mathbf {目标信号$ \ mathbf {x} \ in \ mathbb {r}^n $可以以高保真度重建。虽然对无向图上的采样进行了充分的研究，但我们提出了专门针对有向图定制的第一个采样方案，利用基于Gershgorin盘盘对准（GDAS）的先前的无向图采样方法（GDAS）。具体而言，给定一个定向的阳性图$ \ MATHCAL {G}^D $由随机步行图Laplacian矩阵$ \ Mathbf {l} _ {rw} $指定，我们首先定义平稳的重构信号$ \ Mathbf {x}^$ from samples $ \ m m iathbf） $ \ | \ Mathbf {l} _ {rw} \ Mathbf {x} \ |^2_2 $作为信号先验。要最小化线性系统解决方案的最差重建错误$ \ MathBf {X}^* = \ m athbf {C}^{ - 1} \ Mathbf { \ Mathbf {H} +μ\ MathBf {l} _ {rw}^\ top \ top \ Mathbf {l} _ {rw} $，采样目标是选择$ \ m athbf {h} $，以最大程度地提高最小的Eigenvalue $ ue $λ_} $ { $ \ mathbf {c} $。为了完全绕过特征分解，我们最大化下限的$λ^-_ {\ min}（\ MathBf {s} \ Mathbf {C} \ MathBf {c} \ Mathbf {s}^{ - 1} $ $ \ Mathbf {C} $的转换 - 通过基于Gershgorin Circle定理（GCT）的GDA的变体。实验结果表明，与竞争方案相比，我们的采样方法以更快的速度产生较小的信号重建误差。
Graph sampling is the problem of choosing a node subset via sampling matrix $\mathbf{H} \in \{0,1\}^{K \times N}$ to collect samples $\mathbf{y} = \mathbf{H} \mathbf{x} \in \mathbb{R}^K$, $K < N$, so that the target signal $\mathbf{x} \in \mathbb{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 $\mathcal{G}^d$ specified by random-walk graph Laplacian matrix $\mathbf{L}_{rw}$, we first define reconstruction of a smooth signal $\mathbf{x}^*$ from samples $\mathbf{y}$ using graph shift variation (GSV) $\|\mathbf{L}_{rw} \mathbf{x}\|^2_2$ as a signal prior. To minimize worst-case reconstruction error of the linear system solution $\mathbf{x}^* = \mathbf{C}^{-1} \mathbf{H}^\top \mathbf{y}$ with symmetric coefficient matrix $\mathbf{C} = \mathbf{H}^\top \mathbf{H} + μ\mathbf{L}_{rw}^\top \mathbf{L}_{rw}$, the sampling objective is to choose $\mathbf{H}$ to maximize the smallest eigenvalue $λ_{\min}(\mathbf{C})$ of $\mathbf{C}$. To circumvent eigen-decomposition entirely, we maximize instead a lower bound $λ^-_{\min}(\mathbf{S}\mathbf{C}\mathbf{S}^{-1})$ of $λ_{\min}(\mathbf{C})$ -- smallest Gershgorin disc left-end of a similarity transform of $\mathbf{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.
