# LSAR: Efficient Leverage Score Sampling Algorithm for the Analysis of Big Time Series Data

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2019.

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

- [ATD: Augmenting CP Tensor Decomposition by Self Supervision](https://mlsanity.com/paper/2106.07900/) (2021)
- [MTC: Multiresolution Tensor Completion from Partial and Coarse Observations](https://mlsanity.com/paper/2106.07135/) (2021)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Toeplitz Least Squares Problems, Fast Algorithms and Big Data](https://mlsanity.com/paper/2112.12994/) (2021)
- [Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data](https://mlsanity.com/paper/2303.08242/) (2023)
- [SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data](https://mlsanity.com/paper/2401.00122/) (2023)
- [A Hybrid Statistical-Machine Learning Approach for Analysing Online Customer Behavior: An Empirical Study](https://mlsanity.com/paper/2212.02255/) (2022)
- [Iterative Sketching for Secure Coded Regression](https://mlsanity.com/paper/2308.04185/) (2023)

## Abstract (arXiv)

We apply methods from randomized numerical linear algebra (RandNLA) to develop improved algorithms for the analysis of large-scale time series data. We first develop a new fast algorithm to estimate the leverage scores of an autoregressive (AR) model in big data regimes. We show that the accuracy of approximations lies within (1+bigOvarepsilon) of the true leverage scores with high probability. These theoretical results are subsequently exploited to develop an efficient algorithm, called LSAR, for fitting an appropriate AR model to big time series data. Our proposed algorithm is guaranteed, with high probability, to find the maximum likelihood estimates of the parameters of the underlying true AR model and 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 synthetic as well as real data highly support the theoretical results and reveal the efficacy of this new approach.