Dec, 2023
SALSA：顺序近似杠杆分数算法及其在分析大规模时间序列数据中的应用
SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data
Ali Eshragh, Luke Yerbury, Asef Nazari, Fred Roosta, Michael W. Mahoney
TL;DR使用随机数值线性代数方法开发了一种新的高效的顺序近似杠杆分数算法 SALSA，证明其近似的准确性高概率地与真实杠杆分数的差异在 (1 + O (ε)) 之内。此外，展示了 SALSA 在理论计算复杂度和数值精确度方面超越现有近似方法，并基于该理论结果提出了一种名为 LSARMA 的高效算法，用于拟合大规模时间序列数据的适当 ARMA 模型。我们提出的算法高概率地能够找到真实潜在 ARMA 模型参数的最大似然估计，并在大数据环境下具有显著改进状态的最新替代方案的最坏运行时间。针对大规模数据的实证结果强力支持这些理论结果，并强调了我们新方法的功效。