Autocov with FFT

General Usage
1

Is there a package which has an implementation of autocovariances using FFT? With lots of lags, it should be much faster than the simple approach (eg in StatsBase.autocov).

If there is none, which appears to be my impression, I will code one up and submit to a package, but I wanted to check to save effort.

1 Like
2

@Tamas_Papp I am also interested in an autocovariance implementation that uses FFT. Have you found one or did you end up writing one?

3

I’ve recently looked for exactly the same (probably for a very similar use case to your’s too) …

4

I assume you want to use in context of MCMC convergence? Would be lovely to have a package with fast FFT-based autocov for that, instead of picking just a few lag values.

5

FWIW, I think even the most naive autocorrelation implementation has an insignificant cost compared to MCMC. And then you need a few lags anyway (after a while, they are just noise).

6

True - still, with an FFT, it’ll be very performant and no need to decide on lags up front. Also, could be a good basis for estimating effective number of samples, right?

7

That’s right, I’ve been needing it to approximate autocorrelation time for just that purpose, effective number of samples as well as informing how many samples to discard prior to equilibrium. And so I have a lot of lags and long timeseries. I have been getting by though with this little function that uses the conv function from DSP.jl. The conv uses FFT.

function autocov_con(x::AbstractVector{<:Real},lags::UnitRange{Int})
    lx = size(x,1)
    x .-= mean(x)
    A = conv(x,reverse(x))/lx
    A = [A[k + lx] for k in lags]
end

I have found it to be much faster than autocov form StatsBase.jl when there are many lags. You see in this naive implementation I compute the autocorrelation for all lags and then truncate. And, @Tamas_Papp thank you for your Dec '17 post about inserting code, that was really helpful.

1 Like
8

I very recently ported Dan Foreman-Mackey’s implementation of an FFT-based integrated autocorrelation time estimator from the emcee Python package to Julia.

Dan wrote an excellent blog post about it: Autocorrelation time estimation | Dan Foreman-Mackey

I did put it in BAT.jl for now (since that’s where I’ll need it most)

but maybe there would be space for it in a more central statistics package?

1 Like
9

CC @cpfiffer, @trappmartin

10

I’d be interested in using that!

11

If FFT is a dependency, a mini-package (for only this purpose) could be better.

1 Like
12

Yes, the FFT dependency is why I wouldn’t propose it for StatsBase or so …

So yes, if there’s interest, I’ll probably make a small standalone package for it.

13

MCMCChains’s upcoming 4.0 release (which is breaking) has FFT-based autocovariance calculations for effective sample size. Currently it’s not in an exposed API.

2 Likes
14

Oh, nice! Do you know how your ESS algorithm compares to the estimator used by emcee (Autocorrelation time estimation | Dan Foreman-Mackey)?

1 Like
15

Is there such a package nowadays?