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