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.
5
votes
3answers
51 views
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 ...
3
votes
2answers
46 views
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 ...
1
vote
0answers
18 views
How to interpolate under specific conditions using FFT?
I am solving a very specific problem where I need to apply FFT to interpolate. I am given two sets of distinct points $A = (a_{1}, a_{2}, ... , a_{n})$ and $B = (b_{1}, b_{2}, ..., b_{n})$. Using $B$, ...
0
votes
0answers
24 views
Linear deconvolution using FFT
I want to deconvolve a filtered signal with a known input to recover the filter used using FFTs.
Let $x$ be a vector of length $N$ and $h$ a filter of length $K$ where $N > K$.
Let $x \ast h = y$,...
2
votes
1answer
41 views
FFT from scilab is different than wolfram alpha [closed]
I am getting completely different values of FFT([1,2]) in scilab and Wolfram. I wondering what is going on and who is right.
...
0
votes
0answers
11 views
Analytical expression for PSD
Is it possible to obtain an analytical expression for the PSD?
The PSD is defined as follows,
$S(\omega) = lim_{T \rightarrow \infty} \frac{1}{T} |Y(\omega)|^2 $
Assuming there is $Y(\omega)$ ...
0
votes
0answers
10 views
Unexpected results for Fourier synthesis using IFFT in 2D
I am trying to recover a 2D function using inverse DFT, to my understanding the IDFT outputs the coefficients of the fourier series of the original function up to the Nyquist frequency.
So for ...
2
votes
0answers
46 views
DFT is not a sampling of FT?
From wikipedia:
The discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time ...
0
votes
1answer
29 views
even/odd signals and their FFT
I want to use the following property of the Fourier transform:
Even functions have even transforms; odd functions have odd transforms.
in mathematical terms:
if $f(t)$ is a function that has an ...
0
votes
1answer
25 views
How does matrix vector multiplication scale a norm of vector?
Given a square Vandermonde matrix
$\mathbf{V} =$\begin{pmatrix}
1 & x_0 & x_0^2 & \ldots x_0^{n-1}\\
1 & x_1 & x_1^2 & \ldots x_1^{n-1}\\
\vdots\\
1 & x_{n-1} & x_{n-1}...
0
votes
0answers
35 views
Circulant matrix-vector product procedure
A circulant matrix $C$ can be represented as
$$C = F^{-1} \mbox{diag}(Fc) \, F$$
When $C$ is multiplied by vector $b$
$$C b = F^{-1} \mbox{diag}(Fc) \, (F b)$$
My question only about procedure. ...
0
votes
1answer
38 views
Applying Fourier transform to represent equation with integral as a sum of variables
According to a paper the equation with integral
$\int_{-\infty}^{\infty}dx \rho_0(\lambda)e^{-b\lambda}=1/N$ (#1) where
$\rho_0(\lambda)$ is a distribution function, $N$ is a natural number, can be ...
1
vote
0answers
23 views
Is it possible to use FFT to derive a Fourier series fitting to data?
I want to do something like what is done in this question about fitting , ie find a Fourier series that approximates a continuous but complicated function. However I want to know whether it is ...
1
vote
1answer
31 views
Question about the FFT version of the gradient of a function.
We know that for a sufficiently smooth function $f:\mathbb{R}^{3}\to\mathbb{R}$, its Fourier Transform $\hat{f}(\mathbf{k}) \colon= \mathcal{F}\{f\}$ should satisfy (using integration by parts):
$$\...
0
votes
1answer
22 views
order of accuracy for numerically evaluating $u''(x) +u'(x) +u(x) = e^{-x^2}$ with regard to grid resolution
I was asked (an homework assignment) to apply FFT in order to approximate a solution for the ODE $u''(x) + u'(x) + u(x) = e^{-x^2}$ such that $u(x)$ satisfies the conditions: $u(\pi) = u(-\pi) , u'(\...
0
votes
0answers
9 views
How to convert X,Y Cartesian data to 3D spectrum (frequency, direction, spectral density)?
My question is as follows. I have x,y motion. normally I would ignore directionality and just look at the spectral density of each by performing a FFT on it. For my current problem directionality is ...
0
votes
0answers
17 views
Multiplying Many-Variable Polynomials Using Fast Fourier Transforms
I'm having some trouble figuring out how to use Fast Fourier Transforms to multiply multivariate polynomials. I'm writing a program that intended to expand a large polynomial made of lots of small ...
0
votes
1answer
34 views
Comparability of Analytic Signal with (Discrete) Fourier Analysis
I am working with a finite signal response from an experiment. Basically, I feed in a uniform amplitude sine wave which ramps from 20Hz to 20kHz over the course of 50 seconds, and I read the output, ...
0
votes
1answer
20 views
Confused With using Fast Fourier Transformation for solving equations
As far as I know, the 3 steps of FFT while solving $F_nc = y$ :
Split c into c', c'' such that c' contains elements with even indexes from c and c'' contains the odd ones.
Now we have $F_mc' = y'$ ...
1
vote
1answer
253 views
FFT: Multiplying multiple poynomials in O(KSlogS) time
I have a problem where I have to use the Fast Fourier Transform (FFT) algorithm $K$ polynomials $P_1,...,P_K$ where $\mbox{deg}(P_1) + · · · + \mbox{deg}(P_K) = S$.
I have to show that I can find the ...
0
votes
2answers
33 views
Fast Fourier Transform with Negative Integer Exponent
Given $f(x)=ax+b+\frac{c}{x}$ and $N$, I'd like to ask how to calculate $\sum_{i=1}^{N}f(x)^i$ efficiently using fast Fourier transform?
0
votes
0answers
24 views
Convert Real and Imaginary part from FFT to bands
how can I convert real and imaginary part from FFT to octave bands? I know how to do it for Absolute value, but dont know for Re, Im parts.
Thanks
1
vote
1answer
86 views
Question about roots of unity in the Fast Fourier Transform
I am learning about the Fast Fourier Transform, which converts a polynomial from its coefficient representation into its point-wise form using divide-and-conquer. The Fast Fourier Transform evaluates ...
1
vote
0answers
58 views
How to implement boundary value in Python using spectral methods
I want to solve the heat equation $$u_t=au_{xx},\quad 0\leq t, \ 0\leq x\leq\pi$$ in Python using spectral methods. I set $u(0,x)=\sin(x)$ as initial value for the time and choose $a=2$. My Code:
<...
0
votes
0answers
20 views
How does scaling in frequency domain affect real space?
I have a 3 dimensional array of real data corresponding to measurements in physical 3D space, and its corresponding data in spectral space.
I want to scale certain specific frequencies in the ...
0
votes
0answers
153 views
Fast Fourier transform of the Gaussian function
As I know, the Fourier transform of the Gaussian function is also Gaussian.
The simple verification for that is shown below.
http://mathworld.wolfram.com/FourierTransformGaussian.html
But fast ...
1
vote
1answer
30 views
Can FFT be used to cluster sound waves based on their similarity?
I am new to this so apologies if the question appears trivial.
Say we have n sound files and we want to cluster them to identify which ones are more similar. I ...
1
vote
0answers
55 views
circulant matrix inversion using fast fourier transform
I am Huda. May I know, if I have a circulant matrix, can I calculate its inversion using fast fourier transform? If yes, I really need an explanation.
Thank you.
1
vote
0answers
7 views
2D FFT with unit stride data access?
I am trying to design a large 1D FFT by splitting N into two smaller FFTs of sizes N1 and N2. This is common approach stemming from the Cooley Tukey Algorithm. My FFT is taking time sampled data in ...
0
votes
0answers
14 views
How to re-scale and do correctly the discrete Fourier transform.
I'm stuck with the re-scaling and the proper choice of parameters in doing the discrete Fourier transform. I explain: Suppose you want to calculate the Fourier transform
$$
F(p) = \frac{1}{2\pi}\int ...
0
votes
0answers
23 views
Average of product of Fourier transform of two signals
I have two signals which depend on x and z, $a(x,z)$ and $b(x,z)$. Their Fourier transform along both directions is denoted as $A(k_x,k_z)$ and $B(k_x,k_z)$, respectively. I would like to compute the ...
0
votes
0answers
29 views
Matrix factorisation of the Fourier matrix
I am currently reading a paper Low Communication FMM-Accelerated FFT on GPUs
In that I am not able to understand the definition of the twiddle factor matrix $T_{P, M}$.
The Fourier matrix $F_N$ is ...
0
votes
0answers
13 views
DFT of a series of RC exponentials
Context: I'm trying use matlab to apply a single-pole filter to a time-domain ramp waveform that is generated by a sequence of time-shifted "RC steps" that are added together.
The time domain voltage ...
0
votes
1answer
23 views
Calculate $Av^{\rightarrow}$ using FFT
Given a vector $v^{\rightarrow} = (v_0,v_1, ... v_{n-1})$
And given the matrix A =
$(a_0, a_1 ... a_{n-1})$
$(a_{n-1}, a_0,...., a_{n-2})$
$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$
.....
$(a_1, ......
0
votes
0answers
46 views
Fourier tranform of the derivative
I have been recently studing Fourier transform and there is a proposition that says: If $\lim \limits_{x \to\infty}xf(x)=\lim\limits_{{x}\to -\infty}xf(x)=0$ then $$\hat{f'}(z)=-iz\hat{f}(z)$$
and ...
2
votes
1answer
26 views
Could families of “Airys” and “Bairys” of integer “frequencies” be useful?
A very famous family of functions are the complex exponentials and in the case of real valued functions, the sin and cos functions. They are related by the famous Euler formulas:
$$\exp(i\phi) = \cos(...
0
votes
3answers
53 views
Fast Fourier Transform algoritm - simple explanation(step by step)
I can't find step by step explanation of the FFT algorithm. Why it is faster than common DFT?
As I understand, we calculate DFT for $X$, and for $Y$, then merge them and got the final DFT.
2
votes
0answers
45 views
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 ...
0
votes
0answers
18 views
Fourier odd and even extension of descending steps function
Can anybody help me find even and odd extension of the descending steps function if $f(x)$ be:
\begin{cases}
f(x)= 1 & x\in[0,1]\\
f(x)= (0.5) & x\in[1,2]
\end{cases}
0
votes
0answers
12 views
Should DFT of cosine function be infinite at its frequency?
The Fourier transform of the cosine function is an infinite spike (Dirac delta function) at the frequency of the cosine wave. But it seems most DFT programs give a finite spike corresponding to the ...
0
votes
0answers
43 views
Discrete Fourier transform of sampled sin function nothing like continuous?
So I'm a little confused about what is going on with the discrete Fourier transform.
I tested out discrete Fourier transform with a little python script on a sin function
...
1
vote
1answer
41 views
Coordinates of a vector FFT
I was reading a paper about DFT, at the end he got the relations $Y=\frac{1}{\sqrt N}W_n \cdot y$ and $y=\frac{1}{\sqrt N}W_n \cdot Y$, where $y$ is a vector and $Y$ is the coordinates of that vector ...
1
vote
1answer
14 views
Why is the dot product of two columns $j$ and $k$ in FFT equal to $1+w^{j-k} + \dots + w^{(n-1)(j-k)}$?
The matrix is of the following form:
$\begin{pmatrix}
1 & 1 & \cdots & 1 & 1 \\
1 & w & \cdots & w ^{n-2} & w^{n-1} \\
\vdots & \vdots & \ddots & \vdots &...
2
votes
1answer
70 views
How to minimize sum of matrix-convolutions?
Given $A$, what should be B so that
$\lVert I \circledast A - I \circledast B \rVert _2$
is minimal for any $I$?
$I \in \mathbb{R}^{20x20}, A \in \mathbb{R}^{5x5}, B \in \mathbb{R}^{3x3}. $ Note ...
0
votes
0answers
24 views
Fourier transform of delta(dirac) function-multiplication with exp function
I am trying to find an integral of multiplication exponential function with a delta function.
I know a property of delta function that if I would like to take the integral of the multiplication delta ...
0
votes
0answers
43 views
Informations about Fourier Transform for a Python project (sound manipulation)
I have a project in Python with a friend where we want to manipulate music sound, and we'll need Fourier Transforms, so I made research online and wanted to know if I understand correctly the concepts....
0
votes
0answers
8 views
Most efficient method to find peak frequency of an FFT
I'm using a real to complex fft to get the peak frequency of a signal. What I want to know is the most efficient way to find the index of that peak. I currently use im^2 + re^2 and compare to the ...
0
votes
1answer
42 views
Efficient way to do a Fourrier Transform like operation
Suppose we have two functions $f,g:[0,\infty) \rightarrow [0,\infty)$. Then one can use Fast Fourrier Transforms to quickly compute $\int_0^t f(t-s) g(s) \, ds$ for $t$ in some range of values $[0,T]$ ...
0
votes
2answers
164 views
How to calculate 8-point FFT of data by hand
Given the following data:
Two period sine; samples = [0, 1, 0, -1, 0, 1, 0, -1];
I am asked to calculate the FFT of the sampled data to find the complex coefficients.
I don't necessarily want the ...
0
votes
0answers
12 views
fft algorithm - twidle multiplication
im trying to understand how fft(fast fourier transform) algorithm work and after watching several videos i couldn't understand why there is multiplication with Wn in this specific places and why the ...
