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

168 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
90 views

### Determine the shift in tonal center of a piece of music.

Starting with a sampled audio signal of acapella vocals, I am interested in determining the shift in the tonal center of the music through the performance. As a choir progresses through a ...
61 views

### Translation of the work of Gauss where the fast Fourier transform algorithm first appeared

As far as I know, the fast Fourier transform algorithm first appeared in 1805 in "Theoria interpolationis methodo nova tractata", by Carl Friedrich Gauss. This work is available in Latin, which, to ...
38 views

### Does the fast Fourier transform have equivalents in other transforms?

I've seen the Mellin transform described as the "multiplicative" analogue to the Laplace transform, as well as the Fourier transform when $x\to\log y$. Would a discrete Mellin transform be able to ...
123 views

### How to compute $p(x)=\prod_{k=0}^{n-1}(x-z_k)$ using the FFT with complexity of O(nlog^2 n)?

I've a question and in its last step I'm required to find the above product (I need the coefficients of the result of that product as my final answer). It seems that FFT can be used to compute it. I ...
117 views

### How to decompose a 2d shape into sin and cosin modes?

Assume that you have a circle with radius $r_0$, then you keep adding cosine modes as below: $r=r_0+a_1\cos(1\theta)+a_2\cos(2\theta)+a_3\cos(3\theta)+a_4\cos(4\theta)+~...$ if you plot this as ...
26 views

### DFT and inverse problem

Let two functions $I,J:\{0,1,\ldots,n\}\times \{0,1,\ldots,m\} \mapsto \{0,1,\ldots,p\}$ and $h$ a $v\times v$ matrix ($v\ll n,m$) such that $$J = I * \underbrace{h*\ldots *h}_{p \text{ times}}$$ ...
133 views

### Bandlimited reconstruction of sampled periodic functions.

This has to do with the Nyquist-Shannon sampling and reconstruction theorem and the so-called Whittaker–Shannon interpolation formula. I had previously asked an ancillary question about this here but ...
43 views

### Quantify measure of oscillations in periodic time series data

I have a periodic time series data that are constantly sent to server from machines. It has uneven sampling rate. I want to quantify measure of oscillations by combining information about frequency +...
52 views

### DFT is not a sampling of FT?

From wikipedia: The discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time ...
52 views

### Any Efficient Multiplication with a Primitive Root over Prime Field?

Description: to multiply the "complex unit" $w^{N/4}$ over a prime field, i.e., $w^N \equiv 1 \bmod (\,p)$ (suppose $p, N$ do provide such primitive root). I am implementing the radix-4 Number ...
31 views

### Increasing frequency resolution of FFT on a windowed sample of a signal

Okay, this gets a bit technical, let me explain the background. In doing loudspeaker measurements for its direct sound in normal rooms that have reflections, what we do is measure the whole impulse ...
325 views

### Efficient matrix-vector multiplication for “partial” Hadamard matrices

I've recently been working on an algorithm for bilinear systems in the form $y = (Lw) \odot (Rx)$, where $\odot$ denotes the elementwise product between two matrices of compatible sizes. In the above, ...
110 views

### Discrete versions of the Fourier Slice-Projection Theorem

I understand the continuous version of the Fourier Slice-Projection theorem, which says that given a (nice enough) function $f:\mathbb{R}^3\to\mathbb{C}$ the following operations give the same result: ...
236 views

### Unable to solve nonlinear equation using scipy.optimize.fsolve

I am using scipy.optimize.fsolve to solve a nonlinear equation in Fourier pseudospectral space but it does not work. It gives the same output as the input u0, which is a trivial solution. The equation ...