On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series

We show that for long-memory time series, the Toeplitz system Sigma(n)(f)x = b can be solved in O(n log(5/2) n) operations using a well-known version of the preconditioned conjugate gradient method, where Sigma(n)(f) is the n x 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 the rate of increase in the condition number of the correlation matrix of the discrete Fourier transform (DFT) vector, as the sample size tends to infinity. We derive an upper bound for this condition number. The bound is of interest in its own right, because 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 of volatility in a long-memory stochastic volatility model, and to the evaluation of the Gaussian likelihood function of a long-memory model.