Giá trị tối ưu của bài toán

Sử dụng SVD, ta có thể tìm tập tối ưu cho bài toán tối ưu hóa bình phương tối thiểu

[latex]\begin{align*} p^*:= \min\limits_{x} ||Ax-y||_2^2, \end{align*}[/latex]

Thật vậy, nếu [latex](U, \tilde{S}, V)[/latex] là một phân tích SVD của [latex]A[/latex], bài toán có thể được viết là

[latex]\begin{align*} p^*=\min\limits_x\left\|U\begin{pmatrix} S & 0 \\ 0 & 0 \end{pmatrix} V^T x-y\right\|_2^2=\min\limits_x\left\|\begin{pmatrix} S & 0 \\ 0 & 0 \end{pmatrix} V^T x-U^T y\right\|_2^2, \end{align*}[/latex]

trong đó ta đã khai thác tính chất rằng chuẩn Euclid là bất biến dưới phép biến đổi trực giao [latex]U^T[/latex]. Với [latex]\tilde{x}:=V^Tx[/latex], và [latex]\tilde{y}:=U^Ty[/latex], và đổi biến [latex]x[/latex] thành [latex]\tilde{x}[/latex], ta biểu diễn biểu thức trên là

[latex]\begin{align*} p^*= \min\limits_{\tilde{x}}\left\|\left(\begin{array}{ll} S & 0 \\ 0 & 0 \end{array}\right) \tilde{x}- \tilde{y}\right\|_2^2. \end{align*}[/latex]

Khai triển các số hạng, và sử dụng các ký hiệu phân hoạch [latex]\tilde{x} = (\tilde{x}_r, \tilde{x}_{n-r})[/latex], [latex]\tilde{y} = (\tilde{y}_r, \tilde{y}_{m-r})[/latex], ta thu được

[latex]\begin{align*} p^{*2} = \min\limits_{\tilde{x}_r, \tilde{x}_{n-r}} ||S\tilde{x}_r-\tilde{y}_{r}||_2^2 + ||\tilde{y}_{m-r}||_2^2. \end{align*}[/latex]

Vì [latex]S[/latex] là ma trận khả nghịch, ta có thể làm cho số hạng đầu tiên trong hàm mục tiêu bằng không với lựa chọn [latex]\tilde{x}_r = S^{-1}\tilde{y}_r[/latex]. Do đó giá trị tối ưu là

[latex]\begin{align*} p^* = ||\tilde{y}_{m-r}||_2. \end{align*}[/latex]

Ta quan sát thấy rằng giá trị tối ưu bằng không khi và chỉ khi [latex]y \in {\bf R}(A)[/latex], điều này hoàn toàn tương đương với [latex]\tilde{y}_{m-r} = 0[/latex].

Tập tối ưu

Ta hãy tìm chi tiết tập tối ưu của bài toán. Biến [latex]\tilde{x}[/latex] được xác định một phần, thông qua [latex]r[/latex] thành phần đầu tiên của nó: [latex]\tilde{x}_r^* = S^{-1}\tilde{y}_r[/latex]. [latex]n-r[/latex] biến còn lại chứa trong [latex]\tilde{x}_{n-r}[/latex] là tự do, vì [latex]\tilde{x}_{n-r}[/latex] không xuất hiện trong hàm mục tiêu của bài toán trên.

Do đó, các điểm tối ưu có dạng [latex]x= V\tilde{x}[/latex], với [latex]\tilde{x} = (\tilde{x}^*_r, \tilde{x}_{n-r})[/latex], [latex]\tilde{x}_r^* = S^{-1}\tilde{y}_r[/latex], và [latex]\tilde{x}_{n-r}[/latex] là tự do.

Để biểu diễn điều này theo phân tích SVD ban đầu của [latex]A[/latex], ta quan sát thấy rằng [latex]x= V\tilde{x}=V(\tilde{x}_r, \tilde{x}_{n-r})^T[/latex] có nghĩa là

[latex]\begin{align*} x=V_r \tilde{x}_r+V_{n-r} \tilde{x}_{n-r}=V_r S^{-1} \tilde{y}_r+V_{n-r} \tilde{x}_{n-r} \end{align*}[/latex]

trong đó [latex]V[/latex] được phân hoạch là [latex]V= (V_r, V_{n-r})[/latex], với [latex]V_r \in \mathbb{R}^{n\times r}[/latex] và [latex]V_{n-r} \in \mathbb{R}^{n\times (n-r)}[/latex]. Tương tự, véctơ [latex]\tilde{y}_r[/latex] có thể được biểu diễn là [latex]\tilde{y}_r = U_r^T y[/latex], với [latex]U_r[/latex] được tạo thành từ [latex]r[/latex] cột đầu tiên của [latex]U[/latex]. Do đó, một phần tử [latex]x^*[/latex] bất kỳ trong tập tối ưu có dạng

[latex]\begin{align*} x^* = x_\mathrm{MN} + V_{n-r} z: z \in \mathbb{R}^{n-r}, \end{align*}[/latex]

trong đó [latex]x_\mathrm{MN}:= V_r S^{-1} U_r^T y[/latex]. Các thành phần tự do [latex]\tilde{x}_{n-r}[/latex] tương ứng với các bậc tự do được cho phép bởi không gian hạt nhân của [latex]A[/latex].

Điểm tối ưu có chuẩn nhỏ nhất

Nghiệm riêng của bài toán, [latex]x_\mathrm{MN}[/latex], là nghiệm có chuẩn nhỏ nhất, theo nghĩa nó là phần tử của [latex]\mathbf{X}^\mathrm{opt}[/latex] có chuẩn Euclid nhỏ nhất. Điều này được hiểu rõ nhất trong không gian của các biến [latex]\tilde{x}[/latex].

Thật vậy, lựa chọn cụ thể [latex]\tilde{x} = (\tilde{x}_r^*, 0)[/latex] tương ứng với phần tử trong tập tối ưu có chuẩn Euclid nhỏ nhất. Thật vậy, chuẩn của [latex]x[/latex] bằng với chuẩn của phiên bản đã được xoay của nó, [latex]\tilde{x}[/latex]. [latex]r[/latex] phần tử đầu tiên trong [latex]\tilde{x}_r^*[/latex] là cố định, và vì [latex]||\tilde{x}||_2^2 = ||\tilde{x}_r||_2^2 + ||\tilde{x}_{n-r}||_2^2[/latex], ta thấy rằng chuẩn nhỏ nhất đạt được khi [latex]\tilde{x}_{n-r} = 0[/latex].

Tập tối ưu thông qua ma trận giả nghịch

Ma trận [latex]V_r S^{-1} U_r^T[/latex], xuất hiện trong biểu thức của nghiệm riêng [latex]x_\mathrm{MN}[/latex] đã đề cập ở trên, không gì khác hơn là \textit{ma trận giả nghịch} của [latex]A[/latex], được ký hiệu là [latex]A^{\dagger}[/latex]. Thật vậy, ta có thể biểu diễn ma trận giả nghịch theo SVD là

[latex]\begin{align*} A^{\dagger} = V\left(\begin{array}{ll} S^-1 & 0 \\ 0 & 0 \end{array}\right) U^T. \end{align*}[/latex]

Với quy ước này, điểm tối ưu có chuẩn nhỏ nhất là [latex]A^{\dagger} y[/latex]. Nhắc lại rằng [latex]n-r[/latex] cột cuối cùng của [latex]V[/latex] tạo thành một cơ sở cho không gian hạt nhân của [latex]A[/latex]. Do đó tập tối ưu của bài toán là

[latex]\begin{align*} \mathbf{X}^\mathrm{opt} = A^{\dagger}y + {\bf N}(A). \end{align*}[/latex]

Khi [latex]A[/latex] có hạng cột đầy đủ [latex](r = n \leq m,\; A^TA \succ 0)[/latex], tập tối ưu thu về một tập đơn tử (một tập chỉ có một phần tử), vì không gian hạt nhân là [latex]\{0\}[/latex]. Điểm tối ưu duy nhất được biểu diễn là

[latex]\begin{align*} x_\mathrm{LS} = A^{\dagger}y = (A^TA)^{-1}A^Ty. \end{align*}[/latex]