[Handbook] Singular Values Decomposition và một số ứng dụng

Cơ sở lý thuyết.

1. Giá trị riêng, vector riêng của một ma trận.

1. Định nghĩa.

Giả sử A,xA, x lần lược là một ma trận vuông cấp nn trên trường KK. Giả sử có số λK\lambda\in K thỏa mãn tồn tại vector xKnx\in K^nx0x\ne 0 thỏa mãn Ax=λxAx=\lambda x thì λ\lambda được gọi là giá trị riêng của AA, xx được gọi là vector riêng tương ứng với giá trị riêng λ\lambda.

2. Tính chất.

Tính chất 1.

Mỗi vector riêng có một giá trị riêng duy nhất:

Giả sử ma trận vuông AA có vector riêng xx ứng với hai giá trị riêng λ1,λ2\lambda_1, \lambda_2 thì Ax=λ1x=λ2x(λ1λ2)x=0λ1=λ2Ax = \lambda_1x = \lambda_2x \Leftrightarrow (\lambda_1 - \lambda_2)x = 0 \Leftrightarrow \lambda_1 = \lambda_2

Tính chất 2.

Nếu xx là vector riêng ứng với giá trị riêng λ\lambda của ma trận vuông AA thì kxkx cũng là vector riêng ứng với λ\lambda: Ax=λxA(kx)=λ(kx)Ax = \lambda x \Leftrightarrow A(kx) = \lambda(kx)

Tính chất 3.

Nếu λ\lambda là giá trị riêng của ma trận vuông AA thì λn\lambda^n là giá trị riêng của ma trận AnA^n

Giả sử xx là vector riêng ứng với giá trị riêng λ\lambda của ma trận AA, khi đó Anx=An1(Ax)=An1λx=λAn1x=...=λnxA^nx = A^{n-1}(Ax) = A^{n-1}\lambda x = \lambda A^{n-1} x = ... = \lambda^n x

Tính chất 4.

Giá trị riêng của ma trận vuông AA là nghiệm của phương trình det(AλI)=0\text{det}(A-\lambda\mathbb{I}) = 0

Giả sử λ\lambda là giá trị riêng của ma trận AA, khi đó tồn tại x0x \ne 0Ax=λx(AλI)x=0Ax = \lambda x \Leftrightarrow (A - \lambda\mathbb{I})x = 0

Đây là một hệ phương trình tuyến tính, hệ này có nghiệm x0x \ne 0 khi và chỉ khi det(AλI)=0\text{det}(A-\lambda\mathbb{I}) = 0

Tính chất 5.

Ma trận vuông AA có giá trị riêng λ\lambda thì họ vector riêng ứng với λ\lambda là nghiệm của (AλI)x=0(A - \lambda\mathbb{I})x = 0

Tính chất 6.

Một ma trận đối xứng thì các vector riêng vuông góc với nhau.

Giả sử ma trận đối xứng AA có các vector riêng x,yx, y ứng với các giá trị riêng phân biệt λ,γ\lambda, \gamma. Khi đó:

λxTy=(λx)Ty=(Ax)Ty=xTATy=xTAy=xTγy\lambda x^Ty = (\lambda x)^Ty = (Ax)^Ty = x^TA^Ty = x^TAy = x^T\gamma y

=γxTy(λγ)xTy=0xTy=0= \gamma x^Ty\Leftrightarrow (\lambda - \gamma)x^Ty = 0 \Leftrightarrow x^Ty = 0

2. Chéo hóa ma trận.

1. Định nghĩa.

Ma trận vuông AA được gọi là chéo hóa được khi và chỉ khi tồn tại ma trận PP vuông không suy biến và ma trận đường chéo DD thỏa mãn P1AP=DP^{-1}AP = D

2. Diagonalication Theorem.

Phát biểu:

Ma trận vuông AA kích thước n×nn \times n chéo hóa được khi và chỉ khi nó có nn vector riêng độc lập tuyến tính.

Chứng minh.

Giả sử AAnn vector riêng độc lập tuyến tính là v1,v2,...,vnv_1, v_2, ..., v_n ứng với các giá trị riêng λ1,λ2,...,λn\lambda_1, \lambda_2, ..., \lambda_n, khi đó xét P=(v1,v2,...,vn)P = (v_1, v_2, ..., v_n)D=diag(λ1,λ2,...,λn)D = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_n)

Khi đó dễ thấy AP=PDAP = PD, do PP có các vector độc lập tuyến tính nên PP không suy biến, do đó P1AP=DP^{-1}AP = D nên AA chéo hóa được.

Ngược lại nếu AA chéo hóa được, nghĩa là P1AP=DAP=PDP^{-1}AP = D \Leftrightarrow AP = PD.

Giả sử P=(v1,v2,...,vn)P = (v_1, v_2, ..., v_n)D=diag(λ1,λ2,...,λn)D = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_n). Khi đó Avi=λiviAv_i = \lambda_i v_i

Do đó v1,v2,...,vnv_1, v_2, ..., v_n là các vector riêng của ma trận AA ứng với các giá trị riêng λ1,λ2,...,λn\lambda_1, \lambda_2, ..., \lambda_n

Ngoài ra theo định nghĩa, PP không suy biến, nghĩa là PP gồm các vector độc lập tuyến tính, nói cách khác, các vector riêng v1,v2,...,vnv_1, v_2, ..., v_n là độc lập tuyến tính.

3. Singular Value Decomposition.

1. Giới thiệu.

Singular Value Decomposition là một phương pháp phân tích ma trận AA kích thước m×nm \times n thành dạng tích ba ma trận: A=USVTA = USV^T. Trong đó

UU là ma trận kích thước m×rm \times r sao cho các vector cột tạo thành một hệ trực chuẩn.

SS là ma trận đường chéo kích thước r×rr \times r (rr là hạng của AA)

VV là ma trận kích thước n×rn \times r sao cho các vector cột tạo thành một hệ trực chuẩn.

Thấy rằng AT=VSUTA^T = VSU^T nên ATA=VSUTUSVT=VS2VTA^TA = VSU^TUSV^T = VS^2V^T, nhân bên phải cả hai vế cho VV, ta được ATAV=VS2A^TAV = VS^2

Do đó ta có thể thấy rằng S2S^2 chứa các trị riêng của ATAA^TAVV chứa các vector riêng tương ứng với trị riêng ở vị trí tương ứng.

Tương tự AAT=USVTVSUTAA^T = USV^TVSU^T nên AATU=US2AA^TU = US^2 nên UU chứa các vector riêng của AATAA^T tương ứng với các trị riêng ở ma trận SS

Ta thấy rằng nếu λ\lambda là một giá trị riêng của ma trận ATAA^TA, tương ứng với đó là vector xx thì ATAx=λxA^TAx = \lambda x thì xTATAx=λxTxx^TA^TAx = \lambda x^Tx

Tương đương với Ax2=λx2||Ax||^2 = \lambda ||x||^2, mà do x0x \ne 0 nên λ0\lambda \geqslant 0

Do đó λ1,λ2,...,λr\lambda_1, \lambda_2, ..., \lambda_r là các trị riêng của ATAA^TA thì quy ước S=diag(λ1,λ2,...,λr)S = \text{diag}(\sqrt{\lambda_1}, \sqrt{\lambda_2}, ..., \sqrt{\lambda_r})

• Đặt U=(u1,u2,...,ur),V=(v1,v2,...,vr),S=diag(σ1,σ2,...,σr)U = (u_1, u_2, ..., u_r), V = (v_1, v_2, ..., v_r), S = \text{diag}(\sigma_1, \sigma_2, ..., \sigma_r) thì ta có dạng tương đương của A=USVTA = USV^T như sau:

A=σ1u1v1T+σ2u2v2T+...+σrurvrTA = \sigma_1u_1v^T_1 + \sigma_2u_2v^T_2 + ... + \sigma_ru_rv^T_r

• Các vector u1,u2,...,uru_1, u_2, ..., u_r gọi là các left singular vector.

• Các vector v1,v2,...,vrv_1, v_2, ..., v_r gọi là các right singular vector.

• Các số σ1,σ2,...,σr\sigma_1, \sigma_2, ..., \sigma_r gọi là các singular value.

2. Các tính chất.

Giả sử ta có phân tích SVD của ma trận AA như sau: A=σ1u1v1T+σ2u2v2T+...+σrurvrTA = \sigma_1u_1v^T_1 + \sigma_2u_2v^T_2 + ... + \sigma_ru_rv^T_r, trong đó σ1σ2...σr\sigma_1 \geq \sigma_2 \geq ... \geq \sigma_r

Với 1kr1\leq k\leq r, đặt Ak=σ1u1v1T+σ2u2v2T+...+σkukvkTA_k = \sigma_1u_1v^T_1 + \sigma_2u_2v^T_2 + ... + \sigma_ku_kv^T_k thì rõ ràng AkA_k có hạng bằng kk.

Và cũng dễ thấy rằng AkA_k cũng là tích của ba ma trận: kk cột đầu của UU, ma trận vuông k×kk \times k đầu tiên của SSkk hàng đầu của VTV^T.

Ta có các tính chất sau:

Tính chất 1.

Ta có: v1=argmaxx=1Ax,vi=argmaxx=1,  xv1,v2,...,vi1Axv_1 = \underset{||x|| = 1}{\text{argmax}} ||Ax||, v_i = \underset{||x|| = 1, \;x \perp v_1, v_2, ..., v_{i - 1}}{\text{argmax}} ||Ax||

Giả sử x=i=1rαivix = \sum\limits_{i = 1}^{r} \alpha_i v_i thì Ax=i=1rαiAvi=i=1rαiσiui=i=1rαi2σi2||Ax|| = ||\sum\limits_{i = 1}^{r} \alpha_i Av_i|| = ||\sum\limits_{i = 1}^{r} \alpha_i \sigma_iu_i|| = \sqrt{\sum\limits_{i = 1}^{r} \alpha_i^2\sigma_i^2}

Khi đó để Ax||Ax|| lớn nhất thì i=1rαi2σi2\sqrt{\sum\limits_{i = 1}^{r} \alpha_i^2\sigma_i^2} lớn nhất, mà do i=1rαi2=1\sum\limits_{i=1}^{r} \alpha_i^2 = 1σjσi\sigma_j\leq \sigma_i nên Axσ1||Ax|| \leq \sigma_1

Dấu bằng xảy ra khi và chỉ khi x=v1x = v_1

Tiếp theo x=i=1rαivix = \sum\limits_{i = 1}^{r} \alpha_i v_ixv1x \perp v_1 thì α1=0\alpha_1 = 0, do đó Ax=i=2rαi2σi2σ2||Ax|| = \sqrt{\sum\limits_{i = 2}^{r} \alpha_i^2\sigma_i^2} \leq \sigma_2

Dấu bằng xảy ra khi và chỉ khi x=v2x = v_2. Cứ tiếp tục như thế và ta thu được kết quả.

Tính chất 2.

Trong tất cả các ma trận XX có hạng bé hơn hoặc bằng kk thì AXF||A - X||_F đạt giá trị nhỏ nhất khi và chỉ khi X=AkX = A_k

Ta thấy rằng AXF||A - X||_F là tổng của bình phương độ dài các vector hàng của AXA - X.

Các vector hàng của AXA - X đạt giá trị nhỏ nhất về độ dài khi và chỉ khi vector hàng tương ứng ở XX là hình chiếu của vector hàng tương ứng ở AA trên không gian sinh bởi các vector hàng của XX

Do đó AXF||A - X||_F nhỏ nhất khi và chỉ khi các vector hàng của XX là hình chiếu của các vector hàng của AA

Để ý rằng nếu không gian sinh bởi các vector hàng của XX có cơ sở w1,w2,...,wkw_1, w_2, ..., w_k là một hệ trực chuẩn thì AXF2AF2(Aw12+Aw22+...+Awk2)||A - X||_F^2 \geq ||A||_F^2 - (||Aw_1||^2 + ||Aw_2||^2 + ... + ||Aw_k||^2) (Định lý Pythagoras)

Do đó ý tưởng ta sẽ quy nạp Av12+Av22+...+Avk2Aw12+Aw22+...+Awk2||Av_1||^2 + ||Av_2||^2 + ... + ||Av_k||^2 \geqslant ||Aw_1||^2 + ||Aw_2||^2 + ... + ||Aw_k||^2 và công việc này thực sự được chứng minh nhẹ nhàng nhờ tính chất 1.

Cuối cùng, nhận xét rằng AkA_k là hình chiếu của các vector hàng của AA lên không gian được sinh bởi các vector hàng của AkA_k, và hiển nhiên cơ sở của nó là v1,v2,...,vkv_1, v_2, ..., v_k.

3. Nhận xét.

Phần định nghĩa giới thiệu về SVD là cách phân tích một ma trận qua dạng SVD bằng cách tính các giá trị riêng và vector riêng của ATAA^TAAATAA^T

Theo tính chất 2, ta phần nào đó có thể nói rằng AkA_k là ma trận xấp xỉ nhất với AA trong tất cả các ma trận hạng bé hơn hoặc bằng kk, với kk càng cao thì càng xấp xỉ.

Một cách hình học, Vk=span({v1,v2,...,vk})V_k = \text{span}(\{v_1, v_2, ..., v_k\}) là không gian kk chiều khít AA nhất. Về bản chất, có lẽ định hướng về hình học này là nguyên nhân sinh ra SVD.

Tuy nhiên thì đi từ hướng chưa có gì này nó hơi khó một chút nên mình đi theo hướng ngược lại để bài viết ngắn hơn.

4. Các hàm hỗ trợ tính SVD.

Trong thực tế, người ta thường chọn U,VU, V là các ma trận vuông kích thước m×m,n×nm \times m, n\times nSS có kích thước m×nm\times n (Dù dư một số vector nằm trong null(A)\text{null}(A))

Trong Python, hàm tính SVD là U, s, V = np.linalg.svd(...), trong Octave, Matlab[U, s, V] = svd(...)

Ứng dụng cơ bản.

1. Giảm chiều dữ liệu.

Các ma trận AkA_k gần khít với AA và có hạng bằng kk nên ta có thể dùng SVD để giảm chiều dữ liệu.

Việc giảm chiều dữ liệu giúp ta có khả năng biễu diễn bộ dữ liệu đó một cách khá chính xác trên đồ thị. Giả sử ta có một tập dữ liệu 4 chiều và ta muốn biểu diễn tập dữ liệu này trên đồ thị thì ta có thể dùng SVD để giảm chiều dữ liệu về 3.

Việc giảm chiều dữ liệu nhưng vẫn giữ được đặc trưng của bộ dữ liệu còn giúp số lượng tham số cần tính toán là ít hơn nên tính toán nhanh hơn.

2. Nén ảnh.

Với tính chất 2, ta thấy rằng nếu ảnh grayscale là AA kích thước m×nm \times n thì AkA_k kích thước m×nm \times n sẽ khá khít với AA khi kk càng lớn.

Do đó ta có ý tưởng lưu các ma trận SVD của AkA_k để thay thế, như thế ta cần lưu k(m+n+1)k(m + n + 1) phần tử (Chỉ cần lưu các singular values ở SS) so với mnmn phần tử của AA

Ta cần k<mnm+n+1k < \dfrac{mn}{m + n + 1} là được. Và để ảnh có thể biểu diễn tốt nhất thì ta cần AAkF2AF2=i=k+1rσi2i=1rσi2\dfrac{||A - A_k||_F^2}{||A||_F^2} = \dfrac{\sum\limits_{i = k + 1}^{r} \sigma_i^2}{\sum\limits_{i = 1}^{r} \sigma_i^2} chấp nhận được.

Tương tự với ảnh màu, ta làm tương tự cho từng ma trận của từng kênh màu.

3. Hồi quy tuyến tính.

Với bài toán hồi quy tuyến tính, với AAbb cho trước, ta phải tìm xx sao cho Axb||Ax - b|| là bé nhất.

Khi đó phân tích SVD A=USVTA = USV^T, trong đó U,VU, V là các ma trận trực giao. (Cách lấy thứ 2, không phải cách lấy được giới thiệu đầu bài)

Ta có UTU^T là một phép quay và VVT=1VV^T = 1 nên Axb=UT(AVVTxb)=SVTxzUTb=i=1n(σiziuiTb)2||Ax - b|| = ||U^T(AVV^Tx - b)|| = ||S\underset{z}{\underbrace{V^Tx}} - U^Tb|| = \sum\limits_{i = 1}^{n} (\sigma_iz_i - u_i^Tb)^2

Với i>ri > r thì σi=0\sigma_i = 0 nên Axb=i=1r(σiziuiTb)2+i=r+1n(uiTb)2i=r+1n(uiTb)2||Ax - b|| = \sum\limits_{i = 1}^{r} (\sigma_iz_i - u_i^Tb)^2 + \sum\limits_{i = r + 1}^{n} (u_i^Tb)^2 \geq \sum\limits_{i = r + 1}^{n} (u_i^Tb)^2

Dấu bằng xảy ra khi và chỉ khi zi=uiTbσiz_i = \dfrac{u_i^Tb}{\sigma_i} hay x=i=1ruiTbσivix = \sum\limits_{i = 1}^{r} \dfrac{u_i^Tb}{\sigma_i}v_i

4. PCA.

Ta thấy rằng, khi từ một tập điểm cho trước, việc giảm chiều cũng như là kẻ một siêu phẳng biểu diễn khít tập điểm đã cho. Ta không thể dùng các ma trận AkA_k một cách trực tiếp được, vì các ma trận AkA_k biểu diễn một siêu phẳng đi qua góc tọa độ.

Ta có thể thấy rằng v1v_1 biểu diễn phương mà tập điểm đó phân bố tập trung nhất khi nhìn từ gốc tọa độ (Av1||Av_1|| đạt giá trị lớn nhất). Sau đó v2v_2 lại biểu diễn phương vuông góc với v1v_1 mà phương đó tập điểm phân bố tập trung nhất cũng khi nhìn từ gốc tọa độ... Vậy một cách đơn giản, ta chỉ cần dời nó về trọng tâm của tập điểm và dùng SVD giảm chiều xuống.

Kết luận.

Ngoài các ứng dụng trên, SVD còn có các ứng dụng trong tối ưu cực trị rời rạc, lát cắt cực đại, K-means Clustering, Graph Partitioning, ... với một performance tính toán tương đối, rất thích hợp cho lượng dữ liệu lớn nhưng công dụng chính nhất vẫn là giảm chiều dữ liệu. Trong đó các vector v1,v2,...,vrv_1, v_2, ..., v_r lần lượt biểu diễn các phương mà dữ liệu phân bố tập trung nhất khi nhìn từ gốc tọa độ. Mong bài biết nhỏ này có thể giúp các bạn hiểu hơn về mô hình dữ liệu, cách sử dụng, tính toán SVD bằng tay hoặc bằng hàm viết sẵn. Việc dẫn nguồn rất khó vì mình đọc từ rất nhiều tài liệu pdf trên mạng và viết bài này mà không có kinh nghiệm dẫn nguồn, ngoài ra bài viết có thể có nhiều sai sót nên mong các bạn góp ý, thông cảm.