"

37

37.1. Tập nghiệm thông qua ma trận giả nghịch

[latexpage]

Định lý sau đây cung cấp tất cả các nghiệm (tập tối ưu) của một bài toán bình phương tối thiểu.

Định lý: Tập tối ưu của bài toán bình phương tối thiểu thông thường
 

Tập tối ưu của bài toán OLS

[latex]p^* = \min_x \|A x - y\|_2[/latex]

có thể được biểu diễn là

[latex]\mathbf{X}^{\text {opt }} = A^{\dagger} y + \mathbf{N}(A),[/latex]

trong đó [latex]A^{\dagger}[/latex] là \textit{ma trận giả nghịch} của [latex]A[/latex], và [latex]A^{\dagger} y[/latex] là điểm có chuẩn nhỏ nhất trong tập tối ưu. Nếu [latex]A[/latex] có hạng cột đầy đủ, nghiệm là duy nhất, và bằng

[latex]x^* = A^{\dagger} y = (A^T A)^{-1} A^T y.[/latex]

Tổng quát, nghiệm riêng [latex]A^{\dagger} y[/latex] là nghiệm có chuẩn nhỏ nhất của bài toán bình phương tối thiểu.

37.2. Phân tích độ nhạy

Ta xét phương trình

\[ y + \delta y = A x, \]

với

  • [latex]A \in \mathbb{R}^{m \times n}[/latex] là ma trận dữ liệu (đã biết), với [latex]A[/latex] có hạng cột đầy đủ (do đó [latex]m \geq n[/latex]).
  • [latex]y \in \mathbb{R}^m[/latex] là phép đo (đã biết).
  • [latex]x \in \mathbb{R}^n[/latex] là véctơ cần ước lượng (chưa biết).
  • [latex]\delta y \in \mathbb{R}^m[/latex] là một nhiễu hoặc sai số đo lường (chưa biết).

Ta có thể sử dụng OLS để cung cấp một ước lượng [latex]\hat{x}_{\text{OLS}}[/latex] của [latex]x[/latex]. Ý tưởng là tìm véctơ [latex]\delta y[/latex] nhỏ nhất sao cho phương trình trên trở nên khả thi, tức là,

\[ \min_{x, \delta y} \|\delta y\|_2 : y + \delta y = A x. \]

Điều này dẫn đến bài toán OLS:

\[ \min_x \|A x – y\|_2. \]

Vì [latex]A[/latex] có hạng cột đầy đủ, phân tích SVD của nó có thể được biểu diễn là

\[ A = U \begin{pmatrix} \Sigma \\ 0 \end{pmatrix} V^T, \]

trong đó [latex]\Sigma=\mathbf{diag}\left(\sigma_1, \ldots, \sigma_n\right)[/latex] chứa các giá trị kỳ dị của [latex]A[/latex], với [latex]\sigma_1 \geq \ldots \geq \sigma_n>0[/latex].

Vì [latex]A[/latex] có hạng cột đầy đủ, nghiệm [latex]\hat{x}_{\mathrm{LS}}[/latex] của bài toán OLS là duy nhất, và có thể được viết dưới dạng một \textit{hàm tuyến tính} của véctơ đo lường [latex]y[/latex]:

\[ \hat{x}_{\mathrm{LS}} = A^{\dagger} y, \]

với [latex]A^{\dagger}[/latex] là ma trận giả nghịch của [latex]A[/latex]. Một lần nữa, vì [latex]A[/latex] có hạng cột đầy đủ,

\[ A^{\dagger} = (A^T A)^{-1} A^T = V \begin{pmatrix} \Sigma^{-1} & 0 \end{pmatrix} U^T. \]

Cách phát biểu OLS cung cấp một ước lượng [latex]\hat{x}[/latex] của đầu vào [latex]x[/latex] sao cho véctơ phần dư [latex]Ax-y[/latex] được tối thiểu hóa về chuẩn. Ta quan tâm đến việc phân tích tác động của các nhiễu trong véctơ [latex]y[/latex] đối với nghiệm kết quả [latex]\hat{x}_{LS}[/latex]. Ta bắt đầu bằng việc phân tích các sai số tuyệt đối trong ước lượng và sau đó chuyển sang phân tích các sai số tương đối.

Tập hợp các sai số có thể

Ta hãy giả sử một mô hình đơn giản về các nhiễu tiềm năng: ta giả sử rằng [latex]\delta y[/latex] thuộc một quả cầu đơn vị: [latex]||\delta y||_2 \leq \alpha[/latex], trong đó [latex]\alpha>0[/latex] là một giá trị cho trước. Ta sẽ giả sử [latex]\alpha=1[/latex] để đơn giản hóa; phân tích có thể dễ dàng được mở rộng cho mọi [latex]\alpha>0[/latex].

Ta có

\[ \begin{aligned} \delta x &:= x – \hat{x} \\ &= x – A^{\dagger} y \\ &= x – A^{\dagger}(A x – \delta y) \\ &= (I – A^{\dagger} A) x + A^{\dagger} \delta y \\ &= A^{\dagger} \delta y. \end{aligned} \]

Trong các bước trên, ta đã khai thác tính chất rằng [latex]A^{\dagger}[/latex] là một ma trận nghịch đảo trái của [latex]A[/latex], tức là, [latex]A^{\dagger} A=I_n[/latex].

Tập hợp các sai số có thể của nghiệm [latex]\delta x[/latex] khi đó được cho bởi

\[ \mathbf{E} = \left\{ A^{\dagger} \delta y : \|\delta y\|_2 \leq 1 \right\}, \]

là một elipsoid có tâm tại gốc tọa độ, với các trục chính được cho bởi các giá trị kỳ dị của [latex]A^{\dagger}[/latex]. Elipsoid này có thể được diễn giải là một \textit{elipsoid tin cậy} cho ước lượng [latex]\hat{x}[/latex], với kích thước và hình dạng được xác định bởi ma trận [latex]A^{\dagger}(A^{\dagger})^T[/latex].

Ta có thể rút ra một số kết luận từ phân tích này:

  • Sai số tuyệt đối lớn nhất trong nghiệm có thể gây ra bởi một nhiễu cộng tính có chuẩn đơn vị trên [latex]y[/latex] có bậc là [latex]1 / \sigma_n[/latex], trong đó [latex]\sigma_n[/latex] là giá trị kỳ dị nhỏ nhất của [latex]A[/latex].
  • Sai số tương đối lớn nhất là [latex]\sigma_1 / \sigma_n[/latex], chính là số điều kiện của [latex]A[/latex].

37.3. Tính chất BLUE

Bây giờ ta quay lại trường hợp của một bài toán OLS với ma trận [latex]A[/latex] có hạng cột đầy đủ.

Các ước lượng tuyến tính không chệch

Xét họ các ước lượng tuyến tính, có dạng

\[ \hat{x} = B y, \]

trong đó [latex]B \in \mathbb{R}^{n \times m}[/latex]. Với ước lượng này, ta có sai số

\[ \begin{aligned} \delta x &= x – \hat{x} \\ &= x – B y \\ &= x – B(A x – \delta y) \\ &= (I – B A) x + B \delta y. \end{aligned} \]

Ta nói rằng ước lượng (được xác định bởi ma trận [latex]B[/latex]) là \textit{không chệch} nếu số hạng đầu tiên bằng không:

\[ B A = I. \]

Các ước lượng không chệch chỉ tồn tại khi phương trình trên khả thi, tức là, [latex]A[/latex] có một \textit{ma trận nghịch đảo trái}. Điều này tương đương với điều kiện của chúng ta là [latex]A[/latex] có hạng cột đầy đủ. Vì [latex]A^{\dagger}[/latex] là một ma trận nghịch đảo trái của [latex]A[/latex], ước lượng OLS là một trường hợp đặc biệt của một ước lượng tuyến tính không chệch.

Ước lượng tuyến tính không chệch tốt nhất

Phân tích trên dẫn đến câu hỏi sau: ước lượng tuyến tính không chệch nào là tốt nhất? Một cách để phát biểu bài toán này là giả sử rằng véctơ nhiễu [latex]\delta y[/latex] bị chặn theo một cách nào đó, và cố gắng tối thiểu hóa tác động có thể có của các sai số bị chặn như vậy đối với nghiệm.

Ta hãy giả sử rằng [latex]\delta y[/latex] thuộc một quả cầu đơn vị: [latex]\|\delta y\|_2 \leq 1[/latex]. Tập hợp các sai số kết quả của nghiệm [latex]\delta x[/latex] khi đó là

\[ \mathbf{E} = \left\{ B \delta y : \|\delta y\|_2 \leq 1 \right\}, \]

là một elipsoid có tâm tại gốc tọa độ, với các trục chính được cho bởi các giá trị kỳ dị của [latex]B[/latex]. Elipsoid này có thể được diễn giải là một elipsoid tin cậy cho ước lượng [latex]\hat{x}[/latex], với kích thước và hình dạng được xác định bởi ma trận [latex]BB^T[/latex].

Có thể chứng minh rằng ước lượng OLS là tối ưu theo nghĩa là nó cung cấp elipsoid tin cậy “nhỏ nhất” trong số tất cả các ước lượng tuyến tính không chệch. Cụ thể:

\[ B B^T \succeq A^{\dagger} (A^{\dagger})^T. \]

Tính tối ưu này của ước lượng LS được gọi là tính chất BLUE (Best Linear Unbiased Estimator – Ước lượng Tuyến tính Không chệch Tốt nhất).

License

Icon for the Public Domain license

This work (Đại số tuyến tính by Tony Tin) is free of known copyright restrictions.