Optimal Approximate Matrix Multiplication over Sliding Windows

Matrix multiplication is a core operation in numerous applications, yet its exact computation becomes prohibitively expensive as data scales, especially in streaming environments where timeliness is critical. In many real-world scenarios, data arrives continuously, making it essential to focus on recent information via sliding windows. While existing approaches offer approximate solutions, they often suffer from suboptimal space complexities when extended to the sliding-window setting.

In this work, we introduce SO-COD, a novel algorithm for approximate matrix multiplication (AMM) in the sliding-window streaming setting, where only the most recent data is retained for computation. Inspired by frequency estimation over sliding windows, our method tracks significant contributions, referred to as "snapshots", from incoming data and efficiently updates them as the window advances. Given matrices 𝑿 ∈ R 𝑑 𝑥 ×𝑛 and 𝒀 ∈ R 𝑑 𝑦 ×𝑛 for computing 𝑿 𝒀 𝑇 , we analyze two data settings. In the normalized setting, where each column of the input matrices has a unit 𝐿 2 norm, SO-COD achieves an optimal space complexity of 𝑂