We’re rewarding the question askers & reputations are being recalculated! Read more.

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
12
votes
3answers
5k views

How does FFT work?

For five years I tried to understand how Fourier transform works. Read a lot of articles, but nobody could explain it in simple terms. Two weeks ago I stumbled upon the video about a 100 years old ...
5
votes
3answers
75 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 ...
5
votes
2answers
3k views

Solve Poisson Equation Using FFT

I am trying to solve Poisson equation using FFT. The issue appears at wavenumber $k = 0$ when I want to get inverse Laplacian which means division by zero. We have ${\nabla ^2}\phi = f$ Taking ...
5
votes
0answers
85 views

Determine the shift in tonal center of a piece of music.

Starting with a sampled audio signal of acapella vocals, I am interested in determining the shift in the tonal center of the music through the performance. As a choir progresses through a ...
4
votes
2answers
188 views

Application of the FFT

A discrete Fourier transformation of N-th order is the map $F:\mathbb{C}^N\to\mathbb{C}^N$ given by $$w=Fz\qquad w_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\zeta_N^{jk}z_j,$$ where $\zeta_N=e^{-\frac{2\pi ...
4
votes
1answer
67 views

Can't extract odd function with FFT

I can't correctly extract spectrum from data points of odd function (e.g. $\cos\left(\frac23\pi x\right)$, $16$-points vector $[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1]$), instead of one function I get a ...
4
votes
3answers
666 views

Negacyclic FFT multiplication

I am using an FFT to multiply polynomials. Because I want the program to be as fast as possible I am leaving away the zero padding. For example, if we want to calculate: $(58 + 37x + 238x^2 + 155x^3)^...
3
votes
2answers
71 views

Value Proposition of Fourier Analysis?

I am a software engineer trying to wrap his head around Fast Fourier Transform (FFT). Specifically, I need to implement it as part of some software I am writing. Now I can handle the implementation of ...
3
votes
2answers
55 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 ...
3
votes
1answer
103 views

Omitting twiddle factors in Cooley–Tukey FFT algorithm

The discrete Fourier transform $$ X_k = \sum_{m=0}^{n-1} x_m e^{-2\pi ikm/n} $$ can be computed via Cooley–Tukey FFT algorithm The key of the algorithm is the butterfly transform, given by $$ X_k = ...
3
votes
1answer
693 views

Multivariate Polynomial Multiplication using Fast Fourier Transform (FFT)

I am trying to find the coefficients of multiplications of 2 $N$-variate polynomials using $N$-dimensional fast Fourier transform (FFT) on MATLAB. My approach so far is as follows: Based on this post,...
3
votes
1answer
48 views

Get an approximate factorization for a number $n$

For a given number $n$, I am interested in the closest number that can be written as a product of a given set of prime factors. More precisely, I am interested in a solution of the following problem ...
3
votes
0answers
61 views

Translation of the work of Gauss where the fast Fourier transform algorithm first appeared

As far as I know, the fast Fourier transform algorithm first appeared in 1805 in "Theoria interpolationis methodo nova tractata", by Carl Friedrich Gauss. This work is available in Latin, which, to ...
3
votes
0answers
2k views

How to implement NTT( Number theoretic transform) [closed]

I am having tough time while implementing NTT. After reading lot of tutorials on FFT and NTT from http://www.apfloat.org/ntt.html, http://codeforces.com/blog/entry/43499 and some others, I have ...
3
votes
0answers
38 views

Does the fast Fourier transform have equivalents in other transforms?

I've seen the Mellin transform described as the "multiplicative" analogue to the Laplace transform, as well as the Fourier transform when $x\to\log y$. Would a discrete Mellin transform be able to ...
3
votes
1answer
123 views

How to compute $p(x)=\prod_{k=0}^{n-1}(x-z_k)$ using the FFT with complexity of O(nlog^2 n)?

I've a question and in its last step I'm required to find the above product (I need the coefficients of the result of that product as my final answer). It seems that FFT can be used to compute it. I ...
3
votes
0answers
117 views

How to decompose a 2d shape into sin and cosin modes?

Assume that you have a circle with radius $r_0$, then you keep adding cosine modes as below: $r=r_0+a_1\cos(1\theta)+a_2\cos(2\theta)+a_3\cos(3\theta)+a_4\cos(4\theta)+~...$ if you plot this as ...
2
votes
2answers
111 views

What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand ...
2
votes
1answer
913 views

How does the phase plot of Fourier transform of sine wave look like?

I found that transform of Sin(t) look like THIS If its amplitude look like THIS How does its phase look like? I have found one question on stack which is similar to my question but does not ...
2
votes
1answer
69 views

Indexing of Discrete Fourier Transforms

I was looking at the Discrete Fourier Tranform section in these notes and I'm very confused about how the transform is being indexed. There, a list of the form $f(x_n)$ is given where $x_n$ takes on ...
2
votes
2answers
599 views

The best textbook on Fourier Transformation for beginners

I am absolutely new to Fourier Transformations. I have a bit of background in Trigonometry. Which text book would you recommend to learn Fourier transforms from the very basics?
2
votes
1answer
45 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 ...
2
votes
1answer
84 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
50 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. ...
2
votes
1answer
28 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(...
2
votes
4answers
100 views

Intuition of fft over time to frequency

I understand how FFT (DFT) works. It acts as a change of basis. However, while many websites describe fft as a method that convert time domain stuff to frequency domain stuff, I still do not know why ...
2
votes
1answer
121 views

How to get the frequency of a time-domain signal with limited sample length?

Let's say there is a signal who only has one peak in its power spectrum. I would like to know the frequency at which the peak is (the magnitude of power is not important to me). But I only have very ...
2
votes
1answer
78 views

Is it possible to solve the following PDE without using Fourier transform?

Solve the following non-homogenous heat equation:$$ \frac{\partial u}{\partial t} = a^2 \frac{\partial ^2 u}{\partial x^2} + \epsilon \sin(k_0x)$$ on the domain $-\infty \lt x \lt \infty $, with ...
2
votes
1answer
1k views

Relation between Discrete Fourier Transform and Fourier Series

I was given a task to obtain a Fourier Series approximation from the DFT (Discrete Fourier Transorm), more exactly fft function from MATLAB. I know that a Fourier Series has the form $\frac{a_0}{2}+\...
2
votes
1answer
80 views

Find the fourier series representation of a function

Consider the function $f(x) = \begin{cases} \frac{\pi}{2}+x & & x \in (-\pi, 0] \\ \frac{\pi}{2}-x & & x \in (0, \pi]\\ \end{cases}$ extended 2$\pi$ periodically to $\mathbb{R}$. ...
2
votes
1answer
599 views

Compute Fourier coefficients of spline fit to data

Suppose you have data $$\{(x_i, -1^{i+1})\}_{1\dots N}, \quad x_1=0<x_i<x_{i+1}<x_N=2\pi \ \forall i \in\{2,\dots N-1\} $$ In other words, we have a sequence of $y=\pm1$ values at distinct ...
2
votes
1answer
1k views

Recursive FFT java implementation [closed]

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...
2
votes
0answers
26 views

DFT and inverse problem

Let two functions $I,J:\{0,1,\ldots,n\}\times \{0,1,\ldots,m\} \mapsto \{0,1,\ldots,p\}$ and $h$ a $v\times v$ matrix ($v\ll n,m$) such that $$ J = I * \underbrace{h*\ldots *h}_{p \text{ times}} $$ ...
2
votes
1answer
133 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 ...
2
votes
0answers
40 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 +...
2
votes
0answers
52 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 ...
2
votes
0answers
51 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 ...
2
votes
1answer
76 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 ...
2
votes
0answers
31 views

Increasing frequency resolution of FFT on a windowed sample of a signal

Okay, this gets a bit technical, let me explain the background. In doing loudspeaker measurements for its direct sound in normal rooms that have reflections, what we do is measure the whole impulse ...
2
votes
1answer
324 views

Efficient matrix-vector multiplication for “partial” Hadamard matrices

I've recently been working on an algorithm for bilinear systems in the form $y = (Lw) \odot (Rx)$, where $\odot$ denotes the elementwise product between two matrices of compatible sizes. In the above, ...
2
votes
0answers
110 views

Discrete versions of the Fourier Slice-Projection Theorem

I understand the continuous version of the Fourier Slice-Projection theorem, which says that given a (nice enough) function $f:\mathbb{R}^3\to\mathbb{C}$ the following operations give the same result: ...
2
votes
0answers
236 views

Unable to solve nonlinear equation using scipy.optimize.fsolve

I am using scipy.optimize.fsolve to solve a nonlinear equation in Fourier pseudospectral space but it does not work. It gives the same output as the input u0, which is a trivial solution. The equation ...
2
votes
0answers
106 views

How to solve least square quadratic problem using FFT

Let A, B, C and D be some matrix and x be a vector, I want to solve the following optimization problem: $$ \min_x \| Ax -B\|^2_2 + \| Cx-D\|^2_2 $$ my solution: $$ J = \| Ax -B\|^2_2 + \| Cx-D\|^2_2 ...
2
votes
0answers
144 views

Period-based Fast Fourier transform

I have a list of events times $t_n$ in which I would like to find repeating patterns in the temporal density (how many events per second). And finally plot how likely it is to find a pattern of period ...
2
votes
0answers
670 views

Fourier Series: Music from a Piano vs Keyboard [closed]

So, I've been working on a project to compare the Fourier Series of a Piano versus that of a Keyboard. I've computed the FFT on MATLAB using this code: dt = 1/fs t = (1:length(data))*dt X=fft(data) ...
2
votes
0answers
94 views

Does NTT have an upper bound?

I'm working with NTT (Number theoretic transform) to reduce the complexity of a polynomial multiplication. For this, I'm using $P = 2^{64}-2^{32}+1$ to generate the primitive root $\omega_N$ needed by ...
2
votes
0answers
761 views

Solving a simple Schrodinger equation with Fast Fourier Transforms

While trying to solve a stochastic Gross-Piaevskii equation I have found a problem that can be tracked down to something buggy occuring in the simplest Schrodinger equation possible: $\partial_t \psi ...
2
votes
0answers
702 views

Inverse of a Toeplitz matrix with FFT-based methods

I have a covariance matrix $Q$ and need to find $Q^{-1}$. Here, $Q$ is a Toeplitz matrix. I want to calculate the inverse of the matrix with FFT-based methods rather than the conventional ones like ...
1
vote
1answer
2k views

Find the solution of the Dirichlet problem in the half-plane y>0.

Find the solution of the Dirichlet problem in the half-plane $y>0$. $${u_y}_y +{u_x}_x=0, -\infty<x<\infty,y>0$$ $$u(x,0)=f(x),-\infty<x<\infty$$ $u$ and $u_x$ vanish as $$ \lvert ...
1
vote
3answers
897 views

What is the Permutation Matrix in FFT DFT Factorization?

Given: $$F_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^...