Near optimal linear algebra in the online and sliding window models

Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou

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

    Abstract

    We initiate the study of numerical linear algebra in the sliding window model, where only the most recent W updates in a stream form the underlying data set. Although many existing algorithms in the sliding window model use or borrow elements from the smooth histogram framework (Braverman and Ostrovsky, FOCS 2007), we show that many interesting linear-algebraic problems, including spectral and vector induced matrix norms, generalized regression, and low-rank approximation, are not amenable to this approach in the row-arrival model. To overcome this challenge, we first introduce a unified row-sampling based framework that gives randomized algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and ell {1}-subspace embeddings in the sliding window model, which often use nearly optimal space and achieve nearly input sparsity runtime. Our algorithms are based on'reverse online' versions of offline sampling distributions such as (ridge) leverage scores, ell {1} sensitivities, and Lewis weights to quantify both the importance and the recency of a row; our structural results on these distributions may be of independent interest for future algorithmic design. Although our techniques initially address numerical linear algebra in the sliding window model, our row-sampling framework rather surprisingly implies connections to the well-studied online model; our structural results also give the first sample optimal (up to lower order terms) online algorithm for low-rank approximation/projection-cost preservation. Using this powerful primitive, we give online algorithms for column/row subset selection and principal component analysis that resolves the main open question of Bhaskara et al. (FOCS 2019). We also give the first online algorithm for ell {1}-subspace embeddings. We further formalize the connection between the online model and the sliding window model by introducing an additional unified framework for deterministic algorithms using a merge and reduce paradigm and the concept of online coresets, which we define as a weighted subset of rows of the input matrix that can be used to compute a good approximation to some given function on all of its prefixes. Our sampling based algorithms in the row-arrival online model yield online coresets, giving deterministic algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and ell {1}-subspace embeddings in the sliding window model that use nearly optimal space.

    Original languageEnglish (US)
    Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
    PublisherIEEE Computer Society
    Pages517-528
    Number of pages12
    ISBN (Electronic)9781728196213
    DOIs
    StatePublished - Nov 2020
    Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
    Duration: Nov 16 2020Nov 19 2020

    Publication series

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

    Conference

    Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
    Country/TerritoryUnited States
    CityVirtual, Durham
    Period11/16/2011/19/20

    Keywords

    • numerical linear algebra
    • online algorithms
    • sliding window model
    • streaming algorithms

    ASJC Scopus subject areas

    • Computer Science(all)

    Fingerprint

    Dive into the research topics of 'Near optimal linear algebra in the online and sliding window models'. Together they form a unique fingerprint.

    Cite this