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.

Filter by
Sorted by
Tagged with
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. ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
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+\...
user avatar
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_{...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $|\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. (...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 (...
user avatar
  • 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)...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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}...
user avatar
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-...
user avatar
  • 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^{\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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^{'} \...
user avatar
-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 ...
user avatar
  • 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 &...
user avatar
  • 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}...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
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} \...
user avatar
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 ...
user avatar
  • 23

1
2 3 4 5
8