On the Correlation Matrix of the Discrete Fourier Transform and the Fast Solution of Large Toeplitz Systems For Long-Memory Time Series

Abstract

For long-memory time series, we show that the Toeplitz system §n(f)x = b can be solved in O(n log5=2 n) operations using a well-known version of the preconditioned conjugate gradient method, where §n(f) is the n£n covariance matrix, f is the spectral density and b is a known vector. Solutions of such systems are needed for optimal linear prediction and interpolation. We establish connections between this preconditioning method and the frequency domain analysis of time series. Indeed, the running time of the algorithm is determined by rate of increase of the condition number of the correlation matrix of the discrete Fourier transform vector, as the sample size tends to 1. We derive an upper bound for this condition number. The bound is of interest in its own right, as it sheds some light on the widely-used but heuristic approximation that the standardized DFT coefficients are uncorrelated with equal variances. We present applications of the preconditioning methodology to the forecasting and smoothing of volatility in a long memory stochastic volatility model, and to the evaluation of the Gaussian likelihood function of a long-memory model.