Bài giảng 30: Phân tích giá trị kỳ dị (Singular Value Decomposition)

(Nếu công thức chưa load được hoặc mờ, các bạn ấn refresh để công thức hiện và rõ nét hơn nhé!)

Các định lý chéo hóa đóng vai trò quan trọng trong nhiều ứng dụng thú vị. Tuy nhiên, như chúng ta đã biết, không phải mọi ma trận đều có thể được phân tích dưới dạng $A=PDP^{-1}$ với $D$ là ma trận đường chéo. Tuy nhiên, một phân tích dưới dạng $A=QDP^{-1}$ là khả thi đối với mọi ma trận $m\times n$ bất kỳ! Một phép phân tích đặc biệt thuộc loại này, gọi là phân tích giá trị kỳ dị (singular value decomposition – SVD), là một trong những phép phân tích ma trận hữu ích nhất trong đại số tuyến tính ứng dụng.

Phân tích giá trị kỳ dị dựa trên tính chất sau của phép chéo hóa thông thường, một tính chất có thể được mô phỏng đối với các ma trận hình chữ nhật: Giá trị tuyệt đối của các trị riêng của một ma trận đối xứng $A$ phản ánh mức độ mà $A$ kéo giãn hoặc thu hẹp một số vectơ nhất định (các vectơ riêng). Nếu $A\mathbf{x}=\lambda\mathbf{x}$ và $\|\mathbf{x}\|=1$ , thì:

(1) $\begin{equation*}\|A\mathbf{x}\|=\|\lambda\mathbf{x}\|=|\lambda|\|\mathbf{x}\|=|\lambda|\end{equation*}$

Nếu $\lambda_1$ là trị riêng có độ lớn lớn nhất, thì một vectơ riêng đơn vị tương ứng $\mathbf{v}_1$ xác định một hướng mà trong đó hiệu ứng kéo giãn của ma trận $A$ là lớn nhất. Nói cách khác, độ dài của $A\mathbf{x}$ đạt giá trị cực đại khi $\mathbf{x}=\mathbf{v}_1$ , và $\|A\mathbf{v}_1\|=\|\lambda_1\|$ , theo phương trình (1). Mô tả này về $\mathbf{v}_1$ và $\|\lambda_1\|$ cũng có một tương tự đối với các ma trận hình chữ nhật, điều này sẽ dẫn đến phép phân tích giá trị kỳ dị.

Ví dụ 1: Nếu $A=\begin{bmatrix}4&11&14\\8&7&-2\\\end{bmatrix}$ , thì phép biến đổi tuyến tính $\mathbf{x}\mapsto A\mathbf{x}$ sẽ ánh xạ mặt cầu đơn vị $\{\mathbf{x}:\|\mathbf{x}\|=1\}$ trong $\mathbb{R}^3$ thành một hình elip trong $\mathbb{R}^2$ , như được minh họa trong hình 1. Hãy tìm một vectơ đơn vị $\mathbf{x}$ sao cho độ dài $\|A\mathbf{x}\|$ đạt giá trị lớn nhất, và tính độ dài cực đại này.

HÌNH 1: Một phép biến đổi từ $\mathbb{R}^3$ sang $\mathbb{R}^2$ .

Giải: Đại lượng $\|A\mathbf{x}\|^2$ đạt giá trị cực đại tại cùng một vectơ $\mathbf{x}$ với $\|A\mathbf{x}\|$ , và $\|A\mathbf{x}\|^2$ thì dễ khảo sát hơn. Ta có:

$\|A\mathbf{x}\|^2=(A\mathbf{x})^T(A\mathbf{x})=\mathbf{x}^T A^T A\mathbf{x}=\mathbf{x}^T(A^T A)\mathbf{x}$

Ngoài ra, $A^T A$ là một ma trận đối xứng, vì $(A^T A)^T=A^TA^{TT}=A^T A$ . Do đó, bài toán trở thành: Tối đa hóa dạng toàn phương $\mathbf{x}^T(A^T A)\mathbf{x}$ với điều kiện $\|\mathbf{x}\|=1$ . Theo định lý 6, giá trị cực đại sẽ là trị riêng lớn nhất $\lambda_1$ của $A^T A$ . Giá trị cực đại đó đạt được tại vectơ riêng đơn vị tương ứng với $\lambda_1$ của $A^T A$ .

Với ma trận $A$ trong ví dụ này:

$A^T A=\begin{bmatrix}4&8\\11&7\\14&-2\\\end{bmatrix}\begin{bmatrix}4&11&14\\8&7&-2\\\end{bmatrix}=\begin{bmatrix}80&100&40\\100&170&140\\40&140&200\\\end{bmatrix}$

Các trị riêng của $A^T A$ là: $\lambda_1=360,\lambda_2=90$ , và $\lambda_3=0$ . Các vectơ riêng đơn vị tương ứng lần lượt là

$\mathbf{v}_1=\begin{bmatrix}1/3\\2/3\\2/3\end{bmatrix},\quad\mathbf{v}_2=\begin{bmatrix}-2/3\\-1/3\\2/3\end{bmatrix},\quad\mathbf{v}_3=\begin{bmatrix}2/3\\-2/3\\1/3\end{bmatrix}$

Do đó, giá trị cực đại của $\|A\mathbf{x}\|^2$ là 360, đạt được khi $\mathbf{x}=\mathbf{v}_1$ , là vectơ đơn vị tương ứng với $\lambda_1$ . Khi đó:

$A\mathbf{v}_1=\begin{bmatrix}4&11&14\\8&7&-2\\\end{bmatrix}\begin{bmatrix}1/3\\2/3\\2/3\end{bmatrix}=\begin{bmatrix}18\\6\\\end{bmatrix}$

Vì $\|\mathbf{x}\|=1$ , nên giá trị lớn nhất của $\|A\mathbf{x}\|$ là $\|A\mathbf{v}_1\|=\sqrt{360}=6\sqrt{10}$ .

Ví dụ 1 cho thấy hiệu ứng của phép biến đổi $\mathbf{x}\mapsto A\mathbf{x}$ lên mặt cầu đơn vị trong $\mathbb{R}^3$ liên quan mật thiết đến dạng toàn phương $\mathbf{x}^T(A^T A)\mathbf{x}$ . Thực tế, toàn bộ hành vi hình học của phép biến đổi này được mô tả hoàn toàn bởi dạng toàn phương nói trên.

Các Giá Trị Kỳ Dị của Ma Trận $m\times n$

Cho ma trận $A$ kích thước $m\times n$ . Khi đó, $A^T A$ là ma trận đối xứng và có thể được chéo hóa trực chuẩn.

Gọi $\{\mathbf{v}_1,\dots,\mathbf{v}_n\}$ là một cơ sở trực chuẩn của $\mathbb{R}^n$ , bao gồm các vectơ riêng của $A^T A$ , và $\lambda_1,\dots,\lambda_n$ là các giá trị riêng tương ứng. Khi đó, với mỗi $i=1,\dots,n$ , ta có:

(2) $\begin{equation*}\begin{matrix}\|A\mathbf{v}_i\|^2=&(A\mathbf{v}_i)^T(A\mathbf{v}_i)=\mathbf{v}_i^T A^T A\mathbf{v}_i\\&=\mathbf{v}_i^T(\lambda_i\mathbf{v}_i)=\lambda_i\\\end{matrix}\end{equation*}$

Tức là, các giá trị riêng của $A^T A$ đều không âm ( $\geq 0$ ). Bằng cách đánh số lại nếu cần, ta có thể giả sử rằng:

$\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n\geq 0$

Các giá trị kỳ dị của $A$ là căn bậc hai của các giá trị riêng của $A^T A$ , ký hiệu là $\sigma_1,\dots,\sigma_n,$ với $\sigma_i=\sqrt{\lambda_i}$ . Chúng được sắp xếp theo thứ tự giảm dần $\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_n\geq 0$ . Theo công thức (2), các giá trị kỳ dị của $A$ cũng chính là độ dài của các vectơ $A\mathbf{v}_1,\dots,A\mathbf{v}_n$ .

Ví dụ 2: Cho ma trận $A$ như trong ví dụ 1. Vì các giá trị riêng của $A^T A$ là 360, 90 và 0, nên các giá trị kỳ dị (singular values) của $A$ là:

$\sigma_1=\sqrt{360}=6\sqrt{10};\quad\sigma_2=\sqrt{90}=3\sqrt{10};\quad\sigma_3=0$

Từ ví dụ 1, ta biết rằng giá trị kỳ dị thứ nhất của $A$ chính là giá trị lớn nhất của $\|A\mathbf{x}\|$ khi $\mathbf{x}$ chạy qua tất cả các vectơ đơn vị, và giá trị lớn nhất này đạt được tại vectơ riêng đơn vị $\mathbf{v}_1$ . Định lý 7 chỉ ra rằng giá trị kỳ dị thứ hai của $A$ là giá trị lớn nhất của $\|A\mathbf{x}\|$ trên tập tất cả các vectơ đơn vị vuông góc với $\mathbf{v}_1$ , và giá trị này đạt được tại vectơ riêng đơn vị thứ hai, $\mathbf{v}_2$ . Với $\mathbf{v}_2$ trong ví dụ 1:

$A\mathbf{v}_2=\begin{bmatrix}4&11&14\\8&7&-2\end{bmatrix}\begin{bmatrix}-2/3\\-1/3\\2/3\end{bmatrix}=\begin{bmatrix}3\\-9\end{bmatrix}$

Điểm này nằm trên trục ngắn của hình elip trong hình 1, tương tự như $A\mathbf{v}_1$ nằm trên trục dài. Xem hình 2.

Hai giá trị kỳ dị đầu tiên của $A$ chính là độ dài của nửa trục dài và nửa trục ngắn của hình elip.

Việc $A\mathbf{v}_1$ và $A\mathbf{v}_2$ vuông góc trong hình 2 không phải là ngẫu nhiên, như được chỉ ra trong định lý sau:

ĐỊNH LÝ 9 Giả sử  là một cơ sở trực chuẩn của , bao gồm các vector riêng của , được sắp xếp sao cho các giá trị riêng tương ứng của  thỏa mãn:  và giả sử  có  giá trị kỳ dị khác 0. Khi đó, tập hợp  là một cơ sở trực giao cho cột không gian của , tức là:  và: .

Chứng minh Vì $\mathbf{v}_i$ và $\lambda_j\mathbf{v}_j$ là trực giao khi $i\ne j$ ,

$(A\mathbf{v}_i)^T(A\mathbf{v}_j)=\mathbf{v}_i^T A^T A\mathbf{v}_j=\mathbf{v}_i^T(\lambda_j\mathbf{v}_j)=0$

Do đó, $\{A\mathbf{v}_1,\ldots,A\mathbf{v}_n\}$ là một tập hợp trực giao. Hơn nữa, vì độ dài của các vectơ $A\mathbf{v}_1,\ldots,A\mathbf{v}_n$ là các giá trị kỳ dị của $A$ , và vì có $r$ giá trị kỳ dị khác không, nên $A\mathbf{v}_i\ne 0$ khi và chỉ khi $1\le i\le r$ . Vậy các vectơ $A\mathbf{v}_1,\ldots,A\mathbf{v}_r$ là độc lập tuyến tính và nằm trong $\text{Col}\,A$ . Cuối cùng, với mọi $\mathbf{y}$ thuộc $\text{Col}\,A$ – giả sử $\mathbf{y}=A\mathbf{x}$ – ta có thể viết $\mathbf{x}=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n$ , và

$\mathbf{y}=A\mathbf{x}=c_1 A\mathbf{v}_1+\cdots+c_r A\mathbf{v}_r+c_{r+1}A\mathbf{v}_{r+1}+\cdots+c_n A\mathbf{v}_n$

$=c_1 A\mathbf{v}_1+\cdots+c_r A\mathbf{v}_r+0+\cdots+0.$

Do đó, $\mathbf{y}$ thuộc $\text{Span}\,\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}$ , điều này cho thấy rằng $\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}$ là một cơ sở trực giao của $\text{Col}\,A$ . Vậy $\text{rank}\,A=\dim\,(\text{Col}\,A)=r$ .

Ghi chú số học

Trong một số trường hợp, hạng của ma trận $A$ có thể rất nhạy cảm với những thay đổi nhỏ trong các phần tử của $A$ . Phương pháp hiển nhiên là đếm số cột chốt trong $A$ không hoạt động hiệu quả nếu $A$ được rút gọn hàng bằng máy tính. Sai số làm tròn thường tạo ra dạng bậc thang với hạng đầy đủ.

Trên thực tế, cách đáng tin cậy nhất để ước lượng hạng của một ma trận lớn $A$ là đếm số lượng giá trị kỳ dị khác không. Trong trường hợp này, các giá trị kỳ dị rất nhỏ nhưng khác không được xem như bằng không vì mục đích thực tiễn, và hạng hiệu dụng của ma trận là số lượng các giá trị kỳ dị khác không còn lại sau khi bỏ qua những giá trị nhỏ đó.

Các Giá Trị Kỳ Dị của Ma Trận $m\times n$

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 30: Phân tích giá trị kỳ dị (Singular Value Decomposition)

Lesson Attachments

Các Giá Trị Kỳ Dị của Ma Trận

Để lại một bình luận Hủy

Các Giá Trị Kỳ Dị của Ma Trận $m\times n$