40
- SVD của các ma trận đơn giản
- Hạng và SVD
- Bài toán Procrustes
- SVD và các phép chiếu
- SVD và bình phương tối thiểu
40.1. SVD của các ma trận đơn giản
1. Xét ma trận
[latex]\begin{align*} A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \end{align*}[/latex]
a. Tìm không gian ảnh, không gian hạt nhân, và hạng của [latex]A[/latex].
b. Tìm một phân tích SVD của [latex]A[/latex].
c. Xác định tập nghiệm của hệ phương trình tuyến tính [latex]Ax=y[/latex], với
[latex]y=\left(\begin{array}{l} 2 \\ 3 \\ 0 \\ 0 \end{array}\right), \quad y=\left(\begin{array}{l} 2 \\ 0 \\ 0 \\ 3 \end{array}\right).[/latex]
2. Xét ma trận [latex]2 \times 2[/latex]
[latex]A=\frac{1}{\sqrt{10}}\left(\begin{array}{l} 2 \\ 1 \end{array}\right)\left(\begin{array}{ll} 1 & -1 \end{array}\right)+\frac{2}{\sqrt{10}}\left(\begin{array}{c} -1 \\ 2 \end{array}\right)\left(\begin{array}{ll} 1 & 1 \end{array}\right).[/latex]
a. Phân tích SVD của [latex]A[/latex] là gì? Biểu diễn nó dưới dạng [latex]A = USV^T[/latex], với [latex]S[/latex] là ma trận đường chéo của các giá trị kỳ dị được sắp xếp theo thứ tự giảm dần. Hãy kiểm tra tất cả các tính chất cần thiết cho [latex]U, S, V[/latex]
b. Tìm độ dài các bán trục và các trục chính (khoảng cách nhỏ nhất và lớn nhất cùng các phương tương ứng từ [latex]\mathcal{E}[/latex] đến tâm) của elipsoid
[latex]\mathcal{E}(A) = \{Ax: x \in \mathbb{R}^2, ||x||_2 \leq 1\}.[/latex]
Gợi ý: Sử dụng SVD của [latex]A[/latex] để chứng minh rằng mọi phần tử của [latex]\mathcal{E}(A)[/latex] đều có dạng [latex]y = U \overline{y}[/latex] với một phần tử [latex]\overline{y}[/latex] nào đó trong [latex]\mathcal{E}(S)[/latex]. Tức là, [latex]\mathcal{E}(A) = \{U\overline{y}: \overline{y} \in \mathcal{E}(S)\}[/latex]. (Nói cách khác, ma trận [latex]U[/latex] ánh xạ [latex]\mathcal{E}(S)[/latex] vào tập [latex]\mathcal{E}(A)[/latex].) Sau đó, phân tích hình học của tập đơn giản hơn [latex]\mathcal{E}(S)[/latex].
c. Tập [latex]\mathcal{E}(A)[/latex] là gì khi ta nối thêm một véctơ không sau cột cuối cùng của [latex]A[/latex], tức là [latex]A[/latex] được thay thế bằng [latex]\tilde{A} = (A, 0) \in \mathbb{R}^{2 \times 3}[/latex]?
d. Câu hỏi tương tự khi ta nối thêm một hàng sau hàng cuối cùng của [latex]A[/latex], tức là, [latex]A[/latex] được thay thế bằng [latex]\tilde{A} = [A^T, 0]^T \in \mathbb{R}^{3 \times 2}[/latex]. Diễn giải kết quả của bạn về mặt hình học.
40.2. Hạng và SVD
Hình ảnh bên trên cho thấy một ma trận [latex]256 \times 256[/latex] [latex]A[/latex] của các giá trị điểm ảnh. Các đường thẳng chỉ các giá trị [latex]+1[/latex]; tại mỗi giao điểm của các đường, phần tử ma trận tương ứng là [latex]+2[/latex]. Tất cả các phần tử khác bằng không.
1. Chứng minh rằng với một số ma trận hoán vị [latex]P, Q[/latex], ma trận được hoán vị [latex]B: = PAQ[/latex] có dạng đối xứng [latex]B = pq^T + qp^T[/latex], với hai véctơ [latex]p, q[/latex]. Xác định [latex]P, Q, B[/latex] và [latex]p, q[/latex].
2. Hạng của [latex]A[/latex] là gì? Gợi ý: tìm không gian hạt nhân của [latex]B[/latex].
3. Tìm một phân tích SVD của [latex]A[/latex]. Gợi ý: Tìm một phân tích giá trị riêng của [latex]B[/latex] (sửa từ gốc: S thành B), sử dụng kết quả của một bài tập về giá trị riêng tại đây.
40.3. Bài toán Procrustes
Bài toán Procrustes trực giao là một bài toán có dạng
[latex]\begin{align*} \min\limits_{X} ||AX-B||_F: X^TX = I_p, \end{align*}[/latex]
trong đó [latex]||\cdot||_F[/latex] ký hiệu chuẩn Frobenius, và các ma trận [latex]A \in \mathbb{R}^{m \times n}[/latex], [latex]B \in \mathbb{R}^{m \times p}[/latex] là đã cho. Ở đây, biến ma trận [latex]X \in \mathbb{R}^{n \times p}[/latex] bị ràng buộc phải có các cột trực chuẩn. Khi [latex]n=m=p[/latex], bài toán có thể được diễn giải về mặt hình học là tìm một phép biến đổi các điểm (nằm trong [latex]A[/latex]) thành các điểm khác (nằm trong [latex]B[/latex]) mà chỉ bao gồm phép quay.
1. Chứng minh rằng nghiệm của bài toán Procrustes ở trên có thể được tìm thấy thông qua SVD của ma trận [latex]A^TB[/latex].
2. Tìm một công thức cho câu trả lời của bài toán bình phương tối thiểu có ràng buộc
[latex]\begin{align*} \min\limits_{x} ||Ax-b||_2: ||x||_2=1, \end{align*}[/latex]
với [latex]A \in \mathbb{R}^{m \times n}[/latex], [latex]b \in \mathbb{R}^m[/latex] đã cho.
40.4. SVD và các phép chiếu
1. Ta xét một tập hợp [latex]m[/latex] điểm dữ liệu [latex]x_i \in \mathbb{R}^n[/latex], [latex]i = 1, \cdots, m[/latex]. Ta tìm một đường thẳng trong [latex]\mathbb{R}^n[/latex] sao cho tổng bình phương các khoảng cách từ các điểm đến đường thẳng đó là nhỏ nhất. Để đơn giản, ta giả sử rằng đường thẳng đi qua gốc tọa độ.
a. Xét một đường thẳng đi qua gốc tọa độ [latex]\mathcal{L} = \{tu: t\in\mathbb{R}\}[/latex], trong đó [latex]u \in \mathbb{R}^n[/latex] là một véctơ cho trước. (Bạn có thể giả sử mà không mất tính tổng quát rằng [latex]||u||_2=1[/latex].) Tìm một biểu thức cho phép chiếu của một điểm [latex]x[/latex] cho trước lên [latex]\mathcal{L}[/latex].
b. Bây giờ xét [latex]m[/latex] điểm và tìm một biểu thức cho tổng bình phương các khoảng cách từ các điểm đến đường thẳng [latex]\mathcal{L}[/latex].
c. Giải thích cách bạn sẽ tìm đường thẳng đó thông qua SVD của ma trận [latex]n\times m[/latex] [latex]X = [x_1, \cdots, x_m][/latex].
d. Thử giải quyết bài toán nếu không có ràng buộc đường thẳng phải đi qua gốc tọa độ.
2. Giải các bài toán tương tự như trên bằng cách thay thế đường thẳng bằng một siêu phẳng.
40.5. SVD và bình phương tối thiểu
1. Xét ma trận [latex]A[/latex] được tạo thành bởi
[latex]A = (c_1, c_2, c_3)[/latex], với [latex]c_1 = (1, 2, 8)^T, \quad c_2 = (3, 6, 9)^T, \quad c_3 = c_1 - 4c_2 + \epsilon_1 v, \quad \epsilon_1 = 10^{-7},[/latex]
với [latex]v[/latex] là một véctơ được chọn ngẫu nhiên trong [latex][-0.5, 0.5]^3[/latex] (điều này biểu thị một khối lập phương 3 chiều với mỗi chiều chạy từ [latex]-0.5[/latex] đến [latex]0.5[/latex]). Ngoài ra, ta định nghĩa
[latex]y = 2c_1 - 7c_2 + \epsilon_2 w, \quad \epsilon_2 = 10^{-4},[/latex]
với [latex]w[/latex] lại được chọn ngẫu nhiên trong [latex][-0.5, 0.5]^3[/latex]. Ta xét bài toán bình phương tối thiểu tương ứng
[latex]\begin{align*} \min\limits_x ||Ax-y||_2. \end{align*}[/latex]
a. Tìm hạng của [latex]A[/latex]
b. Áp dụng công thức bình phương tối thiểu [latex]x^* = (A^TA)^{-1}A^Ty[/latex]. Chuẩn của véctơ phần dư, [latex]r = Ax-y[/latex], là bao nhiêu?
c. Biểu diễn nghiệm bình phương tối thiểu theo SVD của [latex]A[/latex]. Tức là, tạo ma trận giả nghịch của [latex]A[/latex] và áp dụng công thức [latex]x^* = A^{\dagger} y[/latex]. Bây giờ chuẩn của véctơ phần dư là bao nhiêu?
d. Sử dụng kết quả vừa tìm được để giải thích ý nghĩa bài toán
2. Xét một bài toán bình phương tối thiểu
[latex]\begin{align*} \min\limits_x ||Ax-y||_2 \end{align*}[/latex]
trong đó ma trận dữ liệu [latex]A \in \mathbb{R}^{m \times n}[/latex] có hạng một.
a. Nghiệm của bài toán có duy nhất không?
b. Chỉ ra cách quy bài toán về một bài toán chỉ liên quan đến một biến vô hướng.
c. Biểu diễn tập nghiệm dưới dạng đóng.