Dynamic Kernel Graph Sparsifiers

A geometric graph associated with a set of points P= x1, x2, cdots, xn subset ℝd and a fixed kernel function mathsfK:ℝd× ℝd→ℝ≥ 0 is a complete graph on P such that the weight of edge (xi, xj) is mathsfK(xi, xj). 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 no(1) with high probability, and the initialization time is n1+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 no(1) time, under sparse updates to the query vectors, or under modification of points in P.