"

38

38.1. Xấp xỉ hạng thấp

[latexpage]

Ta xét một ma trận [latex]A \in \mathbb{R}^{m \times n}[/latex], với phân tích SVD được cho như trong định lý SVD:

\[ A = U \tilde{S} V^T, \quad \tilde{S} = \mathbf{diag}\left(\sigma_1, \ldots, \sigma_r, 0, \ldots, 0\right), \]

trong đó các giá trị kỳ dị được sắp xếp theo thứ tự giảm dần, [latex]\sigma_1 \geq \ldots \geq \sigma_r>0[/latex]. Trong nhiều ứng dụng, việc xấp xỉ [latex]A[/latex] bằng một ma trận hạng thấp có thể hữu ích.

Ví dụ: Giả sử [latex]A[/latex] chứa logarit tỷ suất sinh lợi của [latex]n[/latex] tài sản trong [latex]m[/latex] khoảng thời gian, sao cho mỗi cột của [latex]A[/latex] là một chuỗi thời gian cho một tài sản cụ thể. Việc xấp xỉ [latex]A[/latex] bằng một ma trận hạng một có dạng [latex]pq^T[/latex], với [latex]p \in \mathbb{R}^m[/latex] và [latex]q \in \mathbb{R}^n[/latex] tương đương với việc mô hình hóa các biến động của tài sản như là tất cả đều tuân theo cùng một khuôn mẫu được cho bởi hồ sơ thời gian [latex]p[/latex], với các biến động của mỗi tài sản được co giãn bởi các thành phần trong [latex]q[/latex]. Cụ thể, thành phần [latex](t, \;i)[/latex] của [latex]A[/latex], là logarit tỷ suất sinh lợi của tài sản [latex]i[/latex] tại thời điểm [latex]t[/latex], khi đó được biểu diễn là [latex]p(t)q(i)[/latex].

Ta xét bài toán xấp xỉ hạng thấp

\[ \min _X\|A-X\|_F: \mathbf{rank}(X) = k, \]

trong đó [latex]k[/latex] ([latex]1 \leq k

Định lý: Xấp xỉ hạng thấp
 

Một xấp xỉ hạng [latex]k[/latex] tốt nhất [latex]\hat{A}_k[/latex] được cho bằng cách cho [latex]r-k[/latex] giá trị kỳ dị cuối cùng của [latex]A[/latex] bằng không, tức là

\[ \hat{A}_k = U \hat{S}_k V^T, \quad \hat{S}_k = \mathbf{diag}\left(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0\right) . \]

Sai số tối thiểu được cho bởi chuẩn Euclid của các giá trị kỳ dị đã được cho bằng không trong quá trình này:

\[ \|A-\hat{A}_k\|_F = \sqrt{\sigma_{k+1}^2+\ldots+\sigma_r^2} . \]

Phác thảo chứng minh: Chứng minh dựa trên tính chất là chuẩn Frobenius bất biến qua phép quay của không gian đầu vào và đầu ra, tức là, [latex]\left\|U^T B V\right\|_F=\|B\|_F[/latex] với một ma trận [latex]B[/latex] bất kỳ, và các ma trận trực giao [latex]U, V[/latex] có kích thước phù hợp. Vì hạng cũng bất biến, ta có thể quy bài toán về trường hợp khi [latex]A=\tilde{S}[/latex].

Ví dụ: xấp xỉ hạng thấp của một ma trận [latex]4 \times 5[/latex].

38.2. Mối liên hệ với PCA

Phân tích Thành phần chính (PCA) hoạt động trên ma trận hiệp phương sai của dữ liệu, vốn tỉ lệ với [latex]AA^T[/latex], và đặt các phương chính là các véctơ riêng của ma trận (đối xứng) đó. Như đã lưu ý tại đây, các véctơ riêng của [latex]AA^T[/latex] chính là các véctơ kỳ dị trái của [latex]A[/latex]. Do đó, cả hai phương pháp, phương pháp xấp xỉ ở trên và PCA, đều dựa trên cùng một công cụ là SVD. SVD là một cách tiếp cận hoàn chỉnh hơn vì nó cũng cung cấp các véctơ riêng của [latex]A^TA[/latex] (các véctơ kỳ dị phải), vốn có thể hữu ích nếu ta muốn phân tích dữ liệu theo hàng thay vì theo cột.

Cụ thể, ta có thể biểu diễn phương sai giải được trực tiếp theo các giá trị kỳ dị. Trong bối cảnh trực quan hóa, phương sai giải thích được chỉ đơn giản là tỷ lệ giữa tổng lượng phương sai trong dữ liệu được chiếu và tổng lượng phương sai trong dữ liệu gốc. Tổng quát hơn, khi ta xấp xỉ một ma trận dữ liệu bằng một ma trận hạng thấp, phương sai giải thích được so sánh phương sai trong xấp xỉ với phương sai trong dữ liệu gốc. Ta cũng có thể diễn giải nó về mặt hình học, như là tỷ lệ của bình phương chuẩn của ma trận xấp xỉ so với bình phương chuẩn của ma trận gốc:

\[ \frac{\|\hat{A}_k\|_F^2}{\|A\|_F^2} = \frac{\sigma_1^2+\ldots+\sigma_k^2}{\sigma_1^2+\ldots+\sigma_n^2} . \]

License

Icon for the Public Domain license

This work (Đại số tuyến tính by Tony Tin) is free of known copyright restrictions.