The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
23 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 ...
1
vote
0answers
26 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 ...
9
votes
1answer
411 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 ...
0
votes
1answer
49 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 ...
0
votes
1answer
73 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 ...
5
votes
0answers
59 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 ...
1
vote
1answer
42 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):
2
votes
1answer
193 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 ...
0
votes
1answer
49 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 ...
2
votes
1answer
122 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 ...
11
votes
1answer
349 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 ...
4
votes
3answers
935 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?
1
vote
1answer
32 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 ...