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.

3
votes
0answers
52 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
37 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
0answers
111 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
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 ...
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 ...
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
0answers
103 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
218 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
97 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
142 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
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
722 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
649 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
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$, ...
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
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: <...
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 ...
1
vote
0answers
74 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
28 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
36 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
48 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
248 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
105 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
13 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
231 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
0answers
12 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
76 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
68 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
70 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
251 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
42 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 \...
1
vote
0answers
22 views

Fourier transformation, $G_k$ values

The following paper brings an application of the Fourier transformation. I would like to evaluate $$ G_{k}=\oint_{0}^{2\pi}G(\theta)e^{jk\theta}d\theta, $$ for $k=1,2,...,6$, where $$ G(\theta)=\...
1
vote
0answers
558 views

Solving differential equation using FFT: dealing with zero frequencies

To get started using spectral methods to solve differential equations I am currently using Matlab and its FFT library. I have successfully approximated a first derivative of a function using the ...
1
vote
0answers
88 views

understanding Fourier transform results for probability distribution

I think I do not understand Fourier transform results properly. I am trying to improve my understanding. It would be very kind if someone can help by commenting/answering. This is the following ...
1
vote
0answers
80 views

FFT convolution for log-domain calculations?

I'm dealing with convolution among some large functions. Say f1 and f2. The values f1(i) ...
1
vote
0answers
146 views

DFT implementation: relationship between number of samples and resolution of frequency

I come from an engineer background and I am sorry that this got so long. If $f(t)$ is a continuous signal, let $f[k]$ be the discretized signal for a timerange $T$ between two samples with for ...
1
vote
0answers
16 views

How do spherical harmonic degrees compare to the Fourier domain

I have a filter in the spherical harmonic domain (say a simple cosine taper between degrees 80 and 550) and need to apply that same filter in the Fourier domain (after applying the fft to the data). ...
1
vote
0answers
254 views

Is group theory useful for understanding the FFT?

The Fast Fourier Transform problem is to evaluate the matrix-vector product $$ X = W x $$ quickly, where $x$ is the input signal and $W$ is the DFT matrix, $$ W = \frac{1}{\sqrt{N}} \pmatrix{ 1 & ...
1
vote
0answers
112 views

Calculate Hankel Transform by Fast Fourier Transform

I am currently working on computing convolution by Fast Fourier Transform (FFT). The functions are in 2D however with circular symmetry $f(\mathbf{r}) = f(r)$. I have already implemented 2D FFT to ...
1
vote
0answers
246 views

From acceleration spectrum to velocity

Searching a totally irrelevant matter, i came across the following patent: https://www.google.com/patents/US5744723 , which proposes a framework to calculate velocity from machine vibration data. ...
1
vote
0answers
71 views

Interpreting frequency spectrum of periodic probabiltiy distribution

I'm not sure how to interpret the frequency spectrum produced from some discrete data below. Below is a probability distribution for a simulation I'm running that varies with time (each point on the ...
1
vote
0answers
19 views

FFT not returning period of data

I have some data that I'm trying to build a statistical model for. The data looks like this: To my assessment. This looked like a number of sinusoidal functions. I tried to do a FFT on the data to ...
1
vote
0answers
121 views

Calculating of roots of unity

$$P(x) = (x-1)(x-\omega_{15})(x-\omega_{15}^2)...(x-\omega_{15}^{14})$$ Where $\omega$ is a root of unity of order 15 and $\omega_{15}= e^{2\pi i/15}$ I need to simplify this. The solution is using ...
1
vote
0answers
173 views

Best curve fitting

In general I would like to know the advanced curve fitting algorithms to fit a curved profile from the given set of point coordinates. would be helpful if any insights on what is the algorithm used in ...
1
vote
0answers
128 views

Optimized convolution by FFT / complex multiplication / IFFT

I have some optimization questions about real time partioned convolution by multiplication in the frequency domain. Now my process looks as follows: Initialization: a symmetric FIR impulse response ...
1
vote
0answers
62 views

Vector valued polynomial composition; Computational complexity

Let $$P:\mathbb{R}^n\to\mathbb{R}^n$$ be a vector valued polynomial. What is the computational complexity of the composition of two such polynomial? Can the Fast Fourier Transform be employed on ...
1
vote
0answers
61 views

How to compute the ifft of a vector?

In the following post Concrete polynomial implementation it is said that the final step before obtaining the product of two polynomials is to compute the ifft of a vector. How to compute the ifft of ...
1
vote
0answers
228 views

2D Fourier Differentiation in Matlab

I am working in Matlab to compute partial derivatives and a Laplacian using Fourier Transforms. I prefer to take spectral derivatives, since it corresponds to multiplication by a wave number, however, ...