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.

220 questions
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 ...
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/...
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$...
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 ...
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 ...
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 ...
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 ...
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 [-...
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{...
25 views

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 ...
97 views

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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
128 views

Understanding FFT through Matlab.

Suppose, I have the following matrix which represents a grayscale image in the spatial domain, ...
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 ...
49 views

How to fit points using fft

Say I got a data of several points, for example: ...
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 ...
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)$ ...
88 views

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 ...
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 ...
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 ...
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$$ ...