I have a question about auto-correlation, in fact quite technical.
By definition we have $$R(t) = \frac{\langle x_{t'} x_{t'-t}\rangle_{t'} }{\langle x_{t'} \rangle_{t'} \langle x_{t'-t}\rangle_{t'} }$$
Or explicitly:
$$R(t) = \frac{\sum_{n=0}^{N} (x_n - \bar{x}) (x_{n+t} - \bar{x} ) } {\left( \sum_{n=0}^{N} (x_n - \bar{x})^2 \sum_{n=0}^N (x_{n+t} - \bar{x} )^2 \right)^{1/2} } $$
If the signal is periodic, one can easily compute the auto-correlation using the power spectrum, this implies using fourier transforms but will be less computationally expensive (\( O(NlogN) \) vs \( O(N^2) \) )
Formaly:
$$R(t) = \frac{{F}^{-1}(|{F}(x_t - \bar{x})|^2)}{\sigma^2}$$
where \({F}\) is the fourier transform operator, and \(\sigma^2\) is the variance of \(x_t\).
But obvioulsy in finance we do not have any chance of this periodicity. So my question is: Is there a good and efficient way to build auto-correlation? Is there a library which compute it efficiently? (Pandas one will give the output of one given lag, so it would need to be called N time (and looking at the panda code that would lead to a \( O(N^2) \) method)).
