# SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data

arXiv: https://arxiv.org/abs/2401.00122 · HTML: https://mlsanity.com/paper/2401.00122/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 30 Dec 2023.

## Builds on (most cited first, 15 of 15)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Lectures on Randomized Numerical Linear Algebra](https://mlsanity.com/paper/1712.08880/) (2017)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [MOLIERE: Automatic Biomedical Hypothesis Generation System](https://mlsanity.com/paper/1702.06176/) (2017)
- [LSAR: Efficient Leverage Score Sampling Algorithm for the Analysis of Big Time Series Data](https://mlsanity.com/paper/1911.12321/) (2019)
- [Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments](https://mlsanity.com/paper/1502.03032/) (2015)
- [Efficient Anomaly Detection via Matrix Sketching](https://mlsanity.com/paper/1804.03065/) (2018)
- [Rollage: Efficient Rolling Average Algorithm to Estimate ARMA Models for Big Time Series Data](https://mlsanity.com/paper/2103.09175/) (2021)
- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)
- [Toeplitz Least Squares Problems, Fast Algorithms and Big Data](https://mlsanity.com/paper/2112.12994/) (2021)

## Built on by (most cited first, 1 of 1)

- [Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores](https://mlsanity.com/paper/2507.08143/) (2025)

## Abstract (arXiv)

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.