Singular Value Decomposition (SVD) Demo

Singular Value Decomposition - SVD là một trong những phép phân tích quan trọng nhất trong đại số tuyến tính vì nó được áp dụng cực kỳ phổ biến trong các lĩnh vực về Machine Learning để giảm chiều dữ liệu hay nén ảnh... Bài viết này mình muốn giới thiệu đến bạn về phương pháp này và một interactive demo để các bạn có thể “vọc“ tận tay với nó :)

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:

• $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 được gọi là eigenvector nếu:

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 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

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 là $r$ rank của $A$, ta có thể viết lại

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ó:

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_x$: 100 cột đầu tiên của ma trận 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 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.

Demo