Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting

Authors :: Calandriello, Daniele
Lazaric, Alessandro
Valko, Michal
Publication Year :: 2016
Publisher :: arXiv, 2016.
Abstract: We derive a new proof to show that the incremental resparsification algorithm proposed by Kelner and Levin (2013) produces a spectral sparsifier in high probability. We rigorously take into account the dependencies across subsequent resparsifications using martingale inequalities, fixing a flaw in the original analysis.

Subjects :: FOS: Computer and information sciences
Computer Science - Learning
Statistics - Machine Learning
Computer Science - Data Structures and Algorithms
Machine Learning (stat.ML)
Data Structures and Algorithms (cs.DS)
Machine Learning (cs.LG)

Full Text Access

Tools