Differences

This shows you the differences between two versions of the page.

--- math105-s22:s:jianzhi:start [2022/04/28 02:58]
jianzhi [FFT, Wavelet Transformation, Uncertainty Principle (The Last Presentation)]
+++ math105-s22:s:jianzhi:start [2026/02/21 14:41] (current)
@@ Line 719: / Line 719: @@
 **Discrete Fourier Transform**
-The discrete Fourier transform (DFT) converts a sequence of $N$ numbers $x_0, ..., x_{N-1} \in \mathbb{C}$ to a new sequence of $N$ numbers $X_1, ..., X_{N-1} \in \mathbb{C}$, given by: $X_k = \Sigma_{n=0}^{N-1} x_n e^{\frac{-2 \pi ikn}{N}}$
+The discrete Fourier transform (DFT) converts a sequence of $N$ numbers $(y_j)_{j=0}^{N-1} = (y_0, ..., y_{N-1}) \in \mathbb{C}$ to a new sequence of $N$ numbers $c_0, ..., c_{N-1} \in \mathbb{C}$, given by: $c_k = \Sigma_{j=0}^{N-1} y_j e^{\frac{-2 \pi ijk}{N}}$
-Think of $x_i$ as the values of a function or signal at equally spaced times $t = 0, ..., N - 1$. The output $X_k$ encodes the amplitude and phase of $e^{\frac{2 \pi ikn}{N}$. Key idea: approximate the signals by a linear combination of waves that has wavelength that are an integer factor of $N$.
+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 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, $e^{\frac{2 \pi ikn}{N}}$, $k = \frac{2\pi ik}{N}$, hence a wavelength of $\lambda = \frac{N}{k}$.
+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
 {{:math105-s22:s:jianzhi:screenshot_2022-04-27_at_7.52.07_pm.png?400|}}
+For the encoding of signals, suffices to solve a system of linear equations. Hence, introduce the //Vandermonde Matrix for roots of unity//
-Compute $X_k$ to find the coefficients of an approximation of the signal by a linear combination of such waves. Since each wave has  of cycles per N time unit, approximation will be periodic with period N.
+{{:math105-s22:s:jianzhi:screenshot_2022-04-27_at_9.37.14_pm.png?400|}}
-Vandermonde Matrix for roots of unity
+Suffices to matrix multiply the Vandermonde matrix for roots of unity with the signal vector.
-$\begin{bmatrix}
+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.
-   a & b \\
-   c & d
+**Fast Fourier Transform**
-\end{bmatrix}$
+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.
 **Inverse Fourier Transform**
-$x_n = \frac{1}{N} \Sigma_{k=0}^{N-1} X_k e^{\frac{2 \pi ikn}{N}$
+$y_j = \frac{1}{N} \Sigma_{k=0}^{N-1} c_k e^{\frac{2 \pi ijk}{N}}$
-Many applications comes from encoding a signal:
+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:screenshot_2022-04-27_at_9.37.22_pm.png?400|}}
+**Applications**
+Many applications come from the ability to encode a signal:
   - Digital files can be shrunk by eliminating contributions from the least important waves in the combination.
   - Comparing different sound files by comparing coefficients $X_k$ of DFT.
   - De-noising radio waves
+**Wavelet Transformation and the Uncertainty Principle**
+The problem with Fourier Transform is that it produces a periodic function over the whole space. What if we just want a localized wave? This is so called a "wavelet".
-Fast Fourier Transform
+A function $\psi:\mathbb{R} \rightarrow \mathbb{C} \in L^2(\mathbb{R}$ (square integrable functions i.e. $\int_{-\infty}^{\infty} |\psi|^2 < \infty$) is said to be an //orthonormal wavelet// if it can be used to define a //Hilbert basis//.
-Wavelet Transformation
+The Heisenberg Uncertainty Principle from Physics states: $\Delta E \Delta t \geq \frac{\hbar}{4\pi}$. Translated to signal processing, that becomes $\Delta \omega \Delta t \geq \frac{1}{2}$. Intuitively, it means we cannot measure and clearly resolve both the frequency and the time to a very large degree.
-Uncertainty Principle
+**References**
+  - https://brilliant.org/wiki/discrete-fourier-transform/
+  - https://en.wikipedia.org/wiki/Wavelet_transform

Lecture Notes

User Tools

Site Tools

Differences

Page Tools