# Questions tagged [fourier-transform]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
24k views

### Show how to do FFT by hand

Say you have two polynomials: $3 + x$ and $2x^2 + 2$. I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how ...
• 483
4k views

### FFT-less $O(n\log n)$ algorithm for pairwise sums

Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$. We are interested in finding the counts of all the ...
• 6,281
186 views

### (Slightly) faster simulation of quantum Fourier transform

Suppose I want to write a classical software simulator of a quantum circuit with $N$ qubits. When it comes time to simulate the quantum Fourier transform I can evaluate all $2^N$ states to determine ...
• 17.8k
5k views

### Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?

Karlheinz Brandenburg depicts a MP3 encoder like this: Source: MP3 and AAC Explained I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the psychoacoustic ...
• 203
5k views

### How does the Stockham FFT work?

I'm trying to implement a Fourier transform in an OpenGL shader. I found some literature that explains the general principles, but is a bit sparse on some details. And those details are seriously ...
• 81
19k views

### Explaining why FFT is faster than DFT for the general public?

How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?
• 585
922 views

### Pruned FFT runtime

Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). ...
• 201
3k views

### Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
168 views

### Calculating force between n points placed on the x-axis

There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$. We need to calculate the force on each charge by every other charge. I need the exact force. Charges can be arbitrary. Inputs are ...
935 views

### Morgenstern proof for FFT lower bound

I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses ...
• 173
234 views

• 131
97 views

### Expected Behavior of FFT

I am debugging an FFT. My FFT uses complex numbers in polar form, $(r,\theta)$. I am trying to establish that it works, with a unit test. My real values are all correct, after a polynomial ...
• 229
319 views

### How to distinguish between the different frequency domains?

Sometimes the terms 'Fourier domain', 'complex frequency domain', 'Frequency domain' and 's domain' are used interchangeably. Take these answers here for example. Can you really use them ...
• 585
313 views

### What is the reason that is FFT multiplication slower than other methods for small N?

I've seen plenty of statements in papers and on websites that Fast Fourier Transform-based multiplication algorithms are slower than other multiplication algorithms for relatively small input size N, ...
• 211
47 views

### What's the connection between the two "Fast Walsh Transform"?

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
• 229
538 views

### Confusion related to time complexity of fast fourier transform

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT. It says that lets say I have a polynomial of ...
• 299
2k views

### What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them?

Starting with an image, I have taken its fourier transform and then modified it, and finally taken the inverse fourier transform of the modified fourier transform to get my resulting image. In my ...
1k views

### Compare phase and magnitude spectrum results of 2 Images

I have read that from Fourier transform we obtain magnitude and phase spectrum. The magnitude spectrum tells you how strong are the harmonics in a image and the phase spectrum tells where this ...
• 121
32 views

### Fast calculations using fast-Fourier convolution

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$. We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by ...
• 151
65 views

### generalized translation operator on graph [closed]

David IShuman in " vertix-frequency analysis on graph" claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply ...
1 vote
221 views

1 vote
22 views

### Fourier Transform of t/(t^2+1)^2

Can you help me with what steps to follow to find the Fourier transform of t/(t^2+1)^2. I know it will be solved on the lines of time-frequency duality but cannot seem to get the exact steps for it. ...
• 11
1 vote
313 views

### Understanding the recursive fast Fourier Transform Algorithm from CLRS

Consider the following recursive fast Fourier transform algorithm from CLRS: I believe that I understand this algorithm correctly: you split the input coefficients into the odd and even terms, ...
1 vote
45 views

### Need help implementing an algorithm to solve roots of a transcendental equation

I'm trying to implement this algorithm but I'm having problems reproducing the exemple that it gives a solution to. The general method that I tried is: Make a grid $\theta \in [0,2\pi)$, with say N=...
1 vote
40 views

### What is the runtime of Quantum Fourier Sampling

I have seen estimates for the runtime of Shor's Algorithm,, which relies on Quantum Fourier Transformations. What is the runtime of those transformations themselves? Either big-O or more accurate ...
• 115
1 vote
96 views

### Efficiently compute parallel matrix-vector product for block vectors with FFTs?

Assume I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product $$w = (E\otimes I_N)v$$ ...
1 vote
63 views

• 111
543 views

### Intuitive way to understand the triangle spectrum?

Image on the top is in the time domain, image on the bottom is in the frequency domain. Why do we see -2T and 2T on image of the time domain and why do we see -1/2T and 1/2T of the image in the ...
• 585
43 views

### 2D fourier transform

I an new to image processing and I have some questions I want to understand: What is the meaning of the imaginary and real part of the 2d fourier transform? What can it tell me about the image it ...
115 views

• 527