# Toeplitz Least Squares Problems, Fast Algorithms and Big Data

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 24 Dec 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [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)
- [LSAR: Efficient Leverage Score Sampling Algorithm for the Analysis of Big Time Series Data](https://mlsanity.com/paper/1911.12321/) (2019)
- [Sublinear Time Numerical Linear Algebra for Structured Matrices](https://mlsanity.com/paper/1912.06060/) (2019)
- [Rollage: Efficient Rolling Average Algorithm to Estimate ARMA Models for Big Time Series Data](https://mlsanity.com/paper/2103.09175/) (2021)

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

- [SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data](https://mlsanity.com/paper/2401.00122/) (2023)

## Abstract (arXiv)

In time series analysis, when fitting an autoregressive model, one must solve a Toeplitz ordinary least squares problem numerous times to find an appropriate model, which can severely affect computational times with large data sets. Two recent algorithms (LSAR and Repeated Halving) have applied randomized numerical linear algebra (RandNLA) techniques to fitting an autoregressive model to big time-series data. We investigate and compare the quality of these two approximation algorithms on large-scale synthetic and real-world data. While both algorithms display comparable results for synthetic datasets, the LSAR algorithm appears to be more robust when applied to real-world time series data. We conclude that RandNLA is effective in the context of big-data time series.