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

322 questions
Filter by
Sorted by
Tagged with
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 ...
9 views

40 views

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

53 views

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 <...
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 ...
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: \...
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 ...
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 ...
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 ...
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 ...
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 ...
33 views

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