Spectral Sparsification of Graphs
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Claim: every weighted undirected graph admits a spectral sparsifier with about N log N / ε^2 edges that preserves the Laplacian quadratic form up to 1±ε. Construction samples edges proportional to their effective resistances; computing those uses a low‑dimensional sketch via Johnson–Lindenstrauss projection plus O(log N) Laplacian solves. Deterministic 4N/ε^2 sparsifiers exist but are slow; Kelner–Levin give a one‑pass semi‑streaming sampler with amortized polylog updates.
AI-written summary · about
chapters (33)
- 0:00Intro
- 0:18Graphs
- 1:49Intended Application
- 2:22Cut Approximation Benczur-Karger'96
- 3:22Example: The Complete Graph
- 5:49The Laplacian Matrix
- 7:48The Laplacian Quadratic Form
- 8:55Cuts and the Quadratic Form
- 9:34Spectral Approximation ST'04
- 12:16Spectral Graph Theory
- 12:37Natural Setting
- 15:40Outer Product Expansion
- 16:52Original Goal
- 17:41More General Goal
- 18:20Equivalent General Goal
- 19:35Core Problem
- 21:05Examples of the Reduction
- 22:53Effective Resistance View
- 24:07Electrical Intuition
- 24:39Matrix Chernoff Bound Rudelson'99
- 26:29Resistances are Distances
- 27:37Nearly Linear Time
- 29:22Actual Algorithm
- 30:03Connection to Low Rank Appx.
- 31:25Deterministic Solution [Batson-Spielman-S'09]
- 31:58The Semi-Streaming Model
- 33:15Naïve Approach
- 34:56Main Idea
- 38:45Properties of Resistance
- 39:51Resparsification Algorithm
- 42:03Why does this work?
- 43:01Summary
- 43:20Open Questions
related talks
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 09mSketching High-Dimensional Data
01h 10mSketching High-Dimensional Data
01h 13mSketching High-Dimensional Data
01h 21mAn Overview on Data Streams Algorithms
01h 03mSketching as a Tool for Numerical Linear Algebra
52mRelative Error Tensor Low Rank Approximation
01h 04mSampling Big Ideas in Sublinear Algorithms