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

146 questions
59 views

### Sampling and the Discrete Fourier Transform

Suppose $f:\mathbb{R}\rightarrow\mathbb{C}$. We'd like to take the Fourier Transform of this function, defined as $$F(s) = \int_{-\infty}^\infty f(x)e^{-i \, 2\pi \, s \, x}dx.$$ However, a computer ...
37 views

### Why is there periodicity in the output of Richard Voss' fractional Brownian motion?

I am trying to figure out why the output of fractional Brownian motion (fBm) as described by Richard Voss (Random fractal forgeries. In: Fundamental Algorithms for Computer Graphics, R. A. Earnshaw (...
279 views

### analyze convolution in spatial domain against multiplication in frequency domain

Lets say I have a image of $NxN$ and a separable filter that I want to apply on it. there are 2 ways to do that: 1. By convolution in spatial domain. 2. By multiplication in frequency domain. I need ...
99 views

### Can downsampling create energy at the Nyquist frequency?

I am a bit surprised by the following and would like to share it with you. I expect I am mistaken somewhere and will be happy to be corrected. I have searched StackExchange not only in Mathematics ...
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$,...
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)$ ...
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 ...
36 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. ...
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 ...
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 ...
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
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 ...
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 ...
14 views

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 ... 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 ... 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 ... 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 ... 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 ... 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} 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 ... 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 ... 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 ... 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.... 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 ... 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 ... 0answers 21 views ### Not getting expected results with FFT So I made this virtual car that moves at a velocity that is the sum of three different sine waves (whose individual frequencies I know). I constructed this velocity time graph Then I perform a FFT on ... 0answers 11 views ### Discrete Hartley Transform when N=8 Hi I am currently studying FHT Algorithm but have a hard time to grasp it. I want to calculate FHT when N=8. http://mathworld.wolfram.com/HartleyTransform.html thanks to (19) of the upper link, the ... 0answers 54 views ### Using fft() in Matlab I have a function defined like:$$x(t)=2e^{-\frac{r}{2}t}\sin\left(\frac{1}{2}\sqrt{16\pi^2-r^2}\cdot t\right)\left(\frac{\Theta(t)}{\sqrt{16\pi^2-r^2}}\right) $$Where \Theta(t) is the Heaviside ... 0answers 15 views ### How to assess the convergence of a time series towards a periodic signal and assess the sufficiency of the sample size? I have a sampled temporal signal, result of a transient fluid simulation. At the beginning the flow is being established, so the first few seconds of signal should be ignored (question : is there a ... 0answers 24 views ### Two dimentional discrete Fourier Transform, dimentions when performing convolution I have trouble wrapping my head around the way 2d convoluion with fft is performed. I understand how 2d convolution works when performed clasically (technically I'm interested in cross-correlation as ... 0answers 24 views ### Polar representation of a function in Fourier transform I need to perform a Fourier transform of the function which has the following form$$\hat{f}(\omega)=\mathcal{F}(\mathbb{e}^{i S(x)}R(x)),$$where both R(x) and S(x) are real. I am wondering if ... 0answers 15 views ### DFT on a Vector p(x) = x^n Let m \in \Bbb N, n \in \Bbb N, such that m divides n. What is the output of a DFT_m of order m when the input is the coefficient vector of the polynomial p(x) = x^n? Well this ... 0answers 59 views ### Fourier transform of the ln of a variable Consider the following Fourier transform:$$\hat{f}(\ln \xi) = \int_{-\infty}^{+\infty} f(x) e^{-2\pi i x \ln{\xi}} \, \, dx $$Assuming I can calculate \hat{f}(\ln \xi), how can I go from \hat{f}(\... 0answers 50 views ### Spectral Derivatives and Wave Numbers This author is explaining spectral derivatives on a discritized domain with N grid points, using Fast Fourier Transform (fft) and inverse fourier transform (ifft). The distance between grid points ... 0answers 91 views ### fft of sawtooth signal I have a very basic question. sorry for such a naive question! I have a sawtooth signal which look like this: this is how I generated this signal : ... 0answers 18 views ### convolution of nearly periodic data Suppose I have two vectors x,y\in\mathbb{C}^n. I am interested in efficient calculation of the convolution$$z(k) = \sum_{i=0}^{n-1}x(i)y(i+k)$$for k=0,...,n-1. Note that y is taken nearly ... 0answers 31 views ### Fourier Transform with translation e^{-4t} µ(t+5) note that µ is the Heaviside function. I wonder if the correct transform with translation/shifting would be:$$F(w)= \biggl(\frac{1}{4+iw}\biggl)(e^{5iw})$$0answers 19 views ### Where is the inverse fourier in this solution? I am trying to understand the relationship between the Wiener-Khinchin Theorem and the Autocorrelation Function. I am learning this by myself and just started learning about Fourier Transforms, so I ... 0answers 68 views ### fit curve with fft and calculate it's derivatives Here is my issue: I am trying an algorithm using FFT to fit and get a function's approximative in order and calculate its derivative in an easier way (for any data), but I get some discontinuity. At ... 0answers 37 views ### confused doing FFT I have data vibration in excel, the first row is time, and the second is vibration. I want to use fft to analyze the vibration. Because, i'm new to dsp, i don't know, what is sampling frecuency, etc. ... 0answers 41 views ### Fourier transform on formal series I am searching for a "Fourier transform" T on formal series with coefficients in dyadic numbers, such that:$$T(fg)=T(f)*T(g)$$Where * is the "coefficient by coefficient " multiplication (\sum ... 0answers 618 views ### Compute Transfer Function from FFT of Input and Output I tried the method described in a previous answer (https://math.stackexchange.com/a/718856/451691) to compute the transfer function of a system I am studying, where: In(t) = a(t); Out(t) = b(t) I ... 0answers 51 views ### Low Pass Filter using FFT up to the Nth overtone I'm writing a program in c# that uses Meta.Numerics to calculate the FFT of a signal recorded during one cycle. The overtones are presented as complex numbers. Now I would like to reconstruct the ... 0answers 49 views ### How can I interpret the discrete impulse response measurement? Assume that we have our discrete transfer function G(e^{j\omega_k}) where, k = \frac{\pi k}{M} , k = 0, \dots , M. If we want to find Markov-parameters g_k from the impulse response$$g_k = \...
We're given two positive integers of length $n$ in binary representation. Design an algorithm which divides the numbers into ${n \over k}$ blocks of size $k=\lg n$ using FFT algorithm. We ...