|
Tập nghiệm [latex]\mathbf{S}[/latex] của bài toán bình phương tối thiểu \[ \min _x\|A x-y\|_2^2, \] trong đó [latex]A \in \mathbb{R}^{m \times n}[/latex], và [latex]y \in \mathbb{R}^m[/latex] là các dữ liệu đã cho, có thể được biểu diễn theo phân tích QR đầy đủ của [latex]A[/latex]: \[ A P=Q R, \quad R=\left(\begin{array}{cc} R_{11} & R_{12} \\ 0 & 0 \end{array}\right), \] trong đó [latex]R_{11} \in \mathbb{R}^{r \times r}[/latex] là ma trận tam giác trên và khả nghịch, [latex]R_{12} \in \mathbb{R}^{r \times(n-r)}[/latex], [latex]P[/latex] là một ma trận hoán vị, và [latex]Q[/latex] là ma trận trực giao cỡ [latex]m \times m[/latex]. Cụ thể, ta có [latex]\mathbf{S}=\left\{x_0+N z: z \in \mathbb{R}^{n-r}\right\}[/latex], với [latex]N[/latex] là một ma trận mà các cột của nó là một cơ sở của không gian hạt nhân của [latex]A[/latex]: \[ x_0=P\left(\begin{array}{c} R_{11}^{-1} y_1 \\ 0 \end{array}\right), \quad N=\left(\begin{array}{c} R_{11}^{-1} R_{12} \\ I \end{array}\right) \in \mathbb{R}^{n \times(n-r)}. \] |
Chứng minh: Vì [latex]Q[/latex] và [latex]P[/latex] là các ma trận trực giao, ta có, với [latex]\bar{x}:=P^T x, \bar{y}:=Q^T y[/latex]:
\[ A x-y=A P P^T x-y=Q R \bar{x}-y=Q\left(R \bar{x}-Q^T y\right)=Q(R \bar{x}-\bar{y}), \]
Khai thác tính chất rằng [latex]Q[/latex] bảo toàn chuẩn Euclid, ta biểu diễn bài toán bình phương tối thiểu ban đầu dưới dạng tương đương:
\[ \min _{\bar{x}}\|R \bar{x}-\bar{y}\|_2. \]
Một khi bài toán trên được giải, và [latex]\bar{x}[/latex] được tìm thấy, ta thu được lại biến ban đầu [latex]x[/latex] với [latex]x=P \bar{x}[/latex].
Bây giờ ta hãy phân tích [latex]\bar{x}[/latex] và [latex]\bar{y}[/latex] theo một cách phù hợp với cấu trúc khối của [latex]R[/latex]: [latex]\bar{x}=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \bar{y}=\begin{pmatrix} y_1 \\ y_2 \end{pmatrix}[/latex], với [latex]x_1, y_1[/latex] là hai véctơ [latex]r[/latex] chiều. Khi đó
\[ R \bar{x}-\bar{y}=\left(\begin{array}{c} R_{11} x_1+R_{12} x_2-y_1 \\ -y_2 \end{array}\right), \]
dẫn đến biểu thức sau cho hàm mục tiêu:
\[ \|R \bar{x}-\bar{y}\|_2^2=\left\|R_{11} x_1+R_{12} x_2-y_1\right\|_2^2+\left\|y_2\right\|_2^2. \]
Lựa chọn tối ưu cho các biến [latex]x_1, x_2[/latex] là làm cho số hạng đầu tiên bằng không, điều này có thể đạt được với
\[ x_1=R_{11}^{-1}\left(y_1-R_{12} x_2\right), \]
trong đó [latex]x_2[/latex] là tự do và mô tả sự không duy nhất của nghiệm. Phần dư tối ưu là [latex]\left\|y_2\right\|_2^2[/latex].
Với [latex]x_2=z[/latex], ta có thể viết
[latex]P^T x=\bar{x}=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} R_{11}^{-1} y_1 \\ 0 \end{pmatrix}+\begin{pmatrix} -R_{11}^{-1} R_{12} \\ I \end{pmatrix} z,[/latex]
tức là: [latex]x=P \bar{x}=x_0+N z[/latex], với
[latex]x_0=P\begin{pmatrix} R_{11}^{-1} y_1 \\ 0 \end{pmatrix}, \quad N=P\begin{pmatrix} -R_{11}^{-1} R_{12} \\ I \end{pmatrix} \in \mathbb{R}^{n \times(n-r)}.[/latex]
