Single pass spectral sparsification in dynamic streams

Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    PublisherIEEE Computer Society
    Pages561-570
    Number of pages10
    ISBN (Electronic)9781479965175
    DOIs
    StatePublished - Dec 7 2014
    Event55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States
    Duration: Oct 18 2014Oct 21 2014

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    ISSN (Print)0272-5428

    Other

    Other55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
    CountryUnited States
    CityPhiladelphia
    Period10/18/1410/21/14

    Keywords

    • dimensionality reduction
    • sketching
    • sparse recovery
    • sparsification
    • streaming

    ASJC Scopus subject areas

    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Single pass spectral sparsification in dynamic streams'. Together they form a unique fingerprint.

  • Cite this

    Kapralov, M., Lee, Y. T., Musco, C., Musco, C., & Sidford, A. (2014). Single pass spectral sparsification in dynamic streams. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 561-570). [6979041] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS.2014.66