# Non-uniform FFT

I'm looking for a form of a FFT where the samples in the frequency-domain don't represent uniform spaced frequencies. What I would like to get is a frequency-domain with samples that are unevenly spaced, so that e.g. I get a higher resolution at lower frequencies and coarser resolution at higher frequencies.

1. What algorithms come into play?
2. Are they as computational effective as the FFT? (e.g. precomputed factors).
• Check out the nufft in Matlab. It has the ability to handle non-uniformly spaced data in time and frequency. It typically handles this through interpolation. Commented Apr 3 at 14:55
• some more discussion on this question by this author but on SO: stackoverflow.com/questions/78267390/non-uniform-fft Commented Apr 3 at 15:57
• so, you're looking for something, but not a "form of an FFT", it seems. Commented Apr 3 at 16:53

This is a common problem, but the best choice depends a lot on your requirements: Do you need amplitude, phase, or both, do you want to do frequency domain processing, does the transform needs to be information preserving and/or invertible, do you need to smooth to combine the "low density" frequency areas, etc?

What algorithms come into play?

Constant Q transform, wavelets, cascaded half-band filters, third (or 1/N) octave band analyzers, etc.

Are they as computational effective as the FFT?

Generally not. Many of these algorithms use internally an FFT (or related transform) and then employ a post processing step to recalculate whatever you want to calculate.

EDIT based on comments:

finding the frequency with the greatest amplitude can be based on uniform or non-uniform spaced frequencies

That is NOT straight forward. Numerical spectral analysis will typically return a metric of spectral density of a certain "band" that has a center frequency and a bandwidth, not the "amplitude at a single frequency" which is tricky to define.

If you have non uniform frequency grid, the bandwidth varies with frequency and drawing any conclusion about a single frequency becomes difficult.

Let's look at a simple example: a 3rd octave band analyzer (which is a standard spectral analysis tool for audio). The center frequencies are logarithmically spaced but the bandwidth of each bin is a third of an octave (i.e.$$f_c \cdot 2^{1/3}$$, where $$f_c$$ is the center frequency of each band).

If you feed this with a white signal (equal energy at all frequencies), the result will NOT be constant, but you'll see a rise with frequency. The highest frequency has the highest value since it has the widest bandwidth.

If you feed it with a pink signal, where the amplitude at each frequency is proportional to $$1\f$$, the result will be flat.

So in summary, the concept of "single frequency with greatest amplitude" depends a lot on how exactly you define it and for any given signal you can get different results depending on the method and design parameters. There is no "right" or "wrong" here, it's a matter of giving an precise definition of what exactly you want.

• The goal is simply to find the frequency component with the greatest amplitude. No frequency domain processing, and it does not have to be invertible. We just want a better resolution to lower frequencies, and that with minimal computational requirements. Commented Apr 3 at 12:16
• Can you define "better resolution"? What exactly do you need. Zero padding before FFT is still reasonably efficient (compared to the other options). Can you restrict the frequency band you are searching ? Commented Apr 3 at 14:06
• sounds to me like OP does have uniformly spaced time domain samples, but wants to calculate the fourier transform for a selected set of frequencies that is spaced closer together for low frequencies (as opposed to a DFT that spaces them equally). perhaps there's something with logarithmic/exponential spacing? probably :P Commented Apr 3 at 16:01
• Sorry for the wrong wording in the question. Corrected! Commented Apr 3 at 16:13
• Kind of logrithmic placed frequencies would be good. A factor of 1:10 over the full range from 0 to fs/2 would be ok. Commented Apr 3 at 16:16