arXiv Analytics

Sign in

arXiv:1805.03765 [cs.DS]AbstractReferencesReviewsResources

Numerical Linear Algebra in the Sliding Window Model

Vladimir Braverman, Petros Drineas, Jalaj Upadhyay, Samson Zhou

Published 2018-05-10Version 1

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in the data stream form the underlying set. Much of the previous work in the sliding window model uses one of two frameworks: either the exponential histogram (Datar et al., SICOMP'02) or the smooth histogram (Braverman and Ostrovsky, FOCS'07). We show that some elementary linear algebraic problems, such as the estimation of matrix $\ell_p$ norms, can be addressed in the sliding window model using these frameworks. Specifically, we show that approximating matrix entrywise norms for all $p < \infty$ and Schatten $p$-norms for $p=0,1$, and $2$ (which include the matrix rank, the trace or nuclear norm, and the Frobenius norm) are suitable for the smooth histogram framework. However, most "interesting" problems are not smooth and specifically, we show that the spectral norm, vector induced matrix norms, generalized regression, low-rank approximation, and leverage scores are not amenable for the smooth histogram framework. To overcome this challenge, we generalize the smooth histogram framework from real-valued functions to matrix-valued functions. We believe that this framework is a natural way to study numerical linear algebra problems in the sliding window model and perhaps beyond. We then apply our framework to derive approximations for the following linear algebraic functions in the sliding window model: Spectral sparsification, Low-rank approximation, Generalized regression, Graph sparsification (and applications), Matrix multiplication, Row-subset selection. In addition to the results presented in this paper, we hope that our new framework will be useful in developing future randomized numerical linear algebra algorithms.

Related articles: Most relevant | Search more
arXiv:1504.05553 [cs.DS] (Published 2015-04-21)
A Unified Approach for Clustering Problems on Sliding Windows
arXiv:1611.00129 [cs.DS] (Published 2016-11-01)
Submodular Maximization over Sliding Windows
arXiv:1805.00212 [cs.DS] (Published 2018-05-01)
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows