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 ...