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
1answer
21 views

How to proof the convolution product with the Fourier integral?

One should prove the following: $\mathcal{F}_k^{-1}[\tilde f (k)\tilde g (k)](x)=\frac{1}{\sqrt{2\pi}}(f * g)(x)$ I have absolutely no idea how to solve this exercise. I researched for articles and ...
0
votes
0answers
9 views

Power spectral density (PSD) of a two-dimensional linear stochastic differential equation (SDE) with additive noise

I am considering a two-dimensional linear SDE of the form $$\begin{cases} dX_1 =\bigl(A_{11} X_1 + A_{12} X_2 \bigr)\,dt + \sigma \,dW_1, \\ dX_2 =\bigl(A_{21} X_1 + A_{22} X_2 \bigr)\,dt + \sigma \,...
1
vote
0answers
28 views

power of the DFT matrix

I don't know if it was asked before, didn't find anything using the search. How do I compute the power of the DFT matrix: $DFT^k$ for $k \in \mathbb{N}$ Thank you in advance.
0
votes
0answers
47 views

Understanding of Fourier transform

I have been watching videos from 3Blue1brown guy on youtube. He explains that the fourier transform is an unscaled version of calculating the centre of mass of a graph. ref: https://www.youtube.com/...
0
votes
1answer
62 views

Why is the FFT faster than the naive implementation?

I read several explanations about why the FFT algorithm has the complexity $\mathcal{O}(n \cdot \log(n))$ and not just $\mathcal{O}(n^2)$ like if we directly multiplied the input by the Vandermonde ...
1
vote
0answers
39 views

Is there a way to prove what form the fourier transform of a random variable takes?

Forgive me if any of my terminology isn't right - I come from a physics/stats background, not pure maths. I have a randomly generated time series, which is normally distributed with a mean of $0$ and ...
2
votes
0answers
29 views

Looking for group theory of radix reversal involutions?

From an applied maths background, I'm familiar with (binary) bit-reversal involutions and more generally, radix-reversal involutions when using a mixed-radix counting system. I've become interested in ...
0
votes
0answers
42 views

FFT and flipping bits

First time here asking a question and I have a pretty interesting question. Let's suppose we are having a binary vector $A = [0 1 0 0 1 1]$, and we compute it's FFT to obtain FFT_A. Now let's suppose ...
1
vote
0answers
56 views

Why computing the DFT from the Ricker Pulse isn't the same as the continuous FT function?

Question I'm trying to use Python's scipy library to compute the DFT of the Ricker wavelet function and compare it with the analytical Fourier-transformed version of the same function. When I compare ...
0
votes
0answers
16 views

DFT length and cosines

First merry christmas to all :) Question: DFT length Does the lenght $N$ of the DFT input signal need to be the periodic lenght with $x[n]=x[n+N]$ to to give the right output signal? I mean if I have ...
0
votes
0answers
18 views

address power of polynomial overflow via FFT

I'm interested in all the n-th elementary symmetric polynomials coefficients of some coefficients, and using the FFT approach leads to some strange overflow issue, wondering how can I address them. ...
0
votes
0answers
10 views

what's the operation for element wise product in time domain but from frequency domain?

When doing convolutions in the time domain, normally people do some FFT transformation and perform element-wise product and transform back. Similar to polynomial multiplication, we doing FFT to reduce ...
3
votes
0answers
74 views

Inverse Fourier transform of $\sin^{2} $

Maybe my question is stupid but why the Fourier transform of $ \DeclareMathOperator{\tri}{tri}\sin (f T \pi ) ^{2} $ isn’t $ \frac{1}{T \pi } \tri \big( \frac{t}{T \pi } \big) $ ? if I write the sin ...
0
votes
0answers
21 views

Fourier Transform and its representation

I am not skillful with Fourier Transform, but I think that's an easy question. Consider the function $g(x-y)$. It can be written, using Fourier Transform, as $$g(x-y)= \frac{1}{V} \sum_{k}\hat{g}(k)e^{...
2
votes
1answer
40 views

Prove that $\ f*g = f$

Good morning, We have : $g \in$ $L^{p}(\mathbb{R}^n)$, $\forall p \in [0;\infty)$ and $f\in$ $L^{1}(\mathbb{R}^n)$, $\widehat{f}(x) =0$ if $|x| \geq R $, $\varphi = \widehat{g}$ such as $\varphi(x) =...
2
votes
0answers
52 views

efficient way of calculating the $n-1$ polynomial coefficients

Given $n$ polynomials with the same $M$ degree. $$ A_1 = \sum_{i=0}^M a_{1i} x^i \\ A_2 = \sum_{i=0}^M a_{2i} x^i \\ \cdots \\ A_n =\sum_{i=0}^M a_{ni} x^i $$ My objective is to obtain all ...
0
votes
1answer
29 views

how can I get the fourier transform of this generalized function?

when function f(x) of the generalized function is $f(x) = x+2$, the fourier transform of the generalized function will be like ($F$ is the Fourier transform) $$\int_{-∞}^{∞}(x+2)(F[k(x)])dx$$ when $...
1
vote
2answers
91 views

uncertain orthogonality of discrete Fourier transform on the ring of integers modulo some number

Update: I corresponded with one of the authors of CLRS, and he confirmed that the problem indeed should say "$n$ is a power of two", not "$n$ is even". Original question: CLRS ...
1
vote
0answers
18 views

Complexity of a variant of FFT

To the best of my knowledge, FFT algorithm enables us to compute the matrix-vector multiplication $\boldsymbol{Fx}$ with complexity of $O(N\log N)$ where $\boldsymbol{F}$ is a $N\times N$ Fourier ...
1
vote
0answers
23 views

Does existence of primitive $n$-th root of unity imply $n$ is a unit?

I am studying the fast Fourier transform algorithm in von zur Gathen and Gerard's Modern computer algebra. In it (p. 220), they seem to claim that in a ring with unity where we can apply the discrete ...
1
vote
1answer
38 views

Multiply circulant matrix by usual vector

I found nice way to multiply circulant matrix by a usual vector (page 2): http://web.mit.edu/18.06/www/Spring17/Circulant-Matrices.pdf It means that I can find $\vec{y} = C\vec{x}$ in the following ...
2
votes
0answers
39 views

Eigenvectors of perturbed circulant matrix

I have a circulant matrix defined by a positive kernel W(x): $W_{ij} = W(|i-j|)$ where W is defined on positive reals (so we are sampling {1,2,...,N} to create the matrix). I know this has ...
3
votes
1answer
99 views

Using FFT to calculate derivatives

I know that there are several posts about FFT and derivatives, but i dont get it. The formula is: $$ f(t) \to \hat{f}(\xi), f'(t) \to 2\pi i \xi\hat{f}(\xi) $$ First, i dont understand what is the $\...
1
vote
1answer
35 views

Using Fast Fourier Transform (FFT) to calculate a polynomial and its derivatives at a specific point $x_0$

Those are my homeworks so i prefer a hint and not a full answer I need to use FFT to calculate a polynomial and its derivatives at a certain point $x_0$ at time complexity $O(n\log n)$ Now, i saw this ...
3
votes
1answer
87 views

Numeric calculation of infinite Fourier integral in 2D

Consider a 2D function $f(x,y)$ on $\mathbb{R}^2$, which is finite and decays on some finite interval. I don't have a nice analytical/closed-form expression for $f(x,y)$, but can evaluate it at any $(...
0
votes
0answers
53 views

Parseval theorem on a signal

If I have $ z(t) = x( t - \frac{ T_0 }{4 } ) $ with $ x(t) = rect ( \frac{ t - \frac{T_0}{4} } { \frac{T_0}{2} } $ I obtained that , For parseval theorem , $ Px= Pz = \frac{1}{4} sinc ^{2}( \frac{k}{2}...
0
votes
0answers
28 views

Efficient computation of inner-products involving cosines

Define the following function over vectors $x\in\mathbb{R}^n$: $$ f(x) := \sum_{k=1}^K \cos(A_k x + b_k)^\mathsf{T} c_k $$ where for each $k$, $A_k\in\mathbb{R}^{m\times n}$ is a matrix and $b_k, c_k\...
0
votes
0answers
28 views

How to explain the difference between the FFT result and the analytical Fourier transform?

I am learning FFT by scipy's 'fft'. And now I have the rectangle function as shown below. Its analytical Fourier transform is and its squared absolute value is For performing FFT, I sampled the <...
0
votes
0answers
21 views

Make a divergent exponential convergent

I have a relation which looks like this $$f(\omega) = e^{\alpha \omega} g(\omega)$$ $\alpha$ is a constant, we are working in the Fourier space. I have the values of $g(\omega)$ which is the Fourier ...
1
vote
1answer
20 views

Time average of product of two functions

Suppose the functions $e(x)$ and $h(x)$ with Fourier transforms $E(k)$ and $H(k)$. What is the time average A of $e(x)h(x)$ in function of their Fourier transforms $E(k)$ and $H(k)$? My attempt: \...
0
votes
0answers
37 views

Cumulative downsampling in frequency domain (rather than in time domain)

Given some vector of probability values, e.g. $$\mathit{time\_vec} = \begin{bmatrix}0.1 \\ 0.3 \\ 0.1 \\ 0.1 \\ 0.1 \\ 0.1 \\ 0.1 \\ 0.1\end{bmatrix}$$, I want to downsample the vector by summing ...
0
votes
1answer
65 views

Fourier transform of $e^{-t}u(t)$

I have this signal $ x(t) = \frac{1}{T} e^{- \frac{-(t-T)}{T } } u(t - T ) $ and I found that the Fourier transform is $ X(f) = \frac{ e^{-i \pi 2 f T} e }{ 1 + i 2 \pi f T } $. The correct result is ...
0
votes
0answers
10 views

Analysing periodic information/timings from audio (FFT?)

Lets give a simple example, I have a song that has four notes per measure (1 note per second) If I were playing this through piano, I could easily notice by ear when I am not consistent whether I ...
0
votes
2answers
66 views

Is it possible to represent a sine wave as the sum of multiple sine waves of different frequencies?

I'm working with the FFT, and I've found that it output certain frequencies, but not all. If I input a 440Hz sine wave with 4096 samples, there is no 440Hz response, but instead it's distributed among ...
0
votes
0answers
43 views

Fast Fourier Inversion: Functions of a Complex Argument $f:\mathbb{C} \rightarrow \mathbb{R}$

I'm interested in functions $f: \mathbb{C} \rightarrow \mathbb{R}$ with associated Fourier decompositions $$ f(a + ib) = \int_{-\infty}^{\infty} F(\lambda) \ e^{i \lambda (a + ib)} \ d\lambda.$$ We ...
0
votes
0answers
33 views

Using least squares to extract a Fourier approximation

I am faced with the following problem. I have signal $x_t:\{0,1,N-1\} \rightarrow \mathbb{C}$ where $N$ is very large. I want to compute a few of the Fourier coefficients say for example:$\hat{x}_0, \...
1
vote
0answers
13 views

When do multiply/divied the $\text{fft}$ in $\text{Matlab}$?

I am currently trying to wrap my head around calculating the $\text{DFT}$ in $\text{Matlab}.$ So far as I understood, the standardization by $\frac{1}{N}$ is done by the $\text{fft}$ function itself. ...
0
votes
0answers
32 views

Inverse Fast Fourier Transform in Matlab

I have a function to invert $\hat{f}(\omega)=-\dfrac{i}{\sqrt{2\pi}\,\omega}$, but I am not sure why this is not coded correctly. So the inverse is supposed to be $f(x)=-\text{Sign}(x)/\sqrt{2}$ but ...
0
votes
0answers
16 views

Write formular to draw an image

I am trying to write a program to produce a formula that draws an image like Einstein curve Einstein curve I found a blog explained what I should do but I do not really understand Mathematica that he ...
0
votes
0answers
20 views

Correlation via FFT for different image sizes

Right now I am trying to match a small template image to a bigger one to see where the correlation is the highest. I know that I can compute this by filtering the big image with a filter comprised by ...
0
votes
0answers
22 views

Fourier Series Equivalent for Triangle waves

Is there an equivalent of the Fourier Series except it computes a series of Triangle waves of various magnitudes as oppose to sine waves, that summed together form a particular function / data set?
0
votes
0answers
30 views

More information about Circulant matrix diagonalized in the Fourier basis

I read that a circulant matrix $C$ can be written as $F \phi F^{-1}$ where $\phi$ are $C$'s eigenvalues. Can someone give me more information about the $F$ matrix? Will it be the same for any ...
3
votes
1answer
58 views

Smallest integer greater than or equal to another integer but with prime factors less than or equal to 7

More clearly stated than title, let $n \in \mathbb{N}$ and $A = \{m \in \mathbb{N} : m \geq n \text{ and } m = 2^a 3^b 5^c 7^d \text{ for some } a,b,c,d \in \mathbb{N}\}$. Find $\min(A)$. This can be ...
0
votes
1answer
13 views

Method of weighted residuals: formulation of spectral derivative

I have read Philipp Schlatter's Lecture Notes: Spectral Methods in 2010. A hyperlink is provided below. Lecture Notes: Spectral Methods At Page 2, Eq. $(3)$ in this notes, the author have written the ...
1
vote
1answer
59 views

Fourier transform of $e^{-at}u(t-b)$

I have this signal $ s(t) = e^{- \frac{t}{RC} } [ u(t) - u(t - T_c) ] $ and I have to calculate the Fourier transform. I obtained $$ S(f) = \frac{ RC( 1 - e^{-i2 \pi f T_c } )}{1 + i 2 \pi f RC } $$ ...
0
votes
0answers
17 views

How to uniquely identify a composite wave?

I'm trying to write a little python snippet that stores 'wave' objects. For simple sinusoidal waves I identify my wave objects uniquely by frequency, phase and amplitude. However, I also want to store ...
4
votes
1answer
50 views

Basic question about fast Fourier transforms.

If I consider the function $\sin(t)$ evaluated between 0 and 60 (seconds) with $\Delta t = 0.01$. When I take the fast Fourier transform, the frequency of oscillations can be obtained directly of $$f =...
1
vote
1answer
145 views

Solving a simple differential equation with DFT

I have a simple differential equation of form $\frac{df(x)}{dx}=u(x)$ and u(x) is given to me in a sampled form so I need to solve this equation numerically. I decided to do this via DFT and I came up ...
0
votes
0answers
12 views

Extending fast fourier transform to spin spherical harmonic basis

I have a function that is a a Fourier transform of a product $\bar{T}(\vec{x})\partial_{\langle{i}}\partial_{j\rangle}\bar{T}^{F}(\vec{x})$ contracted with ${k}^{\langle{i}}{k}^{j\rangle}$, with the ...
1
vote
1answer
38 views

Advantage of fast Fourier transform in programming

Someone asked me about the advantage(s) of fast Fourier Transform in civil engineering programs?! or What is the application of the Fourier series in engineering programming? Can you help me or give ...

1
2 3 4 5
7