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
1answer
12 views

Siegman Discrete Fourier Transform notation misunderstanding

I was reading A.E. Siegman's Fiber Fourier Optics paper and came across the following equation which was described as the DFT:enter image description here and I don't understand why it's that equation ...
2
votes
1answer
25 views

FFT in Python without numpy yields other result than with numpy

I tried to find an implementation of the FFT algorithm in Python without the use of the numpy library. I found one and it seemed to work, but when I tested it on a more realistic sample it failed and ...
0
votes
1answer
22 views

Unstable behavior of Discrete Fourier Transform and Fourier Transform alternatives

I have come across a "weird" behavior of the Discrete Fourier Transform (which I will refer to from now as DFT). suppose $$x=(1,-1,1,-1)$$ The real part of the DFT of $x$ is $$Real(DFT(x))=(0,0,4,...
0
votes
0answers
45 views

The value of $\sum_{n=1}^{\infty} \frac{{(-1)}^n}{n^6}$ using the Fourier Transformation

How to compute the sum given in $(1)$, from the fourier transformation of $\pi x |x|-x^3$ over $(-\pi,\pi)$. $$ \sum_{n=1}^{\infty} \frac{{(-1)}^n}{n^6} \tag{1} $$ Suppose we know that $\sum_{n=1}^{...
0
votes
0answers
6 views

Does frequency domain represent distribution of y-axis of Time domain analysis?

I'm wondering how time domain and frequency domain differ in fourier analysis. Converting a vector in time domain to the one in frequency domain refers to Fourier Transform. Is this equivalent to ...
1
vote
0answers
27 views

Using the FFT to get the Fourier transform of a function

I am trying to use an FFT to numerically obtain the Fourier transform of the function $ f(t) = \sqrt{\frac{\mu}{\sqrt{\pi}}} \exp\left(-\tfrac{1}{2} (\mu x)^2 \right) $ which is precidely $F(\omega)...
0
votes
0answers
32 views

Why must the length of a sequence under the discrete Fourier transform be equal to the input sequence length?

Let's consider a continuous signal, $f(t)$, which has been sampled $N$ times, with spacing $T$ between samples. We denote the $N$ samples $f[0], f[1], ..., f[N-1]$. The Fourier transform of the ...
2
votes
1answer
57 views

Discrete Fourier transform of $(1,1,1,1)$

I am asked to determine the Fourier transform of $(1,1,1,1)$. In the solution I found this: I don't get how is he transitioning from the $\omega$'s to $-i, i, -1, 1$ etc... How to break it down, so ...
2
votes
1answer
130 views

Bandlimited reconstruction of sampled periodic functions.

This has to do with the Nyquist-Shannon sampling and reconstruction theorem and the so-called Whittaker–Shannon interpolation formula. I had previously asked an ancillary question about this here but ...
0
votes
0answers
14 views

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 ...
0
votes
0answers
25 views

Problem in Wiener-Khinchin of a discrete signal using matlab

I am trying to calculate the PSD from the autocorrelation using the Wiener Khinchin theorem. In particular I am trying to do this starting from the matlab formula xcorr, which produces an array of ...
2
votes
0answers
23 views

Quantify measure of oscillations in periodic time series data

I have a periodic time series data that are constantly sent to server from machines. It has uneven sampling rate. I want to quantify measure of oscillations by combining information about frequency +...
0
votes
1answer
27 views

Shifting phase in Fourier frequency domain

Suppose I have 2 identical Gaussian pulses, but separated by some phase offset. If I take the Fourier transform of it to move from time domain to frequency domain, how can I manipulate the phase terms ...
0
votes
0answers
20 views

psd of a signal using the welch procedure

I have seen that it is possible to calculate the PSD of a signal u , doing this procedure U=fft(u) psd=U*conj(U) Is this the Welch method? can you someone recommend me a book or a paper that ...
5
votes
3answers
61 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
51 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
21 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
32 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
44 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
47 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
37 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
27 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
43 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
39 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
40 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
44 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
23 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
11 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
20 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
272 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
143 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
22 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
169 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
40 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
76 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
8 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
15 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
27 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
32 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
25 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
47 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(...