Singular Value Decomposition (SVD) Demo
Singular Value Decomposition
SVD cho phép ta phân rã một ma trận $A$ bất kỳ kích thước \(m \times n\) thành ba ma trận khác:
$$A = U \Sigma V^T$$
$U$ là ma trận trực giao kích thước \(m \times m\) với các cột là là eigenvectors của \(AA^T \)
\(\Sigma\) là ma trận chéo kích thước \(m \times n\) chứa các singular values (luôn không âm)
$V$ là ma trận trực giao kích thước \(n \times n\) với các cột là eigenvectors của \(A^TA\)
Một chút kiến thức nền tảng
Eigenvalues và Eigenvectors
Cho ma trận vuông $M$, một vector $v$ được gọi là eigenvector nếu:
$$Mv = \lambda v$$
trong đó \(\lambda\) là eigen value. Điều này có nghĩa là khi nhân ma trận $M$ với $v$ chỉ làm cho $v$ thay đổi độ dài chứ không thay đổi hướng.
Chéo hóa (diagonalization)
Nếu ma trận $M$ có thể viết dưới dạng
$$M = PDP^{-1}$$
với $D$ là ma trận chéo chứa các eigenvalues, thì ta nói $M$ có thể chéo hóa.
Trong SVD, ta không yêu cầu $A$ phải vuông hay khả nghịch. Thay vào đó, ta khai thác eigen-decomposition của hai ma trận vuông đối xứng \(A^TA, AA^T \) , các eigenvectors của chúng sẽ tạo nên ma trận $U, V$
Low-rank Approximation
Giả sử ma trận $A $ có phân rã: \(A=U\Sigma V^T\), nếu sắp xếp các singular values \(\sigma_1 \ge \sigma_2 \ge \dots \ge\sigma_r > 0\) với $r$ là rank của $A$, ta có thể viết lại
$$A = \sum_{i=1}^r \sigma_iu_iv_i^T$$
Trong đó:
\(u_i\) là cột thứ $i $ của $U$
\(v_i\) là cột thứ $i$ của $V$ (chú ý là công thức là \(V^T\), nên \(v_i^T\) trở thành hàng)
Nếu chỉ giữ lại $k < r$ thành phần lớn nhất, ta sẽ có:
$$A_k = \sum_{i=1}^k \sigma_iu_iv_i^T$$
Lúc đó \(A_k\) sẽ là xấp xỉ lớn nhất của $A$ trong chuẩn Frobenius và chuẩn 2 (Eckart–Young–Mirsky theorem)
Như vậy:
Trong xử lý ảnh: chỉ cần vài chục singular values lớn để khôi phục ảnh gần như đầy đủ, thay vì lưu toàn bộ ma trận pixel.
Trong machine learning: thay vì lưu một ma trận lớn (ví dụ 1 triệu user × 100 nghìn sản phẩm), ta có thể xấp xỉ bằng hạng thấp → tiết kiệm bộ nhớ và tính toán.
Ví dụ: Nếu ta lưu một ảnh kích thước 1,920 × 1,080 thì số pixel phải lưu là 2,073,600. Nếu áp dụng SVD với k=100 ta cần:
\(U_k\): 100 cột đầu tiên của ma trận $U$ là 100×1,920 = 192,000
\(\Sigma_k\): 100 phần tử trên đường chéo
\(V_k\): 100 cột đầu tiên của của ma trận $V$ là 100×1,080 = 108,000
Tổng cộng là 300,100 phần tử so với 2,073,600 phần tử của ma trận gốc.