34.1. Định lý SVD

[latexpage]

Ý tưởng cơ bản

Nhắc lại rằng bất kỳ ma trận [latex]A \in \mathbb{R}^{m \times n}[/latex] nào có hạng một đều có thể được viết dưới dạng

\[A = \sigma u v^{T},\]

trong đó [latex]u \in \mathbb{R}^{m}, v \in \mathbb{R}^{n}[/latex], và [latex]\sigma > 0[/latex].

Một kết quả tương tự cũng đúng cho các ma trận có hạng [latex]r[/latex] bất kỳ. Tức là, ta có thể biểu diễn bất kỳ ma trận [latex]A \in \mathbb{R}^{m \times n}[/latex] có hạng [latex]r[/latex] nào dưới dạng tổng của các ma trận hạng một

\[A = \sum_{i=1}^{r}\sigma_{i} u_{i} v_{i}^{T},\]

trong đó [latex]u_{1},\dots, u_{r}[/latex] trực giao đôi một, [latex]v_{1},\dots,v_{r}[/latex] cũng trực giao đôi một, và các số [latex]\sigma_{i}[/latex] là các số dương được gọi là các \textit{giá trị kỳ dị} của [latex]A[/latex]. Trong biểu thức trên, [latex]r[/latex] chính là hạng của [latex]A[/latex].

Kết quả quan trọng sau đây áp dụng cho bất kỳ ma trận [latex]A[/latex] nào, và cho phép ta hiểu được cấu trúc của ánh xạ [latex]x \rightarrow Ax[/latex].

Định lý: Phân tích giá trị kỳ dị (SVD)

Tính toán SVD

SVD của một ma trận [latex]m \times n[/latex] [latex]A[/latex] có thể được tính toán thông qua một chuỗi các phép biến đổi tuyến tính. Độ phức tạp tính toán của thuật toán, khi được biểu thị bằng số lượng phép toán dấu phẩy động, được cho bởi

\[ O(nm\min(n,m)). \]

Độ phức tạp này có thể trở nên đáng kể khi xử lý các ma trận dày đặc, lớn. Tuy nhiên, đối với các ma trận thưa, ta có thể tăng tốc độ tính toán nếu chỉ quan tâm đến một vài giá trị kỳ dị lớn nhất và các véctơ kỳ dị tương ứng của chúng. Để hiểu được nguồn gốc của độ phức tạp này:

• Tích ngoài của các véctơ [latex]u[/latex] và [latex]v^T[/latex] có độ phức tạp là [latex]O(mn)[/latex]. Điều này là do với một véctơ [latex]u[/latex] có độ dài [latex]m[/latex] và một véctơ [latex]v[/latex] có độ dài [latex]n[/latex], tích ngoài tạo ra một ma trận [latex]m \times n[/latex], và việc tính toán mỗi phần tử đòi hỏi một phép nhân.
• Ma trận [latex]A[/latex] có tối đa [latex]r[/latex] giá trị kỳ dị khác không, trong đó [latex]r \leq \min(m,n)[/latex]. Mỗi giá trị kỳ dị này sẽ góp phần vào chi phí tính toán tổng thể.
• Kết hợp các chi phí từ hai bước trước, tổng độ phức tạp tính toán trở thành [latex]O(\min(m,n) \cdot mn)[/latex].

Ví dụ: Ví dụ về ma trận $4 \times 5$.

34.2. Mô tả hình học của định lý SVD

Định lý này cho phép phân tích tác động của [latex]A[/latex] lên một véctơ đầu vào cho trước thành một quy trình ba bước. Để có được [latex]Ax[/latex], trong đó [latex]x \in \mathbb{R}^{n}[/latex], trước hết ta tạo [latex]\tilde{x} := V^{T}x \in \mathbb{R}^{n}[/latex]. Vì [latex]V[/latex] là một ma trận trực giao, [latex]V^{T}[/latex] cũng trực giao, và [latex]\tilde{x}[/latex] chỉ là một phiên bản được xoay của [latex]x[/latex], vẫn nằm trong không gian đầu vào. Sau đó, ta tác động lên véctơ đã xoay [latex]\tilde{x}[/latex] bằng cách co giãn các phần tử của nó. Cụ thể, [latex]r[/latex] phần tử đầu tiên của [latex]\tilde{x}[/latex] được co giãn bởi các giá trị kỳ dị [latex]\sigma_{1},\dots,\sigma_{r}[/latex]; [latex]n-r[/latex] phần tử còn lại được đặt bằng không. Bước này tạo ra một véctơ mới [latex]\tilde{y}[/latex] giờ đây thuộc không gian đầu ra [latex]\mathbb{R}^{m}[/latex]. Bước cuối cùng bao gồm việc xoay véctơ [latex]\tilde{y}[/latex] bằng ma trận trực giao [latex]U[/latex], dẫn đến [latex]y= U\tilde{y}=Ax[/latex].

Ví dụ, giả sử [latex]A[/latex] có dạng

\[A = \begin{pmatrix} 1.3 & 0 \\ 0 & 2.1 \\ 0 & 0 \end{pmatrix},\]

thì với một véctơ đầu vào [latex]x[/latex] trong [latex]\mathbb{R}^{2}[/latex], [latex]Ax[/latex] là một véctơ trong [latex]\mathbb{R}^{3}[/latex] với thành phần thứ nhất là [latex]1.3x_{1}[/latex], thành phần thứ hai là [latex]2.1x_{2}[/latex], và thành phần cuối cùng bằng không.

Tóm lại, định lý SVD phát biểu rằng bất kỳ phép nhân ma trận-véctơ nào cũng có thể được phân tích thành một chuỗi ba phép biến đổi cơ bản: một phép quay trong không gian đầu vào, một phép co giãn đi từ không gian đầu vào đến không gian đầu ra, và một phép quay trong không gian đầu ra. Khác với ma trận đối xứng, các phương đầu vào và đầu ra là khác nhau.

Phép diễn giải này cho phép đưa ra một vài phát biểu về ma trận.

Ví dụ: Ví dụ về ma trận $4 \times 4$.

34.3. Liên hệ với định lý phổ

Nếu [latex]A[/latex] có một phân tích SVD, thì các ma trận [latex]AA^{T}[/latex] và [latex]A^{T}A[/latex] có các phân tích SED sau:

\[A A^T=U \Lambda_m U^T, \quad A^T A=V \Lambda_n V^T,\]

trong đó \[ \Lambda_m := \tilde{S}\tilde{S}^{T} = \mathbf{diag}(\sigma_{1}^2,\dots,\sigma_{r}^2,0,\dots,0) \] ilà ma trận cỡ [latex]m \times m[/latex] (do đó nó có [latex]m-r[/latex] số không ở cuối), và

\[ \Lambda_n := \tilde{S}^{T}\tilde{S} = \mathbf{diag}(\sigma_{1}^2,\dots,\sigma_{r}^2,0,\dots,0) \]

là ma trận cỡ [latex]n \times n[/latex] (do đó nó có [latex]n-r[/latex] số không ở cuối). Các giá trị riêng của [latex]AA^{T}[/latex] và [latex]A^{T}A[/latex] là giống nhau, và bằng với bình phương các giá trị kỳ dị của [latex]A[/latex].

Các véctơ riêng tương ứng là các véctơ kỳ dị trái và phải của [latex]A[/latex].

Đây là một phương pháp (không phải là phương pháp hiệu quả nhất về mặt tính toán) để tìm SVD của một ma trận, dựa trên SED.