Questions tagged [fourier-transform]
The fourier-transform tag has no usage guidance.
49
questions
32
votes
2
answers
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
18
votes
1
answer
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
11
votes
0
answers
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
10
votes
1
answer
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
8
votes
4
answers
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
5
votes
9
answers
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
5
votes
1
answer
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
4
votes
1
answer
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 ...
4
votes
1
answer
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 ...
- 43
3
votes
2
answers
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
3
votes
1
answer
234
views
An $O(n)$ algorithm to FFT-evaluate an FFT evaluation
This question is from a practice exam in my algorithms class. I'm posting the question and the answer listed in that practice exam:
Let $W$ be an $n\times n$ matrix whose $(i,j)$-th entry is $\...
- 45
3
votes
1
answer
389
views
Cost of solving a matrix equation using the FFT
I am trying to calculate
$$V = (H^TH+I)^{-1} U$$
where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. ...
- 33
3
votes
2
answers
301
views
Check for common element in two arrays using FFT
My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT).
(I'm aware that ...
- 1,649
3
votes
1
answer
60
views
How is this definition of the quantum Fourier transform to be understood?
In regards to the quantum Fourier transform Page 845 of The Nature of Computation states
The amplitudes $\tilde{a}_\mathbf{k}$ are the Fourier coefficients of $a_\mathbf{x}$,
$$\tilde{a}_\mathbf{...
- 1,058
3
votes
1
answer
3k
views
What the difference between the Fourier Transform of an image and an image histogram?
Consider this small picture of a sunflower, and its histogram:
What would the Fourier transform of the first picture look like? Is there any relationship between the histogram and the Fourier ...
- 41
3
votes
1
answer
238
views
Speed up minimizing quadratic function by FFT
I'm trying to understand the following excerpt from a paper:
Subproblem 1: computing $S$. The $S$ estimation subproblem corresponds to minimizing
$$
\sum_{p}(S_p - I_p)^2 + \beta((\partial_xS_p -...
- 131
2
votes
3
answers
395
views
Could an NP-Hard problem be in P in after a basis transform? [closed]
I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked.
So here goes:
Take the following problem for example:
Let $x[...
- 131
2
votes
2
answers
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
2
votes
1
answer
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
2
votes
1
answer
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
2
votes
1
answer
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
2
votes
1
answer
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
2
votes
1
answer
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 ...
2
votes
1
answer
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
2
votes
0
answers
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
2
votes
0
answers
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
1
answer
221
views
FFT for expanded form of equation multiplication
I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?
For example, if you are multiplying $...
- 233
1
vote
1
answer
65
views
Distribution of random Fourier coefficients
Let $f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$ be a Boolean function. Let the Fourier coefficients of this function be given by
$$ \hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x \cdot ...
- 249
1
vote
1
answer
178
views
How does each element in the output array of a DFT correspond to a specific frequency?
I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of ...
- 111
1
vote
1
answer
1k
views
Difference between the Magnitude and the Phase Spectrum of the Fourier Transform?
What is the difference between the Magnitude and the Phase Spectrum of the Fourier
Transform?
1
vote
1
answer
78
views
What are 'Butterfly Combinations' and why are they called this way?
In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', ...
- 123
1
vote
1
answer
1k
views
How to evaluate all derivatives of a polynomial at a point with FFT? [closed]
I found this problem:
Evaluating all derivatives of a polynomial at a point
Given a polynomial A(x) of degree-bound n, its tth derivative is
defined by
From the coefficient ...
- 45
1
vote
1
answer
77
views
How can you see which points in the spectrum is from which pixel in the original image?
Take the image and spectrum below.
If I look at the spectrum, it just look like noise....
How to make sense of it intuitively?
Image:
Frequency spectrum of image (using Fourier Transform):
- 41
1
vote
0
answers
62
views
Can FFT for prime $n$ be implemented as a product of $O(n\log(n))$ $2\times 2$ unitaries?
Consider normalized DFT (discrete Fourier transform) — a transform with input $x = (x_0,\dots,x_{n-1})$ and output $y=(y_0,\dots,y_{n-1})$ s.t.
$$y_j = \frac1{\sqrt{n}} \sum_{l=0}^{n-1} x_l \omega^{jl}...
- 111
1
vote
0
answers
56
views
Formula for computing a specific Fourier coefficient of a boolean function
According to O'Donnell's book ``Analysis of Boolean Functions", in order to determine the Fourier coefficient of a boolean function $f$ on a subset $S$, we take an inner product of $\chi_S$ and $...
- 11
1
vote
0
answers
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
0
answers
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, ...
user100598
1
vote
0
answers
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=...
- 11
1
vote
0
answers
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
1
answer
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$$
...
- 25
1
vote
1
answer
63
views
Calculating DFT of a specific polynomial
This seems like a simple problem but I'm getting the impression I'm missing something.
The problem
Given the values $v_1, v_2, \ldots, v_n$ such that $DFT_n(P(x)) = (v_1, v_2, \ldots, v_n) $ for $ P(...
- 13
1
vote
0
answers
105
views
finding period using fourier transform [closed]
In the plot squared length of Fourier coefficients vs frequency, the peak gives the strongest frequency. does it give the accurate value of period??
Is it like a single frequency in frequency domain ...
- 41
1
vote
0
answers
76
views
fastest way to compute scalar product of an ensemble of vectors
I have an ensemble of points in 3D space, represented by their coordinates $\mathbf{c_i}\equiv(x_i,y_i,z_i)^\top$ . I need to calculate
the distance between all these points: $\quad\forall i,j\quad ...
- 111
0
votes
1
answer
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
0
votes
1
answer
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 ...
- 1
0
votes
1
answer
115
views
Snowball Question FFT
http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf
I'm confused as to the solution for the snowball question. To start with, I have two specific questions:
(1) Each pair $a_i,...
- 483
0
votes
1
answer
46
views
How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?
I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
- 101
0
votes
0
answers
28
views
Is there a good analogy between spectral representation of a signal and graph theory?
I am working on some time series problems where the Fourier representation of the signal in the frequency domain is also important. I am wondering if there is any connection between time series ...
0
votes
0
answers
117
views
Use of FFT in order to multiply two positive integers of $n$ digits
We're given two positive integers $t$ and $s$ of length $n$ in binary representation.
Suppose we divide the numbers into ${n \over k}$ blocks of size $k=\lg n$
using FFT algorithm.
Suppose ...
- 527