Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [fast-fourier-transform]

Use this tag for questions related to the fast Fourier transform, an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. Those components are individual sinusoidal oscillations at distinct frequencies each with its own amplitude and phase.

An FFT algorithm computes the discrete Fourier transform (DFT) of a sequence or its inverse (IFFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. A FFT computes such transformations rapidly by factoring the DFT matrix into a product of sparse matrices. As a result, a FFT reduces the complexity of computing the DFT from $O(n^2)$ if one applies the definition of the DFT to $O(n\log n)$ where $n$ is the data size.

Fast Fourier transforms are widely used for many applications in engineering, science, and mathematics.

454 questions
6
votes
2 answers

Why are FFT results different from theory and how to eliminate the difference?

I am working with time series data, and applying FFT to calculate the power spectrum. The data is something like this: $y = \sum_{k=1}^{5} \cos(10 k x)$ All the peaks in the FFT output should have identical magnitudes, similar to the pattern shown…
Jihyun
  • 245
5
votes
3 answers

Imaginary Numbers and DFT

I'm not a math guy per se, but i am trying to understand the DFT. I get to the point where imaginary numbers are used with Euler's formula. What I don't understand is why we need an imaginary plane or "i" to begin with since we can plot any point…
mike628
  • 155
4
votes
0 answers

Is this FFT algorithm known?

Recently I've been thinking about alternatives to the usual Cooley-Tukey FFT for multiplying polynomials. I think I've come up with a pretty nifty algorithm for multiplying polynomials. So my question is, does anyone know if this FFT algorithm has…
Görre Mörre
  • 41
4
votes
1 answer

Basic question about fast Fourier transforms.

If I consider the function $\sin(t)$ evaluated between 0 and 60 (seconds) with $\Delta t = 0.01$. When I take the fast Fourier transform, the frequency of oscillations can be obtained directly of $$f = \frac{(\text{Position of the first peak} - 1…
F.Mark
  • 177
3
votes
2 answers

dimension after fast fourier transform

I am doing a frequency analysis. Reading some literature I have seen that when you perform an fft on a time history of a variable, the dimension of this variable remains the same also after the application of the fft. In particular, in my case study…
luca.mirtanini
  • 31
2
votes
1 answer

differences between some concepts of Number Theoretic Transform (NTT)

I'm researching on different variants of Number Theoretic Transform (NTT) and some concepts just got me confused. What's the difference between Cooley-Tukey transform and Gentleman-Sande transform? My understanding is that both CT and GS transform…
Daisy Ding
  • 53
2
votes
2 answers

scaling magnitude of the dft

I have seen a lot of question like this, but still I have doubts about the answer. When using the fft in matlab the solution need to be divided by the length of the signal (N). I have seen many answers that say that there are at least 3 type of…
Luca Mirtanini
  • 131
2
votes
0 answers

Any Efficient Multiplication with a Primitive Root over Prime Field?

Description: to multiply the "complex unit" $w^{N/4}$ over a prime field, i.e., $w^N \equiv 1 \bmod (\,p)$ (suppose $p, N$ do provide such primitive root). I am implementing the radix-4 Number Theoretic Transform which involves the multiplications…
Fionser
  • 21
2
votes
0 answers

Increasing frequency resolution of FFT on a windowed sample of a signal

Okay, this gets a bit technical, let me explain the background. In doing loudspeaker measurements for its direct sound in normal rooms that have reflections, what we do is measure the whole impulse response of the system, including room reflections.…
soulblast
  • 21
2
votes
4 answers

Intuition of fft over time to frequency

I understand how FFT (DFT) works. It acts as a change of basis. However, while many websites describe fft as a method that convert time domain stuff to frequency domain stuff, I still do not know why it transforms a vector in time domain to one in…
mallea
  • 829
1
vote
0 answers

The units of spatial frequency of fft

We are performing fft on N samples of a function f(x) that is periodic on the interval [0,L] where x is in meters. What would be the most common definition of the units of the domain of the transformed signal ? Will it be cycles per meter or…
Tomer
  • 434
1
vote
0 answers

Frequency ranges of the even and odd term of DFT while developing a FFT algorithm

I'm reading this book: "Theory and application of digital signal processing" by Lawrence R. Rabiner and Bernard Gold. During the development of the classical matrix refactorization used to build a FFT algorithm: Where: $W^{nk} = e^{-2\pi j nk/N}$ ;…
Sam
  • 11
1
vote
0 answers

Time complexity of divide and conquer to multiply $n$ linear polynomials using FFT

I know that the time complexity is $$O\left(\sum^{\log_2n}_{k=0}O\left( n\log_2\left(\frac{n}{2^{k}}\right) \right)\right) = O\left( O\left( n(\log_2n)^2 \right) - \sum^{\log_2n}_{k=0}O\left( nk \right)\right)$$ Unfortunately, operations with big O…
Wei Bin Ang
  • 21
1
vote
1 answer

Function $f$ with $\hat{f}=0$

Is there a function $0\neq f\in L^1(\mathbb R^d) $ with $\hat{f}=0$?
Robert
  • 414
1
vote
1 answer

Why does splitting a polynomial into even and odd degree terms results in polynomials taking as input $x^2$?

The question came up under comments to this YT presentation on FFT as a point taken as self evident, and Math SE seems like a natural place to answer it. The idea is to evaluate a polynomial of degree $n$ at $\pm x_1, \pm x_2, \dots, \pm x_{n/2}$…
Antoni Parellada
  • 8,889
1
2 3 4