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.

0
votes
1answer
282 views

Fourier transform in spherical coordinates from a Cartesian grid

Recently I realized I didn't understand what FT is, which is embarrassing after years of training. However, I don't get what the basic Fourier integral means. To make it concrete, let's assume I ...
0
votes
1answer
114 views

Complexity of Cooley Tukey FFT

http://www.jstor.org/stable/2003354?seq=5#page_scan_tab_contents In the original algorithm of Cooley Tukey it says that in page 298 (11) and (12) the total number of operations is T(r) = rNlogN/...
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
1answer
308 views

Parseval identity in FFT

I was recreating in Matlab a certain function using FFT. In particular I was interesting in knowing how modes are sufficient to approximate quite well my function. To do that, I calculate the norm ...
0
votes
1answer
355 views

Derivatives using fft in Matlab

I have been used matlab for two weeks and I start to appreciate its power. At the moment I am studying Fourier series in order to solve PDEs. The exercise below asks me to find the derivate of a ...
1
vote
1answer
103 views

Approximate Factorization of a Natural Number

I'm implementing the Cooley-Tukey algorithm for computing Discrete Fourier transforms. It so happens that it breaks down a problem of size $n = pq$ into $p$ chunks of size $q$. Given that factoring ...
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 ...
0
votes
1answer
136 views

Which are the wavenumbers for the fast Fast Fourier Transform?

I am having a similar problem to the one discussed here: Computing wavenumbers for discrete Fourier transform Say I performed a FFT on $N = 256$ points, are my wavenumbers indexed as [-128,127] or [-...
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{...
0
votes
0answers
25 views

is there special FFT technique for function of angle argument?

I started working with molecular modelling and stuck at the following problem. I need to calculate dihedral interaction energy by hand. The simplest form of the equation is $V = \frac{Va}{2} * \left( ...
0
votes
0answers
66 views

Fast Fourier Transform in C

I have a time domain data of an electric field(windowed) at a point, say $(x,y)$. The time is around 33 picoseconds and sampled at 20,000 points. To convert this data to frequency domain I am using ...
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
1answer
200 views

Compute $N! \ \mathrm{mod}P$ , where $N<=10^9$ and $P=10^9+7$, where $N!$ is $N$ factorial

I have seen several web pages which mention that this task can be done efficiently using FFT. But, I didn't find any reliable source which can help me understand the process underneath. It will be ...
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 ...
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)=\...
0
votes
1answer
162 views

Fast fourier transform

In fast fourier transform, what are the square and the square root of $\omega_{128}$, the primitive 128th root of 1? Is it possible for you to help me on this one?
1
vote
3answers
51 views

What is $\sin(\frac{\pi}{2}-\frac{n\pi}{2})$ equal to?

I'm having huge trouble with figuring out fourier series as soon as I'm not dealing with a really simple function. I found a solution to my problem (fourier series for $|cos(x)|$, I'm troubled by the ...
0
votes
1answer
77 views

Fourier Transform Scaling the magnitude

I have a set of signals $S_1,\dots,S_N$, for which I am numerically computing the Fourier transforms $F_1,\dots,F_N$. Where $S_i$'s and $F_i$'s are C++ vectors (my computations are in C++). My ...
1
vote
0answers
559 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 ...
0
votes
0answers
177 views

DFT Shift theorem

I am building a home power meter to use in my house. I sent my board to be manufactured that's why at the moment I am simulating an AC power line and applying an FFT in order to calculate all the ...
0
votes
0answers
225 views

FFT with nonsquare matrix

I want to compute the $K$ sums: $$ f_k = \sum_{j=0}^{N-1} a_j e^{i \frac{2 \pi j k}{K}} $$ for $f_0,f_1,...f_{K-1}$. Now if $K = N$, then this is the usual DFT, but in my application $K \ne N$, as I ...
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 ...
0
votes
2answers
522 views

Fourier transform delayed heaviside function : sinc-like output

When I fourier transform (FFT) a (delayed) Step funciton (Heaviside function) I get frequency spectrum that follows a very sinc-like pattern, see figure below (showing the asbolute value of the FFT) ...
0
votes
2answers
128 views

Understanding FFT through Matlab.

Suppose, I have the following matrix which represents a grayscale image in the spatial domain, ...
2
votes
2answers
94 views

What area's of mathematics are needed to make a basic understanding of the FFT algorithm ?

I know FFT is used in signal processing ( at last check), the Lucas-Lehmer Test and probably many other things. But what is the Fast Fourier Transform and what area's of math will help me understand ...
0
votes
1answer
49 views

How to fit points using fft

Say I got a data of several points, for example: ...
0
votes
1answer
266 views

why fft2 of a hermitian matrix gives complex result

for a Hermitian matrix $$A = \left[\begin{array}{ccc}2& 2+i& 4\\ 2-i& 3& i\\ 4& -i& 1\end{array}\right]$$ the result of matlab fft2(A) is a complex matrix instead of a real ...
0
votes
1answer
33 views

If two PSDs are related, are the PDFs of the time-series related?

Suppose a power spectral density (PSD) is related to another PSD by a function $\alpha(\omega)$. $$S_a(\omega) = \alpha(\omega)S_b(\omega)$$ If we generate an ensemble of time-series $x_a(t), x_b(t)$ ...
0
votes
0answers
88 views

The fastest algorithm to calculate the $C^n$

I am looking for the fastest algorithm to calculate the $$C^n$$ where the $C$ is some algebraic constant. For example it can be $$C=\frac{\sqrt3-1}{2}$$ or one of the root of $$x^5+x^2-1=0$$ If $$C=...
1
vote
0answers
82 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
148 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 ...
0
votes
0answers
70 views

Discorrespondence between Continous Fourier Transform and Discrete Fourier Transform

My goal is to use a deconvolution method to extract a desired signal (delta peak) out of a convoluted measured function. My problem at first concerns the discrete Fourier Transform (DFT) or FFT ...
1
vote
0answers
17 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
1answer
30 views

Why this time-frequency representation of a pure sine function with Stockwell Transform is different in the boundary?

This time-frequency decomposition was made with Stockwell Transform to a pure sine function and graphed with matlab. But as you can see in the boundary of the image the pattern is different. I need to ...
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 ...
2
votes
1answer
115 views

How to get the frequency of a time-domain signal with limited sample length?

Let's say there is a signal who only has one peak in its power spectrum. I would like to know the frequency at which the peak is (the magnitude of power is not important to me). But I only have very ...
0
votes
1answer
40 views

Fourier transformation formula confusion

I found two formulas for Fourier transformation , which one is correct. $$ F[f(x)]=\frac {1}{\sqrt {2\pi}} \int_{-\infty}^\infty f(x)e^{ipx} dx $$ $$ F[f(x)]= \int_{-\infty}^\infty f(x)e^{ipx} dx $$ ...
0
votes
0answers
564 views

Using FFT to efficiently multiply multiple polynomials modulo N

I have a set of polynomials $P_k$ defined as: $$ P_k = \sum_{n = 0}^{n = N} p_{kn} x^n $$ $N$ is large ($2^{16}$) I would like to perform multiplication on the polynomials: $$ Q = \prod_{k=0}^{k=K}...
1
vote
1answer
188 views

Create a graph of dominant frequencies at each point in time in signal?

I have a signal that varies in frequency and amplitude, and I want to create a moving window that takes a number of samples, finds out the "dominant frequency" in the window using FFT, and stores the ...
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
1answer
73 views

If $y$ is the $DFT$ of a real sequence $x$ of length $n$; where $n$ is a power of two, show that $y_0$ and $y_{n/2}$ must be real.

If $y$ is the $DFT$ (Discret Fourier Transform) of a real sequence $x$ of length $n$; where $n$ is a power of two, show that $y_0$ and $y_{n/2}$ must be real. I have no idea how to answer this ...
0
votes
1answer
265 views

Trying to show that columns of Fourier matrix are eigenvectors

I posted a picture since the syntax for this one seems quite complex: I found this: Discrete Fourier Transform - proof that columns of matrix are orthogonal which only shows that are orthogonal. In ...
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 ...
0
votes
2answers
45 views

Sample equally a set of discontinuous points

Suppose I have a vector $a=[0, 0.3, 1]$ with amplitudes $A=[0, 1, 0]$ and I want it sampled, equally-spaced, with $N=8$ samples from $a[0]=0$ to $a[2]=1$. If I only keep count of $0$ and $1$, the ...
1
vote
1answer
343 views

Is the DFT really the DTFS?

In the continuous domain, I know that the Fourier Series is given by: $$x(t)=\sum_{k=-\infty}^{\infty}c_ke^{j\frac{2\pi}{T}kt}$$ So in the discrete domain, it would make sense that a discrete N-...
1
vote
1answer
261 views

Convolution of function with singularity

I want to numerically evaluate a convolution that contains the function $$f(t) = \dfrac{1}{e^{t}-1},$$ like $$h(t) = f(t) \circ g(t)$$ where $g(t)$ is a smooth well-behaved function that converges ...
0
votes
1answer
205 views

What is the correct order of DFT values when executing the DIT FFT algorithm?

I was checking the correctness through SageMath (and later through Wolfram Alpha and Mathematica) of some simple whiteboard computations that I've done manually (namely, I have tried to compute the ...