Adding the derivative of fft

[dsweber2]

I've talked with some folks on the gitter who suggested that I could do this via the @grad method, as in several of the examples in tracker/array.jl. Given that in 1D the partial derivative is just ∂fft(x)_j/∂x_k is just e^{2πik*j/N), if I'm reading how @grad works correctly, it should just be

@grad function fft(xs)
  fft(data(xs)), function (Δ)
    ns = size(xs,1)
    ω = [exp(2π*im*j*k/ns) for j=0:(ns-1), k=0:(ns-1)]
    ω*Δ
  end
end

Here's something I've written to test it:

W = randn(5,5)
f(x) = abs(sum(fft(W*x)))
Wp = param(W)
grads = Tracker.gradient(() -> f(W), Params([Wp]))
grads[Wp]

Which is currently returning zeros. However, the comment I've added on #217 suggests this isn't due to the way I implemented the grad here, but something about the way complex numbers are handled in the Tracker.

[marius311]

Just want to chime in that this would be awesome to have. Have you made any progress on this since this post that you could share, even if not a full PR yet? I will probably play with this as well...

[dsweber2]

it turned out there was some major problems with taking derivatives of complex valued variables; it looks like someone has done some work on this, so it may actually be feasible. When I tried the code again though, it seems to raise the error no method matching back!(::Float64), which is not at all clear to me what's happening. Otoh, it does look like Zygote.jl is also working with complex derivatives, so it may be worth looking into making one there. I currently don't have the time to do too much in this direction though.