Dynamic Kernel Graph Sparsifiers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918367898632192 |
|---|---|
| author | Cao, Yang Deng, Yichuan Jin, Wenyu Li, Xiaoyu Song, Zhao Sun, Xiaorui Weinstein, Omri |
| author_facet | Cao, Yang Deng, Yichuan Jin, Wenyu Li, Xiaoyu Song, Zhao Sun, Xiaorui Weinstein, Omri |
| contents | A geometric graph associated with a set of points $P= \{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$ and a fixed kernel function $\mathsf{K}:\mathbb{R}^d\times \mathbb{R}^d\to\mathbb{R}_{\geq 0}$ is a complete graph on $P$ such that the weight of edge $(x_i, x_j)$ is $\mathsf{K}(x_i, x_j)$. We present a fully-dynamic data structure that maintains a spectral sparsifier of a geometric graph under updates that change the locations of points in $P$ one at a time. The update time of our data structure is $n^{o(1)}$ with high probability, and the initialization time is $n^{1+o(1)}$. Under certain assumption, our data structure can be made robust against adaptive adversaries, which makes our sparsifier applicable in iterative optimization algorithms. We further show that the Laplacian matrices corresponding to geometric graphs admit a randomized sketch for maintaining matrix-vector multiplication and projection in $n^{o(1)}$ time, under sparse updates to the query vectors, or under modification of points in $P$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_14825 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Dynamic Kernel Graph Sparsifiers Cao, Yang Deng, Yichuan Jin, Wenyu Li, Xiaoyu Song, Zhao Sun, Xiaorui Weinstein, Omri Data Structures and Algorithms A geometric graph associated with a set of points $P= \{x_1, x_2, \cdots, x_n \} \subset \mathbb{R}^d$ and a fixed kernel function $\mathsf{K}:\mathbb{R}^d\times \mathbb{R}^d\to\mathbb{R}_{\geq 0}$ is a complete graph on $P$ such that the weight of edge $(x_i, x_j)$ is $\mathsf{K}(x_i, x_j)$. We present a fully-dynamic data structure that maintains a spectral sparsifier of a geometric graph under updates that change the locations of points in $P$ one at a time. The update time of our data structure is $n^{o(1)}$ with high probability, and the initialization time is $n^{1+o(1)}$. Under certain assumption, our data structure can be made robust against adaptive adversaries, which makes our sparsifier applicable in iterative optimization algorithms. We further show that the Laplacian matrices corresponding to geometric graphs admit a randomized sketch for maintaining matrix-vector multiplication and projection in $n^{o(1)}$ time, under sparse updates to the query vectors, or under modification of points in $P$. |
| title | Dynamic Kernel Graph Sparsifiers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.14825 |