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

Is possible to use negative exponents in FFT Algorithm?

I want to apply the FFT to discover all possible sum in two vector. Let's say it's a = [-1,2,3] and b = [4,5]. I wanted to use FFT to find all possible sums, putting the numbers of the vector as ...
1
vote
0answers
39 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
18 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 $\...
0
votes
0answers
5 views

FFT of discretised linear operators

A Fast Fourier Transform can be used to compute DFT coefficients of a periodic function in a $\mathcal{O}(n \log n)$ time. I'm dealing with a problem concerning periodic functions under linear ...
0
votes
0answers
27 views

How accurate is Python's FFT? [closed]

I am getting started with Python's FFT. I tested it on a signal that is a sum of three signals, two of which have an eigenfrequency of the grid, the third one does not (but due to large no. of data ...
2
votes
1answer
114 views

Solving for coefficients of complex Fourier Series

I am trying to prove the formula for the coefficients of the complex form Fourier Series. The context is that I want to be able solve for the constants using numerical integration, like Romberg's ...
0
votes
0answers
15 views

Fast Fourier transform for a sequence of complex numbers with arbitrary size

I want to apply fast Fourier transform for a sequence of complex numbers with length N. N can be anything (not necessarily a power of 2). It seems that Cooley–Tukey algorithm only works for the ...
0
votes
0answers
15 views

Discrete Fourier transform frequency bins

My understanding is that when performing a discrete Fourier transform that the frequency bins are of size $\dfrac{f_s}{N}$ where $f_s$ is the sampling frequency and $N$ is the number of samples. ...
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 $\...
0
votes
0answers
25 views

FFT based Fast Poisson Solver convergence error rate giving an order below of expected

Hello to the stackexchange community. I have been assigned a homework regarding an FFT based Poisson solver. However, I have been struggling with the error of convergence of this method. Before I ask ...
0
votes
0answers
22 views

Why do these PSD differ?

I have a circular 2D convolution (the underlying function $f$ only depends on radius) that I apply to a 2D gaussian white noise map $M$. I am then comparing : the PSD (Power Spectral Density) along ...
0
votes
0answers
15 views

Fast Toeplitz multiplication requires padding with a matrix — what is this “padding matrix” called?

Let $T$ be a Toeplitz matrix of the form: $$ T= \begin{pmatrix} t_d & t_{d+1} & \cdots & t_{2d-1} \\ t_{d-1} & t_{d} & \cdots & t_{2d-2} \\ \vdots & \vdots &\ddots ...
1
vote
0answers
24 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 ...
0
votes
1answer
20 views

scaling magnitude of the dft

I have seen a lot of question like this, but still I have doubts about the answer. When using the fft in matlab the solution need to be divided by the length of the signal (N). I have seen many ...
0
votes
0answers
23 views

Convert overlap save method to multi-bank filter

I want to understand what does mean by mixing bin in this article "Turning Overlap-Save into a Multiband Mixing, Downsampling Filter Bank" and why should the filter length be multiple of decimation ...
0
votes
0answers
22 views

Deconvolution of probability density functions

I am trying to implement a code that yields the probability density function $p(f)$, given knowledge of two other PDFs, $p(\omega)$ and $p(\theta)$. The whole procedure is based on the paper ...
0
votes
0answers
12 views

Which frequency bins give the best interpolation for the derivative of a function?

A function $u:[0,2\pi]\to\mathbb R$ sampled over $N$ equidistant points $\theta_j=(2\pi/N)j,\, j = 0, \dots, N-1,$ can be interpolated by a set of functions $\{u_{k_0}\}$ enumerated by integers $k_0\...
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 ...
0
votes
1answer
56 views

What does the phase data of a Fourier transform represent?

I have written some software which can perform additive synthesis given a set of partials; that is, the frequency, phase and amplitude of a set of sinusoids. The idea is to perform an FFT on some ...
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 \...
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}} $$ ...
0
votes
0answers
8 views

spectral method of 1d wave propagation

As indicated in the: "wave propagation in structures: an FFT-based spectral analysis methodology", by James F. Doyle: For the spectral solution of 1D- elastic wave equation is as follow: $$\widetilde{...
0
votes
0answers
16 views

Fast multiplication of a near Toeplitz matrix

I have a matrix $\bar{\bar {A}}$ which is a Teoplitz matrix of the standard form. This allows a Matrix vector multiplication to be expressed in terms of FFT's if we embed the Toeplitz matrix inside a ...
0
votes
0answers
15 views

How do you change the amplitude of a specific sine wave after applying the FFT to it?

Once I calculate the FFT of a given waveform, how do you change the amplitude of a specific wave or waves before passing it back the IFFT? I understand the imaginary part of the result of the FFT ...
0
votes
0answers
26 views

Amplitude coefficients of discrete, periodic pulses from their Fourier energy coefficients

Concise Summary: This is not a homework question. In short, I'd like to find an algorithm to compute polynomial coefficients that satisfy: $c_{0}$ $=$ $x_{1}^{2}$ + $x_{2}^{2}$ + $\cdots$ + $x_{L}^{...
1
vote
1answer
286 views

Question about roots of unity in the Fast Fourier Transform

I am learning about the Fast Fourier Transform, which converts a polynomial from its coefficient representation into its point-wise form using divide-and-conquer. The Fast Fourier Transform evaluates ...
1
vote
1answer
43 views

FFT-Filter frequency cutoff and negative frequencies

When using a standard implementation for the FFT, for example the numpy implementation, the Fourier transformed output is in so called "standard" order. To quote the numpy implemenetation If $A$ = ...
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 ...
0
votes
1answer
13 views

Siegman Discrete Fourier Transform notation misunderstanding

I was reading A.E. Siegman's Fiber Fourier Optics paper and came across the following equation which was described as the DFT:enter image description here and I don't understand why it's that equation ...
2
votes
1answer
46 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 ...
0
votes
1answer
32 views

Unstable behavior of Discrete Fourier Transform and Fourier Transform alternatives

I have come across a "weird" behavior of the Discrete Fourier Transform (which I will refer to from now as DFT). suppose $$x=(1,-1,1,-1)$$ The real part of the DFT of $x$ is $$Real(DFT(x))=(0,0,4,...
0
votes
0answers
49 views

The value of $\sum_{n=1}^{\infty} \frac{{(-1)}^n}{n^6}$ using the Fourier Transformation

How to compute the sum given in $(1)$, from the fourier transformation of $\pi x |x|-x^3$ over $(-\pi,\pi)$. $$ \sum_{n=1}^{\infty} \frac{{(-1)}^n}{n^6} \tag{1} $$ Suppose we know that $\sum_{n=1}^{...
0
votes
0answers
8 views

Does frequency domain represent distribution of y-axis of Time domain analysis?

I'm wondering how time domain and frequency domain differ in fourier analysis. Converting a vector in time domain to the one in frequency domain refers to Fourier Transform. Is this equivalent to ...
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)...
0
votes
0answers
34 views

Why must the length of a sequence under the discrete Fourier transform be equal to the input sequence length?

Let's consider a continuous signal, $f(t)$, which has been sampled $N$ times, with spacing $T$ between samples. We denote the $N$ samples $f[0], f[1], ..., f[N-1]$. The Fourier transform of the ...
2
votes
1answer
88 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
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 ...
0
votes
0answers
29 views

Problem in Wiener-Khinchin of a discrete signal using matlab

I am trying to calculate the PSD from the autocorrelation using the Wiener Khinchin theorem. In particular I am trying to do this starting from the matlab formula xcorr, which produces an array of ...
2
votes
0answers
45 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 +...
0
votes
1answer
30 views

Shifting phase in Fourier frequency domain

Suppose I have 2 identical Gaussian pulses, but separated by some phase offset. If I take the Fourier transform of it to move from time domain to frequency domain, how can I manipulate the phase terms ...
0
votes
0answers
23 views

psd of a signal using the welch procedure

I have seen that it is possible to calculate the PSD of a signal u , doing this procedure U=fft(u) psd=U*conj(U) Is this the Welch method? can you someone recommend me a book or a paper that ...
3
votes
2answers
56 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 ...
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 ...
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$, ...
0
votes
0answers
51 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$,...
2
votes
0answers
703 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 ...
4
votes
3answers
671 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)^...
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. ...
0
votes
0answers
15 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)$ ...