fft-based interpolations

[babaq]

matlab have interpft which is a fft-based interpolation, or generally speaking, a smoothing method.

hope this can be added to the package.

[timholy]

Contributions are always welcome!

[ghost]

very easy to implement for 1D real signal ( most cases ) : What I am using :

using FFTW 
function FFTW_based_interpolation(sig::AbstractArray{<:Real,1},n::Integer)
    n_orig = div(length(sig),2)
    return irfft( vcat( rfft(sig), zeros( div(n,2) - n_orig ) ) , n )
end

[tomasaschan]

Is FFTW a heavy package? If so, it might be a bad idea to pull it in as a dependency for everyone who uses Interpolations.jl just to support this case.

What should be possible, though, is to extend Interpolations.jl in a separate package; if you build something that has a similar API (e.g. extending the interpolate function with methods that take your own signalling types, and that return your own type deriving from AbstractInterpolation) you can probably piggy-back on many of the constructs in the package (like extrapolation and/or scaling) without having to have the implementation inside the package. (This is analogous to how Julia code outside of Base is not second-class to Julia code inside Base, so there is no real need to have everything in Base.)

[ghost]

Well that's just for 1D real signals, Discrete Fourier Transform based interpolation can be generalized to any class of discrete and multidimensionnal signals.

Intermediate points are evaluated by summing cardinal sinuses weighted by the initial and given samples. The DFT interpolation just make it easy to calculate this by padding the frequency domain of the signal and taking the inverse DFT.

It is really useful in image and audio processing when you know that your original signal ( or function ) is band limited and that the sampled version respect the Nyquist-Shanon theorem of sampling ( i.e that your original function has been sampled properly ). See this paper for example

Concerning the FFTW package, it is supported by Julia-Math, weigths 11 Mo when built, and needs the FFTW library. In comparison with Interpolations.jl it weights a lot for just this basic application and I understand that it is not useful right now.

I made a PR and tested the implementation, people can check it if they want to use DFT interpolation.

If the need for DFT interpolations grows It could be nice to consider what @tomasaschan proposed.

[ghost]

Wavelet based interpolation can also be considered, which is a nice way of approximating functions. Very useful if you know some stuff about the regularity of your function ( how the high order derivatives behave ).

[tomasaschan]

Given that FFTW.jl requires an external dependency, that's a big 👎 to including this in Interpolations.jl from me, unfortunately.

One of the main goals of this package from the start was to provide a Julia-native, performant and easy-to-work-with library for interpolation - if we don't care about the Julia-native part, we can just as well use one of the wrappers for any other C/Fortran library (there are several such wrapper packages already).

But, as noted above, this doesn't mean that functionality like this is not useful, or that it would not be nice to have it in a package. It also doesn't mean that it can't use the same interface as, or piggy-back on features implemented in, Interpolations.jl. I just oppose putting it in this package.

[ghost]

Sure !

Maybe I will make a topic on Julia's discourse for wavelet or Fourier based interpolation to see if people are interested in it.

[timholy]

One option is to use Requires. It used to do some shady tricks but it's very above-the-board in its modern implementation.

[danmackinlay]

Also ApproxFuns support Fourier-based approximations, although in a different setting to Interpolations.jl, in that they specifically recommend against interpolating.