2024/04/25 by Christopher J. Geoga, Geoga, Christopher J.
Computer Science · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Methodology (stat.ME) #Neural Networks and Applications #Numerical Analysis (math.NA) #Time Series Analysis and Forecasting
paper · pdf · doi:10.48550/arxiv.2404.16583
openalex publication_date 2024/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We provide in this work an algorithm for approximating a very broad class of symmetric Toeplitz matrices to machine precision in O(n log n) time with applications to fitting time series models. In particular, for a symmetric Toeplitz matrix \mathbfΣ with values \mathbfΣj,k = h|j-k| = ∫-1/21/2 e2 πi |j-k| ω S(ω) d ω where S(ω) is piecewise smooth, we give an approximation F \mathbfΣ FH ≈ D + U VH, where F is the DFT matrix, D is diagonal, and the matrices U and V are in ℂn × r with r ≪ n. Studying these matrices in the context of time series, we offer a theoretical explanation of this structure and connect it to existing spectral-domain approximation frameworks. We then give a complete discussion of the numerical method for assembling the approximation and demonstrate its efficiency for improving Whittle-type likelihood approximations, including dramatic examples where a correction of rank r = 2 to the standard Whittle approximation increases the accuracy of the log-likelihood approximation from 3 to 14 digits for a matrix \mathbfΣ ∈ ℝ105 × 105. The method and analysis of this work applies well beyond time series analysis, providing an algorithm for extremely accurate solutions to linear systems with a wide variety of symmetric Toeplitz matrices whose entries are generated by a piecewise smooth S(ω). The analysis employed here largely depends on asymptotic expansions of oscillatory integrals, and also provides a new perspective on when existing spectral-domain approximation methods for Gaussian log-likelihoods can be particularly problematic.