We develop a new efficient sequential approximate leverage score algorithm,
SALSA, using methods from randomized numerical linear algebra (RandNLA) for
large matrices. We demonstrate that, with high probability, the accuracy of
SALSA's approximations is within $(1 + O({\varepsilon}))$ of the true leverage
scores. In addition, we show that the theoretical computational complexity and
numerical accuracy of SALSA surpass existing approximations. These theoretical
results are subsequently utilized to develop an efficient algorithm, named
LSARMA, for fitting an appropriate ARMA model to large-scale time series data.
Our proposed algorithm is, with high probability, guaranteed to find the
maximum likelihood estimates of the parameters for the true underlying ARMA
model. Furthermore, it has a worst-case running time that significantly
improves those of the state-of-the-art alternatives in big data regimes.
Empirical results on large-scale data strongly support these theoretical
results and underscore the efficacy of our new approach.

使用随机数值线性代数方法开发了一种新的高效的顺序近似杠杆分数算法 SALSA，证明其近似的准确性高概率地与真实杠杆分数的差异在 (1 + O (ε)) 之内。此外，展示了 SALSA 在理论计算复杂度和数值精确度方面超越现有近似方法，并基于该理论结果提出了一种名为 LSARMA 的高效算法，用于拟合大规模时间序列数据的适当 ARMA 模型。我们提出的算法高概率地能够找到真实潜在 ARMA 模型参数的最大似然估计，并在大数据环境下具有显著改进状态的最新替代方案的最坏运行时间。针对大规模数据的实证结果强力支持这些理论结果，并强调了我们新方法的功效。