I have a very high dimensional signal, say $15$ dimensions. Across each dimension the width is $N$ points. So total number of points is $N^{15}$. I already have the FFT given to me. Only low frequency coeffs are non zero. The non zero coeffs are the ones inside of the hypercube of width 5. So only $5^{15}$ are non zero.

Now I want to take an IFFT to compute samples in signal domain.But I dont want to compute all samples of signalbut only a $k$ of them. $k$ is much smaller compared to $N^{15}$. The samplesin signal domain are by no means sparse, but its just that I want to compute only a small number $k$ of them. These $k$ samples are distributed arbitrarily and are not confined to any region. How can I compute them efficiently?

I came across Sparse FFT, but here my signal is not sparse but just that i am interested only in a few samples in signal domain. So I am not sure I can use SFFT.

PS : I don't want to take a full IFFT due to memory constraints.

  • 1
    $\begingroup$ The sparse FFT isn't really applicable here- it's an algorithm for locating the small number of frequencies with non-zero coefficients, in a single that is sparse in the frequency domain, but your signal is dense in the frequency domain and you already know where you want to compute the IFFT. If $k$ is small enough, then you could do this by direct evaluation of the IFFT sum. It's still going to take $O(kN^{15})$ time to do this, because all of your coefficients in the frequency domain are potentially nonzero. $\endgroup$ – Brian Borchers Nov 5 '17 at 16:50
  • $\begingroup$ @Brian not all coffs in frequency are non zero but only 5^15 low frequencies. So in this case i cant better than O(k5^15)? Can i use Gortzel algorithm to get any better? $\endgroup$ – Rajesh D Nov 5 '17 at 22:27
  • 2
    $\begingroup$ If you know exactly which of the Fourier coefficients are nonzero than you can just sum over those terms in the inverse Fourier transform. $\endgroup$ – Brian Borchers Nov 6 '17 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.