TY - GEN

T1 - Single pass spectral sparsification in dynamic streams

AU - Kapralov, Michael

AU - Lee, Yin Tat

AU - Musco, Cameron

AU - Musco, Christopher

AU - Sidford, Aaron

PY - 2014/12/7

Y1 - 2014/12/7

N2 - We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph, G, our algorithm maintains a randomized linear sketch of the incidence matrix into dimension O((1/ε2) n polylog(n)). Using this sketch, the algorithm can output a (1 +/-ε) spectral sparsifier for G with high probability. While O((1/ε2) n polylog(n)) space algorithms are known for computing cut sparsifiers in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in insertion-only streams [KL11], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension ω((1/ε2) n(5/3)) [AGM14]. To achieve our result, we show that, using a coarse sparsifier of G and a linear sketch of G's incidence matrix, it is possible to sample edges by effective resistance, obtaining a spectral sparsifier of arbitrary precision. Sampling from the sketch requires a novel application of ℓ2/ℓ2 sparse recovery, a natural extension of the ℓ0 methods used for cut sparsifiers in [AGM12b]. Recent work of [MP12] on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix AT A given a stream of updates to rows in A.

AB - We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph, G, our algorithm maintains a randomized linear sketch of the incidence matrix into dimension O((1/ε2) n polylog(n)). Using this sketch, the algorithm can output a (1 +/-ε) spectral sparsifier for G with high probability. While O((1/ε2) n polylog(n)) space algorithms are known for computing cut sparsifiers in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in insertion-only streams [KL11], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension ω((1/ε2) n(5/3)) [AGM14]. To achieve our result, we show that, using a coarse sparsifier of G and a linear sketch of G's incidence matrix, it is possible to sample edges by effective resistance, obtaining a spectral sparsifier of arbitrary precision. Sampling from the sketch requires a novel application of ℓ2/ℓ2 sparse recovery, a natural extension of the ℓ0 methods used for cut sparsifiers in [AGM12b]. Recent work of [MP12] on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers. Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix AT A given a stream of updates to rows in A.

KW - dimensionality reduction

KW - sketching

KW - sparse recovery

KW - sparsification

KW - streaming

UR - http://www.scopus.com/inward/record.url?scp=84920047825&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84920047825&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2014.66

DO - 10.1109/FOCS.2014.66

M3 - Conference contribution

AN - SCOPUS:84920047825

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 561

EP - 570

BT - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

PB - IEEE Computer Society

T2 - 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014

Y2 - 18 October 2014 through 21 October 2014

ER -