# Questions tagged [fourier-transform]

The tag has no usage guidance.

44 questions
Filter by
Sorted by
Tagged with
60 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 ...
16 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. ...
23 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 ...
34 views

76 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 ...
79 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 ...
273 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}$. ...
46 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 ...
4k 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 ...
147 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 -...
990 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 ...
3k 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 ...
738 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). ...
47 views

751 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 ...
209 views

72 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 ...
69 views

171 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 ...
56 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):
2k 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 ...
407 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 ...