3
votes
1answer
37 views

Image Reconstruction:Phase vs. Magnitude

Figure 1.(c) shows the Test image reconstructed from MAGNITUDE spectrum only. We can say that the intensity values of LOW frequency pixels are comparatively more than HIGH frequency pixels. $$ ...
2
votes
1answer
74 views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
0
votes
2answers
39 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
2
votes
1answer
142 views

Why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $N \log N$?

As the title says, why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $O(N \log N)$? This is a famous open problem in ...
7
votes
1answer
218 views

A Mathematical way to represent a image kernel?

How to represent the calculation in this image mathematically? For example: With the discrete convolution and Fourier Transform. It tries to do a calculation on the original image (image A/input) ...
0
votes
0answers
457 views

Convolution between a kernel and an image with FFT

In the FFT2D paper (Fast Fourier transform used for a convolution with a kernel in the frequency domain), I'm lost at the second page first picture: ...
1
vote
2answers
293 views

Cooley-Tukey Algorithm?

Why does the Cooley-Tukey Fast Algorithm take $O(n \log n)$ time? The book derives this from the fact that evaluation takes time: $T(n) = 2T(n/2) + O(n)$ and then uses the Master Theorem to arrive ...
1
vote
2answers
257 views

Understanding Matrix Formula with Scant Knowledge of Linear Algebra

$n$ is a power of $2$. $M =\pmatrix{ 1& x_0 & x_0^2 & \dots &x_0^{n-1}\\\ 1& x_1 & x_1^2 & \dots &x_1^{n-1}\\&& \vdots\\1& x_{n-1} & x_{n-1}^{2} ...
4
votes
2answers
1k views

Advice for how to learn more advanced math for audio signal processing?

I am very interested in learning about audio from a signal processing standpoint. However, whenever I try to further my education by reading books, I get extremely frustrated because the books use ...