  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. 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 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. 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.
