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.
396
questions
0
votes
0
answers
12
views
Intuition for performing a Fourier Transform on a multidimensional Array
I am currently working on a Software that simulates the behaviour of metals on a microscopic scale for a given set of time intervals in consideration of different stresses and external circumstances. ...
- 101
0
votes
0
answers
25
views
Fourier Transform With Weighted Kernel
I am working on a spectral problem and trying to perform a numerical calculation involving an integral of this form
$$\int_{\mathbb{R}}dx f(x,k)e^{-ixk} $$
I am sort of interpreting this as a Fourier ...
- 403
0
votes
1
answer
44
views
Discrete Fourier Transform, even and odd components
Let $v = [v_0, v_1, \dots, v_{n−1}]^T$ is the Discrete Fourier Transformation, $V = [V_0, \dots, V_{n-1}]^T $. Define $w = [w_0, w_1, \dots, w_{2n−1}]^T$ where $v_k =w_k$ for $0 \leq k \leq n−1$ and $...
- 1
1
vote
1
answer
47
views
Relationship between a vector and its discrete fourier transform
Suppose we have a real vector $a=(a_0,\ldots,a_{n-1})$ and let $b=(b_0,\ldots,b_{n-1})$ be its discrete fourier trasnform. So $$\mathscr{F}(a_k)=b_k=\sum_{i=0}^{n-1}{a_i}e^{\frac{-j2\pi i k}{n}}$$Let $...
- 615
0
votes
1
answer
77
views
How to compute the Fourier transform of a zero-centered Gaussian pulse over a specified range, say $[0,1]$?
Given an even Gaussian kernel $f : \Bbb R \to \Bbb R^+$
$$f(x) = \exp \left(- \frac{1}{2\sigma^2} x^2 \right)$$
and a probability density function (or, if you discretize $[0,1]$, then a probability ...
- 703
0
votes
0
answers
20
views
Fourier transform of exponentially modified gaussian
So i have to calculate the fourier transform of an exponentially modified gaussian $$f(x, A, \lambda, \mu, \sigma)=\frac{A\lambda}{2}e^{\frac{\lambda}{2}(2\mu+\lambda\sigma^2-2x)}erfc(\frac{\mu+\...
0
votes
1
answer
40
views
Propagating error through a Fast Fourier transform
I am trying to propagate the error associated with a Fast Fourier transform of $x_{n}$. I know the error (variance) for $x_{n}$. Then, I calculated the following quantity:
$$Y=Im\left ( i\omega FFT(x_{...
- 1
2
votes
1
answer
60
views
FFT stride pattern formula
Edit
I have found a solution and I posted it below. Thanks to everyone who tried to help!
Question
I have implemented the radix-2 DIT FFT algorithm but I could not find a formula to determine the ...
- 141
0
votes
0
answers
20
views
How can the Cooley-Tukey algorithm for multiplying polynomials be implemented without approximations?
I view the main idea behind the Cooley-Tukey algorithm as follows. Suppose we have two $n$-degree polynomials (with coefficients in $\mathbb{Z}$). We will
Evaluate the polynomials on the $2n + 1$ ...
- 2,274
0
votes
0
answers
44
views
FFT ELI5 - I mostly get it, but not quite - is my understanding of frames/windows off?
tl/dr: I've got two audio recordings of the same song without timestamps, and I'd like to align them. I believe FFT is the way to go, but while I've got a long way, it feels like I'm right on the ...
- 137
0
votes
1
answer
23
views
Finding the second derivative using DFT
Suppose you have an even real-valued function f(x), which is periodic with T=2L. Introducing a grid
$$x[n]=-L+ndx,\quad f(x[n])\equiv f_n,$$
$$dx=\frac{2L}{N},\quad n=0,\ldots N-1,$$
its DFT is ...
- 33
0
votes
1
answer
33
views
Fourier transform of $f(x)=\frac{1}{1+|x|^n}$ and $f(t)=\frac{1}{\left(1+|x|\right)^n}$ where $n>0$
I was looking for the FT of the symmetric functions:
$f(x)=\frac{1}{1+|x|^n}$ and/or
$f(x)=\frac{1}{\left(1+|x|\right)^n}$
where $n>0$. Here $-\infty \leq x \leq \infty$. I expect the FT to be ...
- 69
0
votes
0
answers
25
views
Why does Fourier transform gives the correct amplitudes?
For instance we would like to get the Fourier transform of $A\cdot cos(2\pi fx)$. At some point, when we find the frequency $f$, we arrive to the following integral.
$$\int_{-T}^{T}A\cdot cos^2(2\pi ...
0
votes
0
answers
20
views
DFT, but with large values available
Suppose that we are calculating a size $N$ integer-valued DFT, with some values possibly adjoined to the integers, such as the imaginary $i$. My question is, if the word size allows integers much ...
0
votes
1
answer
64
views
Fourier transform of $|t|^{-n}$
I am struggling with this although the question is partially answered a few times before. Here $-\infty < t <\infty$ and I am only interested in $0\leq n \leq 2$. Mathematica gives the FT as $|\...
- 69
2
votes
0
answers
68
views
Fast Multiplication of matrix and vector
Multiplication of the DFT matrix and any vector can be implemented by FFT.
I'm interesting about other fast Multiplication.
Suppose there are three matrix of size $N\times N$, $F$ , $Q$ and $P$, where ...
- 21
2
votes
0
answers
22
views
FFT energy calculation by frequency
For a FFT result in frequencies $k$ and associated amplitude magnitude $A(k)$ it is possible to calculate the signal energy by:
$E=\sum_{k=1}^{N} A(k)^2 $
However, what does it mean when the energy ...
- 21
0
votes
0
answers
7
views
Why these operations calculates group delay?
In textbook, group delay is defined as negative derivative of phase (in frequency domain). And in discrete signal, derivative can be approximately calculated as differentiation. But when I browse some ...
- 115
0
votes
0
answers
26
views
Multiply polynomials using DFT algorithm
I am a computer science student, I am studying the Algorithms course independently.
During the course I saw this question:
Multiply the polynomials 1 − 4x − 3x^2 and 2 − 5x using the DFT algorithm.
(...
- 101
0
votes
0
answers
39
views
How to make conceptual sense of the Fourier transform?
I am trying to calculate and understand the fft of the following signal:
Here's what I get for the amplitude of the fft, plotted on a log-log scale:
Does this make sense? I think of the big changes ...
- 169
0
votes
1
answer
47
views
Consistency in definition of Fast Fourier Transform
The book Numerical Analysis by Faires defines the fft of a signal $y_{j}$ as
$$a_{k}+ib_{k}=\frac{(-1)^{k}}{m}c_{k}$$
where
$$c_{k}=\sum_{j=0}^{2m-1}y_{j}e^{ik\pi j/m}$$
for each $k=0,1,...,2m-1$. How ...
- 169
2
votes
1
answer
32
views
Constraining input to an inverse Fourier transform to give real-only output
I am trying to generate a complex 2D field in Fourier space that will give a real-only output when computing the 2D inverse Fourier transform. Is there a way to specifically set some constraint on the ...
- 33
1
vote
0
answers
16
views
Finding the resolution of the discrete Fourier transform of an image
Suppose I have a 2d function defined on a square of length $L$, that is given as an $N \times N$ matrix of values.
The resolution to which we know the function is $\delta L = L/N$. We may take the (...
- 433
0
votes
0
answers
19
views
Radial function of absolute value of 3d FFT data
I have a 3d data set $f(x,y,z)$ from $[-x_{max}, x_{max}]$, $[-y_{max}, y_{max}]$ and $[-z_{max}, z_{max}]$, and I need to calculate the radial function $g(q)$ where $g(Q_x, Q_y, Q_z)=|f(Q_x, Q_y, Q_z)...
- 1
2
votes
1
answer
36
views
Does it make sense to use a FFT to describe a time series of "spikes"?
I will preface this by saying I'm not a mathematician, so apologies if I use terminology incorrectly.
Say I have a time series that looks something like this:
Specifically, the signal is usually zero ...
- 169
1
vote
0
answers
28
views
Accurate way to calculate convolution integrals in arbitrary grids
The convolution integral is defined by:
\begin{eqnarray}
(f*g)(y)=\int_{-\infty}^{+\infty}dx f(x)g(y-x).
\end{eqnarray}
Moreover, assume both $\lim_{x\to \pm \infty} f(x),g(x)=0$. Now, suppose we have ...
- 373
0
votes
0
answers
23
views
Non-uniform Uniform Discrete Fourier Transform
I am working with a simulated diffraction pattern (so in 2D Fourier space), and I'd like to take an inverse transform of this and get back to real space. The problem is that, while the points are ...
0
votes
1
answer
34
views
Is the Fast Fourier Transform associative?
For multiplying 2 polynomials, we can use the FFT:
$$IFFT(FFT(p(x)).FFT(q(x))) = p(x)*q(x)$$
Can I do
$$IFFT(FFT(p(x)).FFT(q(x)).FFT(r(x))) = p(x)*q(x)*r(x)$$
?
Where $.$ is coefficient-wise ...
- 5,776
0
votes
0
answers
16
views
How does the Fast Fourier Transform label the frequency spectrum?
Let us consider a function $f$ defined on the torus $\mathbb{T}^2$, i.e. the domain $[0,1)^2\subset\mathbb{R}^2$ with periodic boundary conditions. The homogenous negative Sobolev norm $\dot{H}^{-1}$ ...
- 410
0
votes
0
answers
37
views
How to Derive the Discrete Fourier Transform from the Fourier Transform
First, this is the Fourier transform formula：
$F(k)=\int_{-\infty}^{\infty}f(x)e^{-ikx}dx$
and this is Discrete Fourier transform formula：
$F(k) = \sum_{x=0}^{N-1} f(x)e^{-i2\pi xk/N} $
Why does N ...
1
vote
0
answers
39
views
2D Fourier transform of $e^{-a(\textbf{r}-\textbf{r}')}/| \textbf{r}-\textbf{r}'| $
I have the following function
\begin{equation}
f(\textbf{r}-\textbf{r}')=\frac{e^{-a|\textbf{r}-\textbf{r}'|}}{|\textbf{r}-\textbf{r}'|},
\end{equation}
with $\textbf{r}=(x,y,z)$ and $a>0$. Now I ...
- 305
1
vote
0
answers
19
views
Functions with equivalent Fourier coefficients
Given two functions $f(x),g(x)$ defined over $\mathbb{R}$, satisfying $f(x+P)=f(x)$ and $g(x+P)=g(x)$ for $P\in\mathbb{R}$, consider their Fourier transformation:
\begin{eqnarray}
\tilde{f}(k)=\frac{1}...
- 373
0
votes
0
answers
14
views
Back-calculating the octaves of 2D Perlin Noise
I am working with 2-dimensional fractal Perlin noise, and I am trying to find a way to back-calculate the octaves that were summed together.
What I would like to do is, given a particular 2-...
- 1
0
votes
0
answers
14
views
second derivative of log convolution
Let $h(x)$ be a one-dimensional function. Let $h^{\ast n} = h \ast h \ast \dots \ast h$, convolution of n $h$.
I know that $(h \ast h)' = h' \ast h$. But what I am actually interested in is $(\log h^{\...
- 1
0
votes
0
answers
26
views
Relationship between polynomial division and element-wise division in frequency domain
Given two polynomial coeffcient $a, b \in \mathbb{R}^d_{+}$, If $c = a \star b$, then $\text{fft}(c) / \text{fft}(a) = \text{fft}(b)$. Here $\star$ is polynomial multiplication, fft is the fast ...
- 1,113
1
vote
0
answers
48
views
Convolution integral over non-uniform grids
Statement of the problem:
The convolution of two functions is defined by:
\begin{eqnarray}
(f*g)(y)=\int_{-\infty}^{+\infty}dx f(x)g(y-x),
\end{eqnarray}
for functions $f(x),g(x)$ defined over the ...
- 373
0
votes
0
answers
8
views
Find index maps for a prime factor FFT knowing $N_1$ and $N_2$
This question from Digital Proccessing Signals (Schaum series):
Find the index maps for a 99-point prime factor FFT with $N_1 = 11$ and $N_2 = 9$
Solution manual says:
For N = 11
$N_1N_1^{'} \...
-1
votes
1
answer
30
views
How to sum a function using its DFT?
I have a function $f(x_n)$ defined over $n$ points, which is initially unknown, but its DFT is known as $F(k_n)$. However, I need to compute $\sum_n f(x_n)$ from the DFT. How to accomplish this ...
- 167
2
votes
3
answers
165
views
Solving Ax=b by FFT
I read in Wiki that it is possible to solve Ax=b via Fast Fourier Transform given that A is a circulant matrix. For example, I have $\begin{bmatrix}
1 & 0 & 0 & -1 \\
-1 & 1 & 0 &...
- 97
2
votes
0
answers
22
views
Convolution of zero-padded DFT
I have a signal
$$x[0, \ldots , 2^n-1].$$ I would like to compute its DFT$$f[0, \ldots , 2^n-1],$$ take the first half $$f[0, \ldots , 2^{n-1}-1],$$ pad it with zeros,
$$g[i] = \left\{\begin{array}{cc}...
- 848
1
vote
0
answers
20
views
What is the relation between the input and output coordinates of a Discrete Fourier Transform?
So take a 2D DFT for example:
$$F(k,l)=\frac{1}{MN}\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}{f(m,n)e^{-2\pi{i}(\frac{k}{M}m+\frac{l}{N}n)}}$$
Practically, this just means that we take a pre-set matrix of ...
- 11
0
votes
0
answers
10
views
FFT result relationship when padding with different amount of zeros?
Suppose I have a list a=[1,2,3,4] and have already calculated its DFT: fft(a)=[10.+0.j, -2.+2.j, -2.+0.j, -2.-2.j].
Now I'd like ...
- 101
1
vote
1
answer
101
views
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 ...
- 7,835
0
votes
0
answers
30
views
How to inverse magnitude and phase Fourier signal
Assume that my measurement equipment returns magnitude and phase of some signal in frequency domain. How to inverse this frequency, magnitude and phase described signal to time domain signal (e.g. in ...
- 23
3
votes
0
answers
65
views
Factorization in Fast Fourier Transform
I am trying to understand the FFT using matrix factorization, and there is just one step that I am unclear about. I took a look at this quesetion (Fast Fourier Transform as Matrix Factorization) but ...
- 1,402
2
votes
0
answers
93
views
Binary polynomial evaluation
Let $p(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ be a polynomial in $\mathbb{Z}_p[x]$ with binary coefficients, i.e., such that $a_i \in \{0,1\}$ for all $i = 0,1,\dots,n-1$. I like to refer ...
- 259
1
vote
0
answers
13
views
Extreme sensitivity to the input scale of a Continuous Fourier Transform approximation from Discrete Fourier Transform
Is there a way to 'bypass' the condition $\Delta k=\frac{1}{x_{max}-x_{min}}$, which requires the range of $x$ to be very large when approximating the CFT as a DFT?
To contextualise my question:
...
- 897
0
votes
0
answers
52
views
2D Fourier transform of periodic structure showing frequencies lower than fundamental frequencies
Is there a possibility that there appears a maxima in the fourier space (in the absolute value of the transform) of a purely periodic structure. I was of the impression that purely periodic structures ...
- 525
0
votes
0
answers
24
views
phase of Fourier transform when arrives at $ \pi $
I'm trying to calculate Phase of "rect" which is like below
\begin{equation}
f(x)=\begin{cases}
1, & \text{if $256<x<768$}.\\
0, & \text{otherwise}.
\end{cases}
\...
0
votes
0
answers
23
views
Is $\mathit{O}(n\log_2n)$ the same as $\mathit{O}(n + \frac n2 log_2n)$
i was looking into the FFT and watching the wonderful Videos of Prof. Strang's MIT 18.06 Linear Algebra Series and came upon Vid.26 where at the end (43 min mark) the time complexity of the FFT in ...
- 23