從線性變換解釋最小平方近似

Posted on 10/28/2009 by ccjou

本文的閱讀等級：初級

在整個線性代數領域，移動向量空間的線性變換以不同面貌貫穿許多重要的主題。線性代數初學者經常將線性變換侷限於單純的幾何變換，例如，旋轉、拉伸、鏡射等，實際情況是線性變換幾乎無所不在，線性變換就隱藏在矩陣向量的乘法運算。直白地說，矩陣向量乘法是線性變換的具體實現，而線性變換則是矩陣向量乘法的情境描述。下面我從線性變換觀點解釋最小平方近似問題的解決過程與意義，透過線性變換觀點不但可使原本抽象的內容變成容易理解的敘事情境，線性變換的映射機制也為線性代數理論與其應用搭建一座橋樑。

令 $A$ 為一個 $m\times n$ 階實矩陣且 $\mathbf{b}\in\mathbb{R}^m$ 。線性方程 $A\mathbf{x}=\mathbf{b}$ 是一致的 (有解) 充要條件可以從兩個觀點表述。寫出 $A=\begin{bmatrix} \mathbf{a}_1&\cdots&\mathbf{a}_n \end{bmatrix}$ ，其中 $\mathbf{a}_j\in\mathbb{R}^m$ 是 $A$ 的行向量 (column vector)。第一個觀點是線性組合：常數向量 $\mathbf{b}$ 可表示為 $\mathbf{a}_1,\ldots,\mathbf{a}_n$ 的線性組合

$\displaystyle \mathbf{b}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\begin{bmatrix} \mathbf{a}_1&\cdots&\mathbf{a}_n \end{bmatrix}\begin{bmatrix} x_1\\ \vdots\\ x_n \end{bmatrix}=A\mathbf{x}$ ，

上面使用了 $x_i\mathbf{a}_i=\mathbf{a}_ix_i$ 。第二個觀點是線性變換： $\mathbf{b}$ 屬於線性變換 $A$ 的值域 (range)，即行空間 (column space) $C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^n\}$ ， $\mathbf{b}=A\mathbf{x}$ 稱為 $\mathbf{x}$ 經映射 $A$ 的像 (image)。如果線性方程 $A\mathbf{x}=\mathbf{b}$ 無解，這時我們只能求其最佳近似解，也就是找出 $\hat{\mathbf{x}}$ 使得誤差向量 $\mathbf{e}=\mathbf{b}-A\hat{\mathbf{x}}$ 有最小的長度平方，即

$\displaystyle\underset{\hat{\mathbf{x}}}{\text{minimize}}\,\Vert\mathbf{b}-A\hat{\mathbf{x}}\Vert^2$ 。

假設 $\hat{\mathbf{x}}\in\mathbb{R}^n$ 經線性變換 $A$ 映射至 $\mathbf{p}=A\hat{\mathbf{x}}\in C(A)$ ，或表示為 $\hat{\mathbf{x}}\overset{A}{\rightarrow}\mathbf{p}$ 。反過來問，我們想知道行空間 $C(A)$ 中那個 $\mathbf{p}$ 會產生最小的誤差 $\Vert\mathbf{e}\Vert$ ？從三維幾何空間直觀，最小誤差發生於 $\mathbf{e}=\mathbf{b}-\mathbf{p}$ 與 $\mathbf{p}$ 正交 (請你自己畫一個圖確認)，也就是說 $\mathbf{p}$ 是向量 $\mathbf{b}$ 至行空間 $C(A)$ 的正交投影。

令 $P$ 代表正交投影至行空間 $C(A)$ 的變換矩陣使得 $\mathbf{p}=P\mathbf{b}$ ，記為 $\mathbf{b}\overset{P}{\rightarrow}\mathbf{p}$ 。因為 $C(A)$ 是 $\mathbb{R}^m$ 的一個子空間，正交投影矩陣 $P$ 是 $m\times m$ 階並滿足 $P^2=P=P^T$ (見“特殊矩陣 (5)：冪等矩陣”)。欲求出正交投影矩陣 $P$ ，投影矩陣性質 $P^2\mathbf{b}=P\mathbf{b}=\mathbf{p}$ 說明投影一次與投影兩次的結果相同。因此， $P\mathbf{p}=P(P\mathbf{b})=P^2\mathbf{b}=\mathbf{p}$ ，於是有

$\begin{aligned} P(\mathbf{b}-\mathbf{p})&=\mathbf{p}-\mathbf{p}=\mathbf{0}\end{aligned}$ 。

上式說明 $\mathbf{b}-\mathbf{p}$ 屬於 $P$ 的零空間 $N(P)$ ，幾何意義是 $\mathbf{b}-\mathbf{p}$ 與行空間 $C(A)$ 正交致使投影向量為零。我們可以證明 $C(P)=C(A)$ ^[1] 且 $N(P)=N(A^T)$ ^[2]。因此， $\mathbf{e}=\mathbf{b}-\mathbf{p}=\mathbf{b}-A\hat{\mathbf{x}}$ 屬於 $C(A)$ 的正交補餘 (orthogonal complement) $C(A)^\perp=N(A^T)$ ，或稱 $A$ 的左零空間 (關於矩陣的四個基本子空間的正交關係介紹，請參閱“線性代數基本定理 (二)”)：

$\begin{aligned} A^T\mathbf{e}&=A^T(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}\end{aligned}$ ，

改寫成

$A^TA\hat{\mathbf{x}}=A^T\mathbf{b}$ 。

上式稱為正規方程 (normal equation)，這裡 normal 表示垂直，意思是殘差 $\mathbf{e}=\mathbf{b}-A\hat{\mathbf{x}}$ 正交於 $C(A)$ 。正規方程的解即為 $A\mathbf{x}=\mathbf{b}$ 的最小平方近似解。當 $A$ 的行向量是線性獨立時， $\mathrm{rank}A=n$ ， $A$ 稱為滿行秩。在此情況下，零空間退化為 $N(A)=\{\mathbf{0}\}$ ，列空間 $C(A^T)$ 充滿整個 $\mathbb{R}^n$ 。因為 $\mathrm{rank}A=\mathrm{rank}(A^TA)$ (證明見“每週問題 October 19, 2009”)，可知 $n\times n$ 階交互乘積 $A^TA$ 是可逆的，故存在唯一的最小平方近似解

$\hat{\mathbf{x}}=(A^TA)^{-1}A^T\mathbf{b}$ 。

由此立刻推論出最小誤差平方的投影向量

$\begin{aligned} \mathbf{p}&=A\hat{\mathbf{x}}=A(A^TA)^{-1}A^T\mathbf{b}\end{aligned}$ ，

正交投影矩陣即為

$P= A(A^TA)^{-1}A^T$ 。

底下補充說明常數向量 $\mathbf{b}$ 與誤差向量 $\mathbf{e}$ 的關係。因為

$\begin{aligned} (I-P)^2&=I-2P+P^2=I-2P+P=I-P\end{aligned}$ ，

$I-P$ 也是一個投影矩陣，且

$\begin{aligned} (I-P)\mathbf{b}&=\mathbf{b}-P\mathbf{b}=\mathbf{b}-\mathbf{p}=\mathbf{e}\end{aligned}$ 。

因此，向量 $\mathbf{b}$ 經 $I-P$ 正交投影至 $\mathbf{e}\in N(A^T)$ 。

最後我們將最小平方近似問題涉及的幾個線性變換整理於下 (見下圖)：

常數向量 $\mathbf{b}\in\mathbb{R}^m$ 經正交投影矩陣 $P=A(A^TA)^{-1}A^T$ 映至行空間 $C(A)$ 的投影向量 $\mathbf{p}$ ：

${\mathbf{b}}\overset{P}{\rightarrow}\mathbf{p}$
常數向量 $\mathbf{b}\in\mathbb{R}^m$ 經正交投影矩陣 $I-P$ 映至左零空間 $N(A^T)$ 的最小誤差向量 $\mathbf{e}$ ：

${\mathbf{b}}\xrightarrow[]{I-P}\mathbf{e}$
常數向量 $\mathbf{b}\in\mathbb{R}^m$ 經變換矩陣 $(A^TA)^{-1}A^T$ 映至列空間 $C(A^T)$ 的最小平方近似解 $\hat{\mathbf{x}}$ ：

$\mathbf{b}\xrightarrow[]{(A^TA)^{-1}A^T}\hat{\mathbf{x}}$
最小平方解 $\hat{\mathbf{x}}$ 經矩陣 $A$ 映至行空間 $C(A)$ 的投影向量 $\mathbf{p}$ ：

$\hat{\mathbf{x}}\xrightarrow[]{A}\mathbf{p}$

因此，將常數向量 $\mathbf{b}$ 映射至投影向量 $\mathbf{p}$ 的正交投影矩陣 $P$ 可以理解為二個線性變換的複合：

$\mathbf{b}\xrightarrow[]{(A^TA)^{-1}A^T}\hat{\mathbf{x}}\xrightarrow[]{A}\mathbf{p}$

但如果 $A$ 有線性相關的行向量，則 $A^TA$ 是一個不可逆矩陣，這時便不存在唯一的最小平方近似解，有興趣進一步瞭解這個主題的讀者請閱讀“通過推導偽逆矩陣認識線性代數的深層結構”。

最小平方近似圖解

註解
[1] 若 $\mathbf{x}\in C(A)$ ，則 $P\mathbf{x}=\mathbf{x}$ ，故 $\mathbf{x}\in C(P)$ ，證明 $C(A)\subseteq C(P)$ 。若 $\mathbf{x}\in C(P)$ ，必有 $\mathbf{y}$ 使得 $\mathbf{x}=P\mathbf{y}$ ，換句話說， $\mathbf{y}$ 通過 $P$ 正交投影至 $\mathbf{x}$ ，故 $\mathbf{x}\in C(A)$ ，證明 $C(P)\subseteq C(A)$ 。合併以上結果， $C(P)=C(A)$ 。
[2] 使用子空間的正交補餘關係， $N(P)=C(P^T)^{\perp}$ 與 $N(A^T)=C(A)^{\perp}$ 。又因為 $P^T=P$ 且 $C(P)=C(A)$ ，推得 $N(P)=C(P)^{\perp}=C(A)^{\perp}=N(A^T)$ 。

This entry was posted in 線性代數專欄, 內積空間 and tagged 線性變換, pseudo inverse, 偽逆矩陣, 投影矩陣, 最小平方法, 正規方程, 正交補餘, 正交投影. Bookmark the permalink.

14 Responses to 從線性變換解釋最小平方近似

miohwsiemit says:

02/10/2012 at 9:29 am

請問老師~
在第三段的前半部，為什麼會有這樣的推論：
「…將兩式相減，即得 P(b-p)=0 → 此式的幾何意義是向量b-p與行空間C(A)正交」？
我搞不太清楚P的行空間和A的行空間有甚麼關係？這個式子我得到~向量b-p在ker(P)，但不知道怎麼與 \mathrm{C(A^T)}做連結？

Reply
- ccjou says:
  
  02/10/2012 at 11:05 am
  
  因為已經假設 $P$ 是正交投影至 $C(A)$ 的 $m\times m$ 階矩陣 (注意 $A$ 是 $m\times n$ 階)，即知 $C(P)=C(A)$ ，理由如下：
  若 $x\in C(A)$ ，則 $Px=x$ ，故 $x\in C(P)$ ， $C(A)\subseteq C(P)$ 。
  若 $x\in C(P)$ ，必有 $y$ 使得 $x=Py$ ，換句話說， $y$ 經 $P$ 投影至 $x$ ，故 $x\in C(A)$ ， $C(P)\subseteq C(A)$ 。
  
  另外 $N(P)=N(A^T)$ 理由如下：
  根據線性代數第二定理， $N(P)=C(P^T)^{\perp}$ ， $N(A^T)=C(A)^{\perp}$ ，又因為 $P^T=P$ ， $C(P)=C(A)$ ，故 $N(P)=C(P)^{\perp}=C(A)^{\perp}=N(A^T)$ 。
  
  也許我該將這段文字放入上文。
  
  請參見冪等矩陣，裡面有較為清楚的說明。
  https://ccjou.wordpress.com/2009/09/29/%E7%89%B9%E6%AE%8A%E7%9F%A9%E9%99%A3-%E4%BA%94%EF%BC%9A%E5%86%AA%E7%AD%89%E7%9F%A9%E9%99%A3/
  
  Reply
miohwsiemit says:

02/10/2012 at 9:33 am

修正：…不知道怎麼與C(A^{T})做連結？

Reply
miohwsiemit says:

02/10/2012 at 1:45 pm

恩，寫得很清楚！謝謝老師！

不過，還想請問老師， $N(P)~=~N(A^T)$ 有什麼直觀看法嗎？(能讓老師一開始忽略了)

Reply
- ccjou says:
  
  02/10/2012 at 2:47 pm
  
  觀念還是在於正交補集 $N(A^T)=C(A)^{\perp}$ 。投影變換 $P$ 將所有 $x\in\mathbb{R}^m$ 正交投影至 $C(A)$ ，當 $x\in N(A^T)$ ，投影量 $Px=0$ ，即 $x\in N(P)$ 。反之亦然，這就說明了 $N(P)=N(A^T)$ 。
  
  Reply
  - miohwsiemit says:
    
    02/10/2012 at 11:08 pm
    
    不好意思，頭腦轉不過來@@
    請問老師可以再指點一下嗎？
    「當$latax x\in N(A^T) \Rightarrow $投影量$latax Px=0$ 」這個推論要怎麼直觀想？
    我這式子只推到$latax A^Tx=0$，不知道怎麼與N(P)做連結？
    謝謝…
    
    Reply
    - miohwsiemit says:
      
      02/10/2012 at 11:11 pm
      
      (上面這段可以刪掉嗎？謝謝:P)
      
      Reply
miohwsiemit says:

02/10/2012 at 11:09 pm

(重貼…)
不好意思，頭腦轉不過來@@
請問老師可以再指點一下嗎？
「當 $x\in N(A^T) \Rightarrow$ 投影量 $Px=0$ 」這個推論要怎麼直觀想？
我這式子只推到 $A^Tx=0$ ，不知道怎麼與N(P)做連結？
謝謝…

Reply
ccjou says:

02/10/2012 at 11:19 pm

因為 $N(A^T)\perp C(A)$ ，當 $x\in N(A^T)$ ，也就有 $x\perp C(A)$ ，既然 $x$ 垂直子空間 $C(A)$ ， $x$ 至 $C(A)$ 的正交投影必定為 0(好像日正當中，直立的竹竿沒有影子)，數學表達式即為 $Px=0$ 。

Reply
- miohwsiemit says:
  
  02/10/2012 at 11:30 pm
  
  我明白了^^ 謝謝老師！
  
  Reply
MMMan says:

05/30/2017 at 12:24 pm

老師您好: 想請問一下，怎麼看唯一的最小平方近似解，一定會落在列空間裡面呢。
謝謝老師您~

Reply
- ccjou says:
  
  05/30/2017 at 1:17 pm
  
  請參考
  https://goo.gl/UOxmZd
  若零空間僅包含零向量，則列空間等於輸入空間 $\mathbb{R}^n$ 。
  
  Reply
Chen says:

07/31/2018 at 2:56 pm

这篇文章让我看到了周老师的睿智.
零秩定理到四个子空间再延伸出
1. 极小范数解: Ax = b, 从C(A’) 中找最小范数特解, 而 N(A) 导致了通解(存在的原因). 将x 分解为C(A’) + N(A)
2. 最小二乘法(极小平方近似) \|Ax – b\|: 无解时的正交投影. 将b 分解为 C(A) + N(A’).

Reply
changxi cheng says:

07/21/2021 at 10:23 am

发现学习了一个线性代数的宝藏网站

Reply

	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨
	jeff85898 on 利用分塊矩陣證明 det(AB)=(det A)(det…