Hanyan Yin

Many real-world matrix datasets arrive as high-throughput vector streams, making it impractical to store or process them in their entirety. To enable real-time analytics under limited computational, memory, and communication resources, matrix sketching techniques have been developed over recent decades to provide compact approximations of such streaming data. Some algorithms have achieved optimal space and communication complexity. However, these approaches often require frequent time-consuming matrix factorization operations. In particular, under tight approximation error bounds, each matrix factorization computation incurs cubic time complexity, thereby limiting their update efficiency. In this paper, we introduce AeroSketch, a novel matrix sketching framework that leverages recent advances in randomized numerical linear algebra (RandNLA). AeroSketch achieves optimal communication and space costs while delivering near-optimal update time complexity (within logarithmic factors) across persistent, sliding window, and distributed streaming scenarios. Extensive experiments on both synthetic and real-world datasets demonstrate that AeroSketch consistently outperforms state-of-the-art methods in update throughput. In particular, under tight approximation error constraints, AeroSketch reduces the cubic time complexity to the quadratic level. Meanwhile, it maintains comparable approximation quality while retaining optimal communication and space costs.

Matrix sketching, aimed at approximating a matrix \(\boldsymbol{A} ∈\mathbb{R}^{N \times d}\)consisting of vector streams of length \(N\)with a smaller sketching matrix \(\boldsymbol{B}∈\mathbb{R}^{\ell\times d}\), \(\ell ≪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({d\over \varepsilon}\right)\)space bound and provides a covariance error guarantee of \(\varepsilon=\lVert \boldsymbol{A}^⊤\boldsymbol{A}-\boldsymbol{B}^⊤\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({d\over\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({d\over\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 DS-FD 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.