3
$\begingroup$

I'm trying to find an efficient way to compute maximum of a signal using its DFT. More formally:

$$\max\left\{ \mathcal F^{-1}\left(X_k\right)\right\}, X_k\text{ is the DFT of the signal and } \mathcal F^{-1} \text{ is the IDFT}$$

The original signal $x(n)$ is real, and it has some noise when sometimes there are wide peaks.

I'm looking for a solution that is quicker than the actual IFFT since the signal is very long (but we have its DFT).

$\endgroup$
  • 1
    $\begingroup$ So, wait, are you looking for its maximum in time or in frequency domain? Can you please define what $F$ and $X$ are? $\endgroup$ – Marcus Müller Mar 27 '17 at 12:15
  • $\begingroup$ so, am I understanding this correctly, you only have the DFT of your signal, but not the original signal? If so, does the signal or its DFT have any special properties (real-valuedness, symmetry, that kind of thing)? what constitutes a maximum? Maximum magnitude? Maximum Real Part? $\endgroup$ – Marcus Müller Mar 27 '17 at 12:24
  • 1
    $\begingroup$ By the way, what is "very long"? Maybe you'd want to also tell us a bit about your computing platform, because things will be different for implementation on ASIC/FPGA/GPU/CPU with SIMD/MCU… Also, it tends to be a good idea to explain where your constraint comes from (is it latency, memory or computational throughput, power consumption?) $\endgroup$ – Marcus Müller Mar 27 '17 at 12:38
  • $\begingroup$ Would you be satisfied with an estimate of the rms level or do you really need to be concerned with the value of an occasional "spike"? $\endgroup$ – Dan Boschen Mar 27 '17 at 23:33
  • 1
    $\begingroup$ Related: dsp.stackexchange.com/q/34936/21075 $\endgroup$ – Rodrigo de Azevedo Mar 29 '17 at 11:17
5
$\begingroup$

This sounds like a good candidate for the Sparse Fast Fourier Transform (sFFT). Have a look at H. Hassanieh, P. Indyk, D. Katabi, and E. Price, sFFT: Sparse Fast Fourier Transform, 2012. I don't know details of the algorithm. You have the domains swapped, which should be fine as the discrete Fourier transform (DFT) and its inverse (IDFT) are nearly identical.

sFFT has been discussed also here on dsp.stackexchange.com.

$\endgroup$
  • $\begingroup$ Actually I think that as is it won't help much, but there is potential for something in the theory that could help me, thanks! $\endgroup$ – Cherny Mar 27 '17 at 12:48
  • $\begingroup$ I'm sorry I ever doubted you, this actually looks very fitting! thanks a lot! $\endgroup$ – Cherny Mar 27 '17 at 13:16
3
$\begingroup$

There is no way to compute the (exact) maximum of the time domain signal directly from its DFT (without doing an IDFT first). Without any further knowledge, the best you can do is

$$|x[n]|=\left|\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j2\pi nk/N}\right|\le\frac{1}{N}\sum_{k=0}^{N-1}|X[k]| $$

which gives you an upper bound. However, this upper bound is usually not very tight, especially for large values of the DFT length $N$.

$\endgroup$
  • $\begingroup$ Yes, this becomes an equality for any $n$ for which $X[k]$ has for all $k$ the same phase as the complex conjugate of $e^{j2\pi n k/N}.$ $\endgroup$ – Olli Niemitalo Apr 18 '17 at 13:26
1
$\begingroup$

Generally:

There can be no shortcut here – every single element of the (inverse or forward, doesn't matter) DFT needs every element of the input. So, the FFT is already pretty much as fast as you can go.

However, you say:

The original signal $x(n)$ is real, and it has some noise when sometimes there are wide peaks.

Aha! That means that your $X$ is (hermitian) symmetric. Which means you might be able to pick an FFT algorithm that benefits from that knowledge and can omit quite a few calculation – but I don't think that'll change the general $\mathcal O(N \log N)$ complexity of the IFFT, nor the $\mathcal O(N)$ of finding the maximum.

$\endgroup$
  • $\begingroup$ I actually thought the more important part is the wide peaks part, because I thought of using something like the sparse cognitive radio, but yea this helps too, thanks! $\endgroup$ – Cherny Mar 27 '17 at 12:47
  • $\begingroup$ well, sparsity is something you can exploit when you know a lot about the number of base vectors you'd need to have to represent your signal. You didn't say anything about the number of your "wide peaks" (which by the way is pretty non-descriptive) nor about how long your vectors are. $\endgroup$ – Marcus Müller Mar 27 '17 at 13:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.