Matrix sketching, aimed at approximating a matrix $\boldsymbol{A} \in
\mathbb{R}^{N\times d}$ consisting of vector streams of length $N$ with a
smaller sketching matrix $\boldsymbol{B} \in \mathbb{R}^{\ell\times d}, \ell
\ll N$, has garnered increasing attention in fields such as large-scale data
analytics and machine learning. A well-known deterministic matrix sketching
method is the Frequent Directions algorithm, which achieves the optimal
$O\left(\frac{d}{\varepsilon}\right)$ space bound and provides a covariance
error guarantee of $\varepsilon = \lVert \boldsymbol{A}^\top \boldsymbol{A} -
\boldsymbol{B}^\top \boldsymbol{B} \rVert_2/\lVert \boldsymbol{A} \rVert_F^2$.
The matrix sketching problem becomes particularly interesting in the context of
sliding windows, where the goal is to approximate the matrix
$\boldsymbol{A}_W$, formed by input vectors over the most recent $N$ time
units. However, despite recent efforts, whether achieving the optimal
$O\left(\frac{d}{\varepsilon}\right)$ space bound on sliding windows is
possible has remained an open question.
In this paper, we introduce the DS-FD algorithm, which achieves the optimal
$O\left(\frac{d}{\varepsilon}\right)$ space bound for matrix sketching over
row-normalized, sequence-based sliding windows. We also present matching upper
and lower space bounds for time-based and unnormalized sliding windows,
demonstrating the generality and optimality of \dsfd across various sliding
window models. This conclusively answers the open question regarding the
optimal space bound for matrix sketching over sliding windows. Furthermore, we
conduct extensive experiments with both synthetic and real-world datasets,
validating our theoretical claims and thus confirming the correctness and
effectiveness of our algorithm, both theoretically and empirically.

我们介绍了 DS-FD 算法，它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制，证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论，从理论和实证两方面证实了我们算法的正确性和有效性。