2017/02/27 by Yin Tat Lee, He Sun, Lee, Yin Tat +1 · 6 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1702.08415
openalex publication_date 2017/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For any undirected and weighted graph G=(V,E,w) with n vertices and m edges, we call a sparse subgraph H of G, with proper reweighting of the edges, a (1+ε)-spectral sparsifier if (1-ε)x\intercalLGx≤ x\intercal LH x≤ (1+ε) x\intercal LGx holds for any x∈ℝn, where LG and LH are the respective Laplacian matrices of G and H. Noticing that Ω(m) time is needed for any algorithm to construct a spectral sparsifier and a spectral sparsifier of G requires Ω(n) edges, a natural question is to investigate, for any constant ε, if a (1+ε)-spectral sparsifier of G with O(n) edges can be constructed in O(m) time, where the O notation suppresses polylogarithmic factors. All previous constructions on spectral sparsification require either super-linear number of edges or m1+Ω(1) time. In this work we answer this question affirmatively by presenting an algorithm that, for any undirected graph G and ε>0, outputs a (1+ε)-spectral sparsifier of G with O(n/ε2) edges in O(m/εO(1)) time. Our algorithm is based on three novel techniques: (1) a new potential function which is much easier to compute yet has similar guarantees as the potential functions used in previous references; (2) an efficient reduction from a two-sided spectral sparsifier to a one-sided spectral sparsifier; (3) constructing a one-sided spectral sparsifier by a semi-definite program.