提出最优空间复杂度的滑动窗口矩阵乘法算法，兼顾精度与效率。
Optimal Approximate Matrix Multiplication over Sliding Windows
- 设计确定性算法DS-COD，实现空间-误差最优权衡。
- 理论证明算法误差界与空间下界紧致，达到最优性能。
- 自适应版本aDS-COD提升计算效率，实测表现更优。
我们研究在滑动窗口模型下的近似矩阵乘法（AMM）问题，该模型通过有限空间流式处理大规模矩阵乘法，适用于机器学习与数据挖掘中对时间敏感和抑制过时数据的场景。尽管近期取得进展，但该问题的最优空间边界仍为开放问题。本文提出DS-COD算法，一种新颖且确定性的滑动窗口AMM方法，实现了空间-误差权衡的最优性。我们给出了算法的理论误差界与复杂度分析，并建立了滑动窗口AMM问题的空间下界。此外，提出自适应版本aDS-COD，提升了计算效率，实验在合成与真实数据集上验证了理论结果，展现了方法的实际有效性。
原文摘要 · Abstract (English)
We explore the problem of approximate matrix multiplication (AMM) within the sliding window model, where algorithms utilize limited space to perform large-scale matrix multiplication in a streaming manner. This model has garnered increasing attention in the fields of machine learning and data mining due to its ability to handle time sensitivity and reduce the impact of outdated data. However, despite recent advancements, determining the optimal space bound for this problem remains an open question. In this paper, we introduce the DS-COD algorithm for AMM over sliding windows. This novel and deterministic algorithm achieves optimal performance regarding the space-error tradeoff. We provide theoretical error bounds and the complexity analysis for the proposed algorithm, and establish the corresponding space lower bound for the AMM sliding window problem. Additionally, we present an adaptive version of DS-COD, termed aDS-COD, which improves computational efficiency and demonstrates superior empirical performance. Extensive experiments conducted on both synthetic and real-world datasets validate our theoretical findings and highlight the practical effectiveness of our methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。