2
$\begingroup$

I'm working in circuits fields and I am not very familiar with spectrum sensing techniques.

Is there a method to identify location of non-zero Fourier coefficients of a signal (just locations, not values) with minimum computational cost (less that computations of FFT)?

Suppose my signal is a vector of length $N$ associated with some white noise.Suppose the demanded frequency accuracy is $$\frac{f_\text{sample}}{10N}$$

and imagine my signal is a 1000 samples of a signal and we have quantized this signal through a low resolution ADC. And signal is sparse in frequency domain, meaning that and only a fraction of its DFT coefficients are non-zero (like less than 10% of coefficents). Currently I am using a method called Periodogram which is based on FFT.

Other than FFT, do you think using multiple band-pass filters work? I was thinking to Band-pass filter, but it seems to be more computationally costly. I mean I can pass the signal through multiple band-pass (like 100) filters which altogether cover the whole spectrum and then measure the energy of the each frequency portion of the signal?

Improve this question
$\endgroup$
15
  • $\begingroup$ FFT has complexity $\mathcal O (N\log N)$, and a abs maximum search is linear, i.e. $\mathcal O(N)$. I don't think you'll get away with less computation for the same accuracy, which is $\frac{f_\text{sample}}N$. But: usually, people just use an accuracy they don't need. What frequency resolution do you need? $\endgroup$
    – Marcus Müller
    Jul 21 '16 at 8:55
  • $\begingroup$ First, thanks for the comment. You mean using a FFT with fewer frequency bins and hence faster computations. Actually I think it is a good idea, I can do it in less frequency resolution. I'll keep this in my mind, however I'm seeking even more efficient method. I encountered Sparse Fast Fourier Transform (sFFT) link , it seems they are using a spectrum estimation prior to calculating FFT to boost the performance of the FFT but I can't figure out their method and try to find something similar. $\endgroup$
    – MimSaad
    Jul 21 '16 at 9:53
  • $\begingroup$ The Problem usually really is that the less samples you use to get the same resolution/variance, the more complex your algorithm tends to be computationally. Really, define your frequency resolution demand first, then define computational limits. I really don't think you're solving the right problem - could you give us a bigger picture of what you know about your signal? There's cases where parametric spectrum estimators might actually become computationally easier, but these are very special cases and not in general equivalent to finding the max dft bin. $\endgroup$
    – Marcus Müller
    Jul 21 '16 at 12:50
  • 1
    $\begingroup$ What does "is sparse in frequency" domain actually imply? Do you know it's only a discrete number of tones? How many? $\endgroup$
    – Marcus Müller
    Jul 29 '16 at 19:09
  • 1
    $\begingroup$ Again, please add this kind of info to the question $\endgroup$
    – Marcus Müller
    Jul 29 '16 at 19:22
1
$\begingroup$

Is there a method to identify location of non-zero Fourier coefficients of a signal (just locations, not values) with minimum computational cost (less that computations of FFT)?

So, first of all, computation of FFT:

Remember, the $10N$-point FFT, which you need for the resolution you demand:

Suppose my signal is a vector of length $N$ associated with some white noise.Suppose the demanded frequency accuracy is $$\frac{f_\text{sample}}{10N}$$

has complexity of $\mathcal O\left(10N\log(10N)\right)$.

You've got a sparsity of ca. $\frac1{20}$:

comment clarify I give an example, imagin we have signal with lengh of 1000 or 2000. We take its DFT and there are less than 50 coefficient non-zero.

which means that it's not that sparse, and all algorithms exploiting sparsity by throwing linear algebra at the problem can't really benefit much from the situation; a $K$/$L$-rank matrix/matrix operation typically has best-case complexity $K\cdot L$, so considering $K=N$ this can only work out¹ in the favour of the sparse operation if $L<10\log(10N)$. Now you gave $N\approx 1000$, and let's chose a very modest logarithm base here – $\log_{10}$ – so, you'd end up with the condition $L < 10\log_{10} 10000 = 40$, and as you can see, with $L\approx 50$, this is not generally the case – this can really only work out if your sparsity-exploiting "tone finder" is very, very, very efficient.

But, you'll say, there's superefficient parametric estimators such as ESPRIT, that can get a much higher resolution with less samples!

Yes, that's what I'd have suggested in your situation, in general, too, but you've got to realize that these subspace/Eigenvalue based approaches work on a autocorrelation signal model – i.e. they need an estimate of the auto-correlation-matrix, which you typically get by calculating the dyadic product of the $N$-sample vector – a operation with complexity $\frac 12 N^2$, i.e. much much more than the complexity of the FFT.

So, to answer your question: No, there's to my knowledge no estimator with lower computational cost, but there's more mathematically efficient estimators than the DFT; however, you might actually get a $\frac1{10}$ resolution with less than $N$ samples, but really, you need to have a rank of your matrix estimate sufficiently higher than the number of tones you're looking for, so I'm afraid this won't change that much.

¹ I'm well aware that's not really how Landau symbols work. However, FFT implementations are really highly optimized, and so is LAPack, and thus, my gut feeling says I can really use the complexity limits as "constants".

Improve this answer
$\endgroup$

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.