Skip to main content

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
0 answers
8 views

iFFT a Known Transformed Function to Get the Unknown Complex-valued Initial Function

Background: In my case, I need to get the solution of a series of 2D equations. The analytical expression of this solution ($f$) is not available but the transformed one is. Therefore, I need to ...
Duomo Feng's user avatar
1 vote
2 answers
68 views

Given Green's function, can I find the corresponding operator?

Green's function is the solution to the equation $L G(x;x') = \delta(x-x')$, where $L$ is a linear differential operator. Usually, we want to find the Green's function of a given $L$. Instead, if we ...
Sean's user avatar
  • 51
0 votes
0 answers
27 views

Is the product of exponentiated elliptic curve basis elements invariant under FFT of scalars?

I am working with an elliptic curve defined over a finite field $\mathbb{F}_p$ and have a basis set of points ${g_0, g_1, \ldots, g_n}$. When I perform the FFT on these points, I obtain a new basis ${...
Nerses Asaturyan's user avatar
0 votes
0 answers
15 views

Fast Fourier transformation in a lattice $H_{\vec{R}}(m,n,l)$ to $H_{\vec{k}}(a,b,c)$

I have a Hamiltonian defined on a lattice grid $H_{\vec{R}}(m,n,l)$ with $m,n,l \in \mathbb{N}$ and ranging in [-M,M], [-N,N], [-L,L]. Based on the $H_{\vec{R}}(a,b,c)$, a discrete Fourier ...
ljw1121's user avatar
0 votes
0 answers
51 views

How to accelerate calculation of a nested integral

Setup Let $A(t)$ and $B(t)$ be positive functions defined on $t \in [t_1, t_2]$. They are sampled uniformly within this interval, with a timestep of $\Delta t$. Question I want to calculate the ...
Aleksejs Fomins's user avatar
0 votes
0 answers
81 views

The Fourier transform of product of derivatives

I have the task to compute the Fourier transform of the product in matlab: $$ \left( \frac{\partial u(t, x)}{\partial x} \right)^2 \left( \frac{\partial^2 u(t, x)}{\partial x^2 } \right)$$ I was ...
unknown's user avatar
  • 391
1 vote
0 answers
45 views

How to correctly calculate Poisson's equation for electric potential using FFT with zero-padding?

I'm working on a program that simulates the electrostatic field in 3D using FFT to solve Poisson's equations based on the following formulas: $$ \phi_{(k)} = \frac{\rho_{(k)}}{\epsilon_0 \times K^2} $$...
pierniczki's user avatar
0 votes
0 answers
54 views

Inversion formula for discrete sine and cosine transforms

$\newcommand{\wh}[1]{{\widehat{#1}}}$ $\newcommand{\R}{{\mathbb{R}}}$ I am looking for a proof of the inversion formulas for the discrete sine and cosine transforms, i.e. a proof of the fact that ...
Bettina Kraus's user avatar
1 vote
1 answer
35 views

What function can model a decay, whose linear slope smoothly changes around a certain x value.

am a biology student trying to find a fitting function to model the $1/f$ decay or 'aperiodic component' of a neural power spectrum. In an (over)simplified way it can often be describes with the ...
Stav32's user avatar
  • 11
0 votes
0 answers
33 views

Help with understanding Inverse Discrete Fourier transform

I am trying to program a simple implementation of Inverse discrete Fourier transform. I thought I understood, but something in my understanding is obviously lacking since my results are wrong. For a ...
Emil's user avatar
  • 1
1 vote
0 answers
23 views

Discrete Fourier transform for time series with small time-shift measurements

I have a time series that can only take positive integer values in the range [0, 100]. This time series shows periodically recurring patterns which can be uncovered by using the discrete Fourier ...
Radu's user avatar
  • 143
2 votes
2 answers
141 views

Why is the FFT output divided by the data length?

I am working with FFT using NumPy in Python, and I noticed that it's common to divide the output of the np.fft.fft function by the length of the data array. Here's a simplified example of my code: <...
Jihyun's user avatar
  • 267
1 vote
0 answers
38 views

convolution-like computation of bivariate distribution

I would like to optimize code to compute a bivariate distribution like this (for example the bivariate poisson distribution): $f_{n,m} = \sum_{i=0}^{n-1} a_i \times b_{n-i} \times c_{m-i}$ It really ...
S4gaN's user avatar
  • 11
0 votes
1 answer
84 views

Interpretation of the impact of n on the fourier transform of exp(np(w)) or way to simplify expression

My goal is to find $$IFT\{exp(np(\omega)\} = \int_{-\infty}^{\infty} exp(np(\omega) + 2i\pi \omega f) d\omega $$ that is the Fourier transform of $exp(np(\omega))$ Here $n>0 \in {\rm I\!R}$ $p(\...
John Smith's user avatar
3 votes
0 answers
170 views

Most efficient way of finding specific coefficients of product of high-dimensional Fourier series

I find myself in need of an efficient way to perform a specific computation. Suppose I have the following two Fourier series $$ a(t_1,t_2,t_3)=\sum_{j=-n}^{n}\sum_{k=0}^{n} \sum_{l=-n}^{n} a_{j,k,l} e^...
Croc2Alpha's user avatar
  • 3,847
1 vote
0 answers
9 views

What's the fastest way to compute the 3D inverse cosine transform for a set of indices

I have a 3D tensor in the Fourier domain and I'm trying to compute the real (spatial) values of a subset of the indices. Computing the entire inverse transform is too computationally expensive. The ...
Alex Jon Lozano's user avatar
0 votes
1 answer
23 views

Inverse FFT at non-integer points

I'm running into something confusing. I have this python code that does an FFT of a real signal, and then reconstructs it by manually summing the complex exponentials: ...
MarcTheSpark's user avatar
1 vote
1 answer
37 views

Fourier Series Coefficient Confusion

In the context of the Discrete Fourier Transform, a function in time may be expanded as a Fourier series, $$ f_m = \frac{1}{T} \sum_{n=0}^{N-1} \tilde{f}_n e^{2\pi inm/N}, $$ where $ f_m $ is the ...
Rich Hard Fine Man's user avatar
1 vote
0 answers
25 views

The units of spatial frequency of fft

We are performing fft on N samples of a function f(x) that is periodic on the interval [0,L] where x is in meters. What would be the most common definition of the units of the domain of the ...
Tomer's user avatar
  • 436
0 votes
1 answer
95 views

The domain of FFT

I have a real signal $f(t) $that is periodic on $[0,L]$ where $L=1$. I sampled it uniformly $64$ times and computed FFT (in python). I was asked to find the frequency where the transformed signal is ...
Tomer's user avatar
  • 436
6 votes
2 answers
2k views

Why are FFT results different from theory and how to eliminate the difference?

I am working with time series data, and applying FFT to calculate the power spectrum. The data is something like this: $y = \sum_{k=1}^{5} \cos(10 k x)$ All the peaks in the FFT output should have ...
Jihyun's user avatar
  • 267
0 votes
1 answer
51 views

The Excel Fourier transform of Gaussian does not match the analytical FT.

I am trying to match the excel FT (Fourier Transform) of a Gaussian to the analytical FT. My Column A goes from 0 to 4095, column B goes from -2048 to 2047. Column C is: C1=(1/200sqrt(2 pi())) exp(-0....
Ray J's user avatar
  • 13
1 vote
0 answers
26 views

custom FFT library vs FFTW library produce different results for Poisson Solution Spectral Gradient

I am trying out different FFT solvers, with two of them being FFTW (fftw version 3.3.3.8, https://www.fftw.org/index.html) and FAST FFT ( https://www.kurims.kyoto-u.ac.jp/~ooura/fft.html). I am using ...
Christos's user avatar
0 votes
1 answer
39 views

Imaginary components in Discrete Fourier Transform of Gaussian?

I am trying to understand Discrete Fourier Transform (DFT), after only having experience with the continuous transformation. The natural idea was to try to understand DFT on the simplest function, ...
Szgoger's user avatar
  • 153
0 votes
0 answers
25 views

Discrete Fourier transform of repeating values

In this post, I call $\hat{v}\in\mathbb{C}^N$ the Discrete Fourier Transform of $v\in\mathbb{C}^N$ the vector such that: $$ \hat{v}_j = \sum_{k=0}^{N-1} v_k \exp\left(-2i\pi \frac{kj}{N}\right) $$ For ...
G. Fougeron's user avatar
  • 1,614
1 vote
1 answer
187 views

From Fourier series to DFT

A complex function $f(x)$ that is periodic on $[0,2L]$ can be represented as infinite sum of a complex, orthonormal exponential functions that represent the frequencies that reside in $f$. $$ f(x) = \...
Tomer's user avatar
  • 436
1 vote
0 answers
27 views

Frequency ranges of the even and odd term of DFT while developing a FFT algorithm

I'm reading this book: "Theory and application of digital signal processing" by Lawrence R. Rabiner and Bernard Gold. During the development of the classical matrix refactorization used to ...
Sam's user avatar
  • 11
0 votes
0 answers
35 views

Summation interchange in DFT/FFT

Let $x(n)$ be a sequence of length $N = LM, n = 0,\dots,N-1$.$N$ and $M$ are integers. The Discrete Fourier Transform (DFT) of $x(n)$ is given by $X(k) = \sum_{n = 0}^{N-1}x(n)W^{nk}_N$ where $W_N = e^...
Vinod's user avatar
  • 2,233
2 votes
2 answers
130 views

Constant term of generating function to solve special case of Subset Sum Problem

Let the set $S = \{ -n,-n+1,-n+2,\dotsc,-1,0,1,2,\dotsc,n \}$. I want to find the total number of subsets whose sum is equal to 0. There is a simple $O(n^3)$ Subset Sum Problem DP solution that can do ...
Joseph Bendy's user avatar
0 votes
0 answers
17 views

FOURIER TRANSFORM: How can I find the index of data points

I am a senior in high school and am currently trying to conduct an exploration on Fourier Analysis, specifically using the Discrete Fourier Transform to analyze a chord played on my piano. Basically, ...
Ralph Khouri's user avatar
0 votes
0 answers
47 views

Fourier transform of sin, cos, and exponential function

I am using this definitions of Fourier transform. Should there be 1/2\pi factor in the inverse one? \begin{equation} G(\omega) = \mathcal{F}[g(t)] = \int\limits_{-\infty}^{+\infty}g(t) e^{-i \...
Anna-Kat's user avatar
  • 131
0 votes
0 answers
33 views

Is there an alternative to FFT to extract spectral density within specific frequency ranges?

I am looking for an algorithm that allows me to get additional/ consistent information of the low frequency spectral components of a signal. So far I have been using Fast fourier transforms, the issue ...
CesarSurf's user avatar
0 votes
0 answers
22 views

Fast method of finding the unique set of vectors between a set of points on a lattice

I have a list of points that sit on a cubic lattice, where each coordinate is always composed of positive integers. I need to find the set of vectors that that can be taken from any point to any other ...
Industrialactivity's user avatar
1 vote
0 answers
49 views

Fast inverse of a zero-padded multidimensional convolution: extension of the Gohberg-Semencul Formula?

TL;DR: Can the Gohberg-Semencul Formula be extended to invert 2D and 3D zero-padded convolutions? Given a discrete, invertible, zero-padded convolution operation of a 2D image (call this ...
CesiumLifeJacket's user avatar
0 votes
0 answers
54 views

What are some good reference books for signals?

The title might be a bit misleading, but basically I've been self studying differential equations so I could apply them in electronic circuit design. I was wondering what books could be recommended on ...
Arthur Prudius's user avatar
0 votes
0 answers
32 views

Forced damped simple harmonic oscillator

Consider the equation of motion of the following forced dampded simple harmonic oscillator $$\ddot x + \gamma \dot x + \Omega^2x = f (t)$$ where f (t) = e^(iω0t) if |t| ≤ T 0 otherwise ...
Francesca's user avatar
0 votes
1 answer
46 views

Can I just confirm my understanding of the Discrete Fourier Transform and the Inverse Discrete Fourier Transform

I am teaching myself how to write artificial intelligence from scratch including all the math myself I have a pretty solid understanding of a neural network and mine is working fairly well I started ...
The Thinkrium's user avatar
0 votes
0 answers
40 views

How to use cosine transform to quickly solve $f(A)x=b$?

How to fast sovle a matrix linear system $f(A)x= b$, where $A$ is a tridiagonal matrix as: $$ \begin{bmatrix} a & b & 0 & 0 & ... & 0 & 0 & 0 & 0\\\\ c & d &...
Owen Jun's user avatar
0 votes
0 answers
41 views

why is fourier transform of AWGN is of the form complex

This is related to this Nice answer by the thread What is the Fourier transform of $f(x)=e^{-x^2}$?. Considering this derivation of fourier transform of Gaussian with mean 0 and unit variance, why do ...
Vinay's user avatar
  • 1
0 votes
0 answers
28 views

Is there a way to avoid division through size n in ift (ifft)?

Is there a way to avoid division through size n in ift (ifft) ? Performing the Inverse (Fast) Fourier Transform on the complexnumbers, you go with a for loop through every element dividing it through ...
rnnUSer11's user avatar
1 vote
0 answers
26 views

Time complexity of divide and conquer to multiply $n$ linear polynomials using FFT

I know that the time complexity is $$O\left(\sum^{\log_2n}_{k=0}O\left( n\log_2\left(\frac{n}{2^{k}}\right) \right)\right) = O\left( O\left( n(\log_2n)^2 \right) - \sum^{\log_2n}_{k=0}O\left( nk \...
Wei Bin Ang's user avatar
0 votes
0 answers
23 views

FFT Basic Question

I've followed a basic tutorial on FFTs and trying to get my head around what's going on here. As I understand it fourier transform converts from time domain to frequency domain. So in a hypothetical ...
Imme22009's user avatar
  • 125
0 votes
0 answers
119 views

Space complexity of FFT algorithm

It is well known that the time complexity of the FFT is $\mathcal{O}(N\log N)$, but is the space complexity equally well known?
tkykssk's user avatar
  • 39
2 votes
1 answer
102 views

Fast convolution with "small" values

Say we have two sequences of integers $a = \{a_1 \dots a_n\}$ and $b = \{b_1 \dots b_n\}$, where $a_i, b_i \in \mathbb{Z}_q$, but we know some value $p<q$ such that $0 \leq a_i < p$. We want to ...
Sam's user avatar
  • 39
1 vote
1 answer
116 views

Intuition for why the fourier tranform of a polynomial is its pointwise evaluation?

Polynomials in coefficient representation can be multiplied in $O(n \, log \,n)$ time by using a fast fourier transform to convolute the coefficients. The DFT of the coefficients correspond to the ...
pgmcr's user avatar
  • 21
2 votes
0 answers
49 views

Under-damped cosine signal estimation

I have N measurements of an under-damped cosine signal, represented by the equation $$ x(t) = Ae^{-\alpha t} \cos(2 \pi ft) $$ where $ A $ is a known constant. My objective is to estimate the ...
omri meron's user avatar
0 votes
0 answers
46 views

Computing NTTs over Finite Fields with multiplicative order not highly divisible by 2

I've recently been working with Number Theoretic Transforms and have a question I can't work out the answer for. Setup Let $\mathbb{F}_{q}$ be a finite field of prime order $q$ and $q = 2m +1$ for $m\...
ZYouell's user avatar
0 votes
0 answers
66 views

Obtaining weights numerically via a Fourier Transform

I have a particularly nasty function, f(x), and I want to numerically find the values $g_k$ where they are defined as the following. $f(x) = \sum^{\infty}_{k=-\infty}g_k \text{exp}(ikx)$ I want to ...
JustAnotherGuyOnline's user avatar
1 vote
0 answers
42 views

Fast Fourier Transform from interferogram

Fourier transform spectrometers use a device called Michelson interferometer. To understand how this device works, we first consider a monochromatic radiation. This radiation strikes the beam splitter,...
user3713179's user avatar
1 vote
0 answers
38 views

Help with Fast Fourier Transform

Usually I try to post questions when I've already managed to accomplish something with the problem but this time I'm really at a lost in here. The problem goes something like this (sorry for any ...
Omar Munguía's user avatar

1
2 3 4 5
10