---
# System prepended metadata

title: Fourier and Wavelet Transform
tags: [AI]

---

---
tags: AI
---
# Fourier and Wavelet Transform

---

### Giới thiệu (Introduction)

- Bài toán: Từ các phương trình $\to$ chuyển đổi thành một hệ tọa độ mà các biểu thức được đơn giản hóa và tách rời cho tính toán và phân tích.
- Ý tưởng: Fourier đưa ra khái niệm rằng các hàm **sin** và **cosin** của tần số tăng dần cung cấp cơ sở trực giao (orthogonal basis) cho không gian của các hàm nghiệm.

---

### Ứng dụng (Application)

- Lý thuyết xấp xỉ (approximation theory)
- Nén hình ảnh và âm thanh theo thời gian thực (real-time image and audio compression) nhờ vào fast Fourier Transfrom
- Xử lý dữ liệu nâng cao (advanced data analysis)
- Xử lý và nén tín hiệu nâng cao (advanced signal processing and compression) nhờ vào các hàm biến đổi wavelets

---

## Chuỗi Fourier và Biến đổi Fourier (Fourier Series and Fourier Transform)
- Giải thích dưới dạng hàm liên tục (continuous functions)
- Giới thiệu các khái niệm liên quan như không gian hàm (function space) hay degrees of freedom

----

### Tích vô hướng của hàm và vectơ (Inner products of functions and vectors)

Tích vô hướng của $f(x)$ và $g(x)$ (liên tục - continuous) xác định bởi $x$ trong miền $\lbrack a, b \rbrack:$
$$\langle f(x), g(x) \rangle = \int_{a}^{b} f(x)\bar{g}(x)dx$$

----

Khi tách $f(x)$ và $g(x)$ thành các vectơ dữ liệu (discretize), ta muốn tích trong vectơ hội tụ thành tích trong của hàm khi độ phân giải lấy mẫu (sampling resolution) tăng lên. Tích vô hướng của vectơ dữ liệu $\mathbf{f} = \lbrack f_1 \enspace f_2 \enspace \dots \enspace f_n \rbrack ^ \top$ và $\mathbf{g} = \lbrack g_1 \enspace g_2 \enspace \dots \enspace g_n \rbrack ^ \top$ là:

$$\langle \mathbf{f}, \mathbf{g} \rangle = \mathbf{g} * \mathbf{f} = \sum_{k = 1}^{n} f_k \bar{g}_k = \sum_{k = 1}^{n} f(x_k) \bar{g}(x_k) $$

----

Độ lớn (magnitude) của tích vô hướng sẽ tăng khi có thêm nhiều điểm dữ liệu ($n$ tăng). Vì vậy chúng ta sẽ chuẩn hóa $\Delta x = (b-a)/(n-1):$

$$\frac{b-a}{n-1} \langle \mathbf{f}, \mathbf{g} \rangle = \sum_{k = 1}^{n} f(x_k) \bar{g}(x_k) \Delta x $$

----

Ta có giá trị xấp xỉ Riemann (Riemann approximation) cho tích bên trong của hàm liên tục. Khi $n \to \infty$, tích vô hướng của vectơ hội tụ với tích vô hướng của công thức gốc.

![](https://i.imgur.com/pyjNIla.png)

----

#### Ứng dụng khác của tích vô hướng

Trong không gian vectơ hữu hạn chiều, tích vô hướng (inner product) có thể được sử dụng để chiếu (project) một hàm vào một hệ tọa độ mới được xác định bằng cơ sở của các hàm trực giao (basis of orthogonal functions). Biểu diễn chuỗi Fourier của một hàm $\mathbf{f}$ chính xác là một phép chiếu của hàm này lên tập trực giao của các hàm **sin** và **côsin** với chu kỳ nguyên trên miền $[a, b]$.

----

### Chuỗi Fourier (Fourier Series)

Một kết quả cơ bản trong phân tích Fourier (Fourier analysis) là nếu hàm $f(x)$ là tuần hoàn (periodic) và "mượt" (smooth), thì nó có thể được viết dưới dạng chuỗi Fourier, là tổng vô hạn của các hàm **cosin** và **sin** có tần số (frequency) tăng dần. Đặc biệt, nếu $f(x)$ tuần hoàn với chu kì $2 \pi$, thì nó có thể được viết là:

$$f(x) = \frac{a_0}{2} + \sum_{k = 1}^{\infty} (a_k cos(kx) + b_k sin(kx))$$


----

Hệ số $a_k$ và $b_k$ được xác định như sau:

$$a_k = \frac{1}{\Vert cos(kx) \Vert ^2} \int_{-\pi}^{\pi} f(x) cos(kx) = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) cos(kx)dx$$

$$b_k = \frac{1}{\Vert sin(kx) \Vert ^2} \int_{-\pi}^{\pi} f(x) sin(kx) = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) sin(kx)dx$$

----

Công thức tổng quát của chuỗi Fourier cho hàm có chu kì $L$ trên $[0, L)$ là:

$$f(x) = \frac{a_0}{2} + \sum_{k = 1}^{\infty} \left( a_k cos \left( \frac{2\pi kx}{L} \right) + b_k sin \left( \frac{2\pi kx}{L} \right) \right)$$

----

Hệ số $a_k$ và $b_k$ được xác định như sau:

$$a_k = \frac{1}{L} \int_{0}^{L} f(x) cos(\frac{2\pi kx}{L})dx$$

$$b_k = \frac{1}{L} \int_{0}^{L} f(x) sin(\frac{2\pi kx}{L})dx$$

----

Ta biểu diễn lại bằng công thức Euler (Euler's formula) $e^{ikx} = cos(kx) + i \space sin(kx)$ để viết chuỗi Fourier dưới dạng phức có hệ số phức $c_k = \alpha_k + i \beta_k:$

$$f(x) = \sum_{k = -\infty}^{\infty} c_k e^{ikx}$$

$$f(x) = \sum_{k = -\infty}^{\infty} (\alpha_k + i \beta_k)(cos(kx) + i \space sin(kx))$$

---

## Biến đổi Fourier Rời rạc và Biến đổi Fourier Nhanh (Discrete Fourier Transform and Fast Fourier Transform)

---

```=python
# Solve the quadratic equation ax**2 + bx + c = 0
# import complex math module
import cmath
a = 1
b = 5
c = 6
# calculate the discriminant
d = (b**2) - (4*a*c)
# find two solutions
sol1 = (-b-cmath.sqrt(d))/(2*a)
sol2 = (-b+cmath.sqrt(d))/(2*a)
print('The solution are {0} and {1}'.format(sol1,sol2))
```

---

## Transforming partial differential equations

## Gabor transform and the spectrogram

## Wavelets and multi-resolution analysis

## 2D transforms and image processing

