SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929195586682880 |
|---|---|
| author | Eshragh, Ali Yerbury, Luke Nazari, Asef Roosta, Fred Mahoney, Michael W. |
| author_facet | Eshragh, Ali Yerbury, Luke Nazari, Asef Roosta, Fred Mahoney, Michael W. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00122 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data Eshragh, Ali Yerbury, Luke Nazari, Asef Roosta, Fred Mahoney, Michael W. Machine Learning 62M10 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. |
| title | SALSA: Sequential Approximate Leverage-Score Algorithm with Application in Analyzing Big Time Series Data |
| topic | Machine Learning 62M10 |
| url | https://arxiv.org/abs/2401.00122 |