math105-s22:s:jianzhi:start
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
math105-s22:s:jianzhi:start [2022/04/28 04:45] jianzhi [FFT, Wavelet Transformation, Uncertainty Principle (The Last Presentation)] |
math105-s22:s:jianzhi:start [2026/02/21 14:41] (current) |
||
|---|---|---|---|
| Line 723: | Line 723: | ||
| Think of $(y_j)$ as the values of a function or signal at equally spaced times $x = 0, ..., N - 1$. The output $c_k$ encodes the amplitude and phase of $e^{\frac{2 \pi ikx}{N}}$. Key idea: approximate the signals by a linear combination of waves that has wavelength that are an integer factor of $N$ i.e. all such waves has wavelength that are an integer | Think of $(y_j)$ as the values of a function or signal at equally spaced times $x = 0, ..., N - 1$. The output $c_k$ encodes the amplitude and phase of $e^{\frac{2 \pi ikx}{N}}$. Key idea: approximate the signals by a linear combination of waves that has wavelength that are an integer factor of $N$ i.e. all such waves has wavelength that are an integer | ||
| - | Normally, we know the wave equation as $y(x) = cos(kx) + i\cdot sin(kx) = e^{ikx}$ where $k = \frac{2\pi}{\lambda}$ is t; $\lambda$ is the wavelength. | + | Normally, we know the wave equation as $y(x) = cos(kx) + i\cdot sin(kx) = e^{ikx}$ where $k = \frac{2\pi}{\lambda}$ is the wavenumber; $\lambda$ is the wavelength. |
| Hence, the wave corresponding to $c_k$, which is $e^{\frac{2 \pi ikx}{N}}$ has wavenumber $k = \frac{2\pi ik}{N}$, thus it has a wavelength of $\lambda = \frac{N}{k}$. Suffices to compute $c_k$ to find the coefficients of an approximation of the original signal $(y_j)_j$ by a linear combination of the waves | Hence, the wave corresponding to $c_k$, which is $e^{\frac{2 \pi ikx}{N}}$ has wavenumber $k = \frac{2\pi ik}{N}$, thus it has a wavelength of $\lambda = \frac{N}{k}$. Suffices to compute $c_k$ to find the coefficients of an approximation of the original signal $(y_j)_j$ by a linear combination of the waves | ||
| Line 737: | Line 737: | ||
| Remark: This problem is also equivalent to evaluating a polynomial at the roots of unity, the so-called changing from coefficient representation to value representation. | Remark: This problem is also equivalent to evaluating a polynomial at the roots of unity, the so-called changing from coefficient representation to value representation. | ||
| - | **Fast | + | **Fast |
| A naive implementation of the Discrete Fourier Transform takes $O(N^2)$. However, Fast Fourier Transform performs it in $O(N log N)$ by exploiting the symmetry of the roots of unity. | A naive implementation of the Discrete Fourier Transform takes $O(N^2)$. However, Fast Fourier Transform performs it in $O(N log N)$ by exploiting the symmetry of the roots of unity. | ||
| - | An illustration of idea is: break down the polynomial into even and odd terms. We can recycle many computations. Use 1 and -1 as an example. | + | An illustration of idea is: break down the polynomial into even and odd terms. We can recycle many computations. Use $1$ and $-1$ as an example. |
| **Inverse Fourier Transform** | **Inverse Fourier Transform** | ||
| - | $y_j = \frac{1}{N} \Sigma_{k=0}^{N-1} c_k e^{\frac{2 \pi ijk}{N}$ | + | $y_j = \frac{1}{N} \Sigma_{k=0}^{N-1} c_k e^{\frac{2 \pi ijk}{N}}$ |
| The trick here is to notice that the inverse matrix is just another Vandermonde matrix with $\bar{\omega}$ instead of $\omega$. | The trick here is to notice that the inverse matrix is just another Vandermonde matrix with $\bar{\omega}$ instead of $\omega$. | ||
math105-s22/s/jianzhi/start.1651121120.txt.gz · Last modified: 2026/02/21 14:43 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
