線性代數之最小二乘法及原理

08-15

線性代數之最小二乘法及原理

來自專欄仔仔的數學小屋19 人贊了文章

本文將介紹線性代數基本定理的應用，即最小二乘法。首先，本文將介紹相關的定理和它們的證明，其中包括線性代數基本定理，逼近定理，和正則系引理。

0.1 線性代數基本定理及證明

如果 $A$ 是一個 $m imes n$ 矩陣, 那麼

$mathrm{Row}(A)^{ot}=mathrm{Null}(A) \ mathrm{Col}(A)^{ot}=mathrm{Null}(A^{T})$

特別得,

$mathrm{Row}(A)oplus mathrm{Null}(A)=mathbb{R}^{n} \ mathrm{Col}(A)oplus mathrm{Null}(A^{T})=mathbb{R}^{m}$

證明:

因為 $mathrm{Col}(A)=mathrm{Row}(A^{T})$ ，我們只需要證明 $mathrm{Row}(A)^{ot}=mathrm{Null}(A)$ 。

令 $vec{u}in mathrm{Row}(A)^{ot}$ 。對於任意的 $vec xin mathrm{Row} (A)$ ，都有 $vec u cdot vec x =0$ 。

注意 $vec x=A^{T}vec y$ ，對於某 $vec yin mathbb R^m$ 。

$egin{aligned} vec ucdot vec x=vec 0 &implies vec u cdot (A^{T}vec y) = 0\ &implies ((A^T)^Tvec u)cdot vec y=0\ &implies (Avec u)cdot vec y = 0 end {aligned}$

因為 $vec ucdot vec x=0$ 對於所有的 $vec xin mathrm{Row}(A)$ 都成立，那麼 $(Avec u)cdot vec y = 0$ 也應當對於所有的 $vec yin mathbb R^m$ 成立。

因此，

$Avec u=vec 0 \ vec u in mathrm{Null}(A)$

因為 $mathrm{Row}(A)^{ot}$ 是 $mathrm{Null}(A)$ 的一個子空間，現在

$egin{aligned} mathrm{dim(Row}(A)^{ot}mathrm{)}&=mathrm{dim}mathbb R^n-mathrm{dimRow}(A)\ &=n-mathrm{rank}(A)\ &=mathrm{dimNull}(A)\ end{aligned}$

最後得到，

$mathrm{Row}(A)^{ot}=mathrm{Null}(A)$

證畢。

0.2 逼近定理及證明

令 $(mathbb V,<,>)$ 為一個內積空間。

假設 $mathbb W$ 是一個 $mathbb V$ 的子空間。

如果 $vec vin mathbb V$ ，則距離子空間 $mathbb W$ 最近的向量為

$mathrm{proj}_mathbb{W}(vec v)$

那就是說，對於所有在子空間 $mathbb W$ 上的 $vec w e mathrm{proj}_mathbb{W}(vec{v})$ ，我們都有

$||vec v-mathrm{proj}_mathbb{W}(vec v)||<||vec v-vec w||$

證明：

注意如果 $vec w e mathrm{proj}_{mathbb{W}}(vec v)$ ，則

$egin{aligned} ||vec v-vec w||^2 &= ||vec v-mathrm{proj}_mathbb W(vec v)+mathrm{proj}_mathbb W(vec v)-vec w||^2\ &= ||vec v-mathrm{proj}_mathbb W(vec v)||^2 + ||mathrm{proj}_mathbb W(vec v)-vec w||^2 end{aligned}$

因為 $||mathrm{proj}_mathbb W(vec v)-vec w||^2 e 0$ ，

$||vec v-mathrm{proj}_mathbb W(vec v)||^2>||vec v-vec w||^2implies||vec v-mathrm{proj}_mathbb W(vec v)||>||vec v-vec w||$

證畢。

說明：證明中使用了勾股定理 $<vec a,vec b>=0implies||vec a+vec b||^2=||a||^2+||b||^2$ 。

0.3 正規系引理(Normal System Lemma)及證明

令 $Ain M_{m imes n}(mathbb R)$ 以及 $vec bin mathbb R^m$ 。

如果 $vec xin mathbb R^n$ 使 $||Avec x-vec b||$ 最小化，那麼 $vec {x}$ 必須滿足正規系方程

$A^T Avec x=A^T vec b$

證明：

假設 $vec uin mathbb{R}^n$ 使 $||Avec x-vec b||$ 最小化（對於所有的 $vec xinmathbb{R}^n$ ）。

注意：因為 $Avec xin mathrm{Col}(A)$ ，所以當 $Avec x=mathrm{proj}_{mathrm{Col(A)}}vec b$ 時， $||Avec x-vec b||$ 被最小化。（根據上篇介紹的逼近定理）

那麼，

$Avec u=mathrm{proj}_{mathrm{Col(A)}}vec b$

現在，

$vec b-Avec u=mathrm{perp}_{mathrm{Col(A)}}vec binmathrm {Null}(A^T)implies A^T(vec b-Avec u)=vec 0$

因此，

$A^Tvec b-A^T Avec u=vec 0$

也就是說 $vec u$ 是 $A^Tvec b=A^T Avec u$ 的一個解。

證畢。

說明：這個定理的逆命題同樣正確。請練習證明此逆命題。

最小二乘法

目的：我們嘗試將數據組

$(x_1,y_1),cdots,(x_k,y_k)$

擬合到某個多項式 $y=a_0+a_1x+a_2x^2+cdots+a_nx^n$ 上。

理想中，我們希望

$a_0+a_1x_1+cdots+a_nx_1^n=y_1\ a_0+a_1x_2+cdots+a_nx_2^n=y_2\ vdots\ a_0+a_1x_k+cdots+a_nx_k^n=y_k$

因此我們建立

$vec b=egin{bmatrix} y_1 \ vdots \ y_k end{bmatrix}$ $X=egin{bmatrix} 1 &x_1 &x_1^2 &cdots &x_1^n \ 1 &x_2 &x_2^2 &cdots &x_2^n \ vdots &vdots &vdots &ddots &vdots \ 1 &x_k &x_k^2 &cdots &v_k^n end{bmatrix}$