The sliding window model, in which only the most recent W updates of a larger data stream form the underlying set, captures settings where recent data is considered more accurate and important than data that arrived prior to a certain time. Although much existing work in the sliding window model uses the smooth histogram framework, most interesting linear-algebraic problems are not smooth. To overcome this challenge, we consider a new notion of reverse online leverage scores that account for both how unique and how recent a row is. By sampling rows based on their reverse online leverage scores and repeatedly downsampling each time a new row arrives, we obtain algorithms for both spectral approximation and low-rank approximation that are space-optimal up to polylogarithmic factors. The downsampling procedure can be streamlined so that both our spectral approximation algorithm and our low-rank approximation algorithm run in nearly input sparsity runtime. We also show that our techniques have a number of applications to linear-algebraic problems in other settings.

Joint work with Vladimir Braverman, Petros Drineas, Jalaj Upadhyay, David P. Woodruff