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.

168 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
90 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 ...
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
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
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
43 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
52 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
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
325 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
95 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
764 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
0answers
16 views

Optimizing FFTs using 3 summations.

The formula for mixed-radix (Cooley Tuky) FFT can be given as: \begin{align} \widehat{x_k} = \sum_{n=0}^{N-1}{ x_n \omega^{n k}} \end{align} with input $x_n$, output $\widehat{x_k}$, and setting $\...
1
vote
0answers
37 views

How to show $ IFFT\:(\:FFT\:(\:x\:)\:) = x $?

Can you show the steps to get $f[m,n] = f[m,n]$ for this? $$ f[m',n'] = IFFT \: ( FFT \: ( \: f[m',n'] \: ) \: ) $$ $$ f[m',n'] = \sum_{k=0}^{M-1}\sum_{l=0}^{N-1} \left[\frac{1}{MN}\sum_{m=0}^{M-1}\...
1
vote
0answers
51 views

Does Fourier Transform Convention Change Convolution

My goal is to find the Fourier transform of the product of two functions: The Heaviside step function $\theta(t)$, and $g(t) = A - A\cos(\omega_0 t)$. I want to do this by first Fourier transforming $\...
1
vote
0answers
23 views

The time complexity of integer multiplication by FFT without any sophistication.

David Harvey and Joris van der Hoeven proved at this year that the product of two integers whose bit length is $O(n)$ can be computed in $O(n\log n)$. I've heard that the optimal complexity of ...
1
vote
0answers
19 views

25 point FFT equations?

I was going to attempt to study up on various papers like this one: One Million-Point FFT (Hans Kanders and Tobias Mellqvist) https://liu.diva-portal.org/smash/get/diva2:1184623/FULLTEXT01.pdf to ...
1
vote
0answers
48 views

Solving a 2D partial differential equation with FFT to reconstruct an image

Let $v$ and $w$ be 2D images. I need to find $v$ such that $$\text{minimize} \quad \sum \frac{r_1}{2} (v - w)^2 + \sum \frac{r_2}{2} \|\nabla v - q\|^2 $$ where $r_1, r_2 > 0$ are scalars and ...
1
vote
0answers
17 views

What is the form of the spectral derivative in the all-positive-frequency notation in DFT?

The Discrete Fourier Transform (DFT) of a function $u:[0,2\pi] \to \mathbb R$ sampled over $N$ equidistant points $\theta_j = 2\pi j/N,\, j = 0, \dots, N-1,$ is defined by $$ \tilde U_k = \frac1N \...
1
vote
0answers
28 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)...
1
vote
0answers
23 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$, ...
1
vote
0answers
47 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
303 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 ...
1
vote
0answers
60 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: <...
1
vote
0answers
103 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
12 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 ...
1
vote
1answer
23 views

Discrete Hartley Transform Diagram

Hi I am looking for DHT diagram(or pseudo code) for N=8 but cannot gain any result. since I am not major in math, cannot grasp whole article. So is there anyone who can draw DHT diagram in N=8 for ...
1
vote
0answers
87 views

Filter a signal using FFT

I need to filter a signal without it losing its properties so that later that signal is inserted into an artificial neural network. I'm using the R and the signal library, I thought about using a low-...
1
vote
0answers
32 views

Difference between NFFTs, NUFFTs, USFFTs (for CT purposes)

I am trying to understand for what cases and in what way NUFFTs would be useful for CT reconstruction. Therefore, I am trying to create an overview for myself that starts with the "easy" problems ...
1
vote
0answers
39 views

What is the Discrete Fourier Transform of a periodic sequence?

Shor's algorithm utilises the properties of quantum computers to find $r$ in, $$ a^r = 1 \mod n $$ wherein $r$ is even and $a^{r/2} + 1\neq 0$. However I haven't been able to find any resources in how ...
1
vote
0answers
93 views

Finding working modulus for FFT over finite fields

I would like to implement multiplication of polynomials using NTT. I followed Number-theoretic transform (integer DFT) and it seems to work. Now I would like to implement multiplication of ...
1
vote
0answers
351 views

Plot Bode from FFT

I have data in excel (time and vibration), which I have done calculated fft for the data. Now, I want to plot the bode diagram, but I don't know how to. Is it possible to plot the bode from fft since ...
1
vote
0answers
126 views

Why can FFT (NTT?) work well on polynomial ring with some integer coefficient modulus?

I understood how FFT works over complex field $\mathbb{C}$, but still do not understand why its variant Number Theoretic Transform (NTT) works over polynomial ring with some integer coefficient ...
1
vote
0answers
15 views

Which part of formula is FFT changing the basis?

I have heard that FFT works by changing the basis of original vector. I do not know which part of formula is correspondence.
1
vote
0answers
264 views

What is the intuition of FFT for polynomial multiplication?

What is the intuition of FFT for polynomial? Multiplications on two ($N-1$)-degree polynomial is naively done in $O(N^2)$. Using FFT, we can reduce the complexity to $O(N\log N)$. As for addition, w/ ...
1
vote
1answer
321 views

Fourier Curve Fitting

I'm having a rough time understanding the world of the Fourier series. I've read an awful lot, but am not mathematically inclined, so most of what I have read is not in terms my brain understands. ...
1
vote
0answers
13 views

Optimization of a Fast Fourier Transformation-based correlation function?

As a forward, I don't have a lot of extensive mathematics knowledge. I'm a sophomore in CS, and I've taken up to Calc 2 (with some other random knowledge from watching youtube vids). I've done some ...
1
vote
0answers
89 views

Arcsin of a number greater than one

I am using a DFT to sum multiple sinusoidal signals produced by an N-anteanna array. $$X_k=\sum_{n=0}^{N-1}f(n)e^{-i2\pi \frac{n}Nk}$$ Assume $f(n)$ is the excitation of the nth antenna and is the ...
1
vote
0answers
80 views

Speed up distance calculations, FFT, Sliding window

I have two time series A and B. A with length m and B with length n. m << n. Both have ...
1
vote
0answers
77 views

Is there a Hausdorff-Young inequality which applies between a length n sequence and its n Discrete Fourier Transform?

I have been looking around for generalization of the Hausdorff-Young inequality that can be applied between a length $n$ sequence and its $n$-Discrete Fourier Transform (DFT) but no luck. The n-DFT $X$...
1
vote
0answers
271 views

Can we use fft algorithm for find Fourier Series coefficients?

wen can easily find a0, a1 and b1 coefficients with classical formula. Also Matlab or that kind of program have built in fft functions and we can find fft of any non-periodic function. I just want to ...
1
vote
0answers
43 views

what is the fast fourier transform of complex guassian?

It is widely known that Fourier transform of complex Guassian function \begin{equation} \mathcal \ F(x)=e^{-j x^2/a} \end{equation} is \begin{equation} \mathcal \ F(f)= A e^{jπ^2f^2a} \end{...
1
vote
0answers
17 views

Fast Fourier Transform Series

Why is the following equality the same? $\sqrt{1 \over 2N} \sum\limits_{j=-N}^N'' \exp({ijk\pi \over N})g({j\pi \over N})=\sqrt{1 \over 2N} \sum\limits_{j=0}^{2N-1} \exp({ijk\pi \over N})g({j\pi \...