# Autocov with FFT

**URL:** <https://discourse.julialang.org/t/autocov-with-fft/4178>\
**Category:** General Usage\
**Tags:** question\
**Created:** [June 9, 2017, 2:39pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178 "2017-06-09T14:39:13Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 9, 2017, 2:39pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/1 "2017-06-09T14:39:13Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![JaredMcB](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jaredmcb/32/14703_2.png) [@JaredMcB](https://discourse.julialang.org/u/JaredMcB)\
**Post date:** [May 8, 2020, 4:51pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/2 "2020-05-08T16:51:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [May 10, 2020, 1:14pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/3 "2020-05-10T13:14:53Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [May 10, 2020, 1:16pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/4 "2020-05-10T13:16:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 10, 2020, 1:41pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/5 "2020-05-10T13:41:58Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [May 10, 2020, 5:03pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/6 "2020-05-10T17:03:27Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![JaredMcB](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jaredmcb/32/14703_2.png) [@JaredMcB](https://discourse.julialang.org/u/JaredMcB)\
**Post date:** [May 21, 2020, 10:48pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/7 "2020-05-21T22:48:20Z")

</div>

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.

```julia
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.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [June 11, 2020, 8:10pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/8 "2020-06-11T20:10:11Z")

</div>

I very recently ported Dan Foreman-Mackey’s implementation of an FFT-based integrated autocorrelation time estimator from [the emcee Python package](https://github.com/dfm/emcee/blob/c14b212964cfc1543c41f0bd186cafb399e847f7/src/emcee/autocorr.py#L48) to Julia.

Dan wrote an excellent blog post about it: [Autocorrelation time estimation | Dan Foreman-Mackey](https://dfm.io/posts/autocorr/)

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

> <https://github.com/bat/BAT.jl/blob/5a7f500bf3a9a37c65822794081eb653bab87aea/src/statistics/autocorr.jl#L99>

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

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [June 11, 2020, 8:12pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/9 "2020-06-11T20:12:58Z")

</div>

CC @cpfiffer, @trappmartin

---

<div class="post-metadata">

**Author:** ![Jon\_Norberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jon_norberg/32/3218_2.png) [@Jon\_Norberg](https://discourse.julialang.org/u/Jon_Norberg)\
**Post date:** [June 11, 2020, 8:17pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/10 "2020-06-11T20:17:53Z")

</div>

I’d be interested in using that!

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 12, 2020, 9:18am UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/11 "2020-06-12T09:18:57Z")

</div>

> [@oschulz](#):
>
> maybe there would be space for it in a more central statistics package?

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

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [June 12, 2020, 11:57am UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/12 "2020-06-12T11:57:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![cpfiffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cpfiffer/32/208747_2.png) [@cpfiffer](https://discourse.julialang.org/u/cpfiffer)\
**Post date:** [June 12, 2020, 3:49pm UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/13 "2020-06-12T15:49:04Z")

</div>

MCMCChains’s upcoming 4.0 release (which is breaking) has [FFT-based autocovariance](https://github.com/TuringLang/MCMCChains.jl/blob/master/src/ess.jl) calculations for effective sample size. Currently it’s not in an exposed API.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [June 13, 2020, 9:54am UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/14 "2020-06-13T09:54:37Z")

</div>

Oh, nice! Do you know how your ESS algorithm compares to the estimator used by emcee ([Autocorrelation time estimation | Dan Foreman-Mackey](https://dfm.io/posts/autocorr/))?

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [February 3, 2022, 7:36am UTC](https://discourse.julialang.org/t/autocov-with-fft/4178/15 "2022-02-03T07:36:14Z")

</div>

> [@Tamas\_Papp](#):
>
> If FFT is a dependency, a mini-package (for only this purpose) could be better.

Is there such a package nowadays?