通過推導偽逆矩陣認識線性代數的深層結構

本文的閱讀等級:高級

長久以來,機械學習法一直是廣被採用的學習方法,好處是短時間可以看見成效,壞處是很難繼續往前邁進。學習線性代數尤其如此,使用機械學習法頂多只能熟悉幾個演算法,記住一些性質和定理,但絲毫無助於理解線性代數的核心概念與結構。通過推導偽逆矩陣 (pseudo inverse),我們運用線性代數的基本定理將其深層結構,譬如向量空間、線性變換、正交、基底、基底變換等,全部予以呈現出來。無須背誦經文照樣可以輕鬆掌握線性代數的重要概念與技巧,何樂而不為之。

 
線性代數的核心問題之一是解線性方程 A\mathbf{x}=\mathbf{b}。但在現實應用中,我們經常會碰到無解的情形。令 A 為一個 m\times n 階實矩陣,且 \mathrm{rank}A=r (如欲延伸至複矩陣,以下只須將轉置 A^T 替換為共軛轉置 A^{\ast} 即可)。線性方程 A\mathbf{x}=\mathbf{b} 的求解障礙來自於底下兩個情況:

  1. A 的列 (row) 向量是線性相關集,即 r<m
  2. A 的行 (column) 向量是線性相關集,即 r<n

C(A) 表示 A 的行空間 (column space,即值域),C(A^T) 表示 A 的列空間 (row space)[1]。行空間 C(A)\mathbb{R}^m 的一個子空間,列空間 C(A^T) 則是 \mathbb{R}^n 的一個子空間。這個事實值得牢記:矩陣的行秩等於列秩 (見“行秩=列秩”),即 \hbox{rank}A=\dim C(A)=\dim C(A^T)。如果發生第一個障礙,r<m,則行空間 C(A) 未能充滿整個 \mathbb{R}^{m}。這時候,若常數向量 \mathbf{b} 不屬於 C(A),則 A\mathbf{x}=\mathbf{b} 不存在解 (或稱為不一致)。假如我們願意接受「最佳近似解」,那麼可將 \mathbf{b} 投影至 A 的值域 C(A)。令 \mathbf{p} 為向量 \mathbf{b}C(A) 的正交投影。這麼一來,問題變成求「山寨方程」A\hat{\mathbf{x}}=\mathbf{p} 的解。根據正交原則,投影 \mathbf{p} 正交於誤差向量 \mathbf{b}-\mathbf{p},也就是說,\mathbf{b}-A\hat{\mathbf{x}} 屬於 C(A) 的正交補餘 N(A^T) (見“從線性變換解釋最小平方近似”),亦即 A^{T}(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0},或表示為

A^{T}A\hat{\mathbf{x}}=A^{T}\mathbf{b}

稱為正規方程 (normal equation)。在線性代數中,normal 有兩個意思:一是正交,譬如法向量 (normal vector) 與正規方程;二是單位向量,譬如單範正交集 (orthonormal set)。基礎線性代數課本經常假設矩陣 A 有線性獨立的行向量,這時 \mathrm{rank}(A^TA)=\mathrm{rank}A=n,推論 n\times n 階交互乘積 (也稱為 Gramian 矩陣) A^{T}A 是可逆的,因此存在唯一的最小平方近似解

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

但若發生上述第二個障礙,r<nA 的行向量是線性相關集,則 A^{T}A 是不可逆的,正規方程便存在無窮多組解。繼續往下閱讀前,建議你徹底弄清楚矩陣尺寸 mn 以及矩陣秩 r 如何決定線性方程解的結構,詳見“由簡約列梯形式判斷線性方程解的結構”。

 
如果我們僅打算找出其中的一個特解,應該選擇哪一個?在所有的特解中有一個最為特別,這個特解構成的向量具有最小的2-範數 (歐幾里得長度),它位於 A 的列空間內而且唯一存在,稱為極小範數解,以符號 \mathbf{x}^{+} 表示,滿足 A\mathbf{x}^{+}=\mathbf{p} (參見“每週問題 May 4, 2009”)。欲求得 \mathbf{x}^{+},我們需要“線性代數基本定理 (三)”,它提供了矩陣 A 的四個基本子空間的單範正交基底,如下:

  • 列空間 C(A^T) 的一組基底:\mathbf{v}_{1},\ldots,\mathbf{v}_{r}\in\mathbb{R}^{n}
  • 零空間 N(A) 的一組基底:\mathbf{v}_{r+1},\ldots,\mathbf{v}_{n}\in\mathbb{R}^{n}
  • 行空間 C(A) 的一組基底:\mathbf{u}_{1},\ldots,\mathbf{u}_{r}\in\mathbb{R}^{m}
  • 左零空間 N(A^T) 的一組基底:\mathbf{u}_{r+1},\ldots,\mathbf{u}_{m}\in\mathbb{R}^{m}

這些基底向量還滿足下面的重要關係:

\begin{aligned}  A\mathbf{v}_{i}&=\sigma_{i}\mathbf{u}_{i},~~\sigma_{i}>0,~~i=1,\ldots,r\\  A\mathbf{v}_{i}&=\mathbf{0},~~i=r+1,\ldots,n,\end{aligned}

其中 \sigma_i 稱為 (非零) 奇異值。

 
因為 \mathbf{x}^{+}\in C(A^T),故可唯一表示為列空間基底 \mathbf{v}_1,\ldots,\mathbf{v}_r 的線性組合:

\mathbf{x}^{+}=c_{1}\mathbf{v}_{1}+\cdots+c_{r}\mathbf{v}_{r}=\begin{bmatrix}  \mathbf{v}_1&\cdots&\mathbf{v}_r&\cdots&\mathbf{v}_n  \end{bmatrix}\begin{bmatrix}    c_1\\    \vdots\\    c_r\\    \vdots\\    0    \end{bmatrix}=V\mathbf{c}

上式中,V=\begin{bmatrix}  \mathbf{v}_1&\cdots&\mathbf{v}_n  \end{bmatrix}n\times n 階正交矩陣,V^T=V^{-1}n 維向量 \mathbf{c} 的前 r 個元等於權重 c_{i}1\le i\le r,其餘元為 0。利用基底關係式計算 A\mathbf{x}^{+},可得

\begin{aligned}  A\mathbf{x}^{+}&=A(c_1\mathbf{v}_1+\cdots+c_r\mathbf{v}_r)\\  &=c_{1}\sigma_{1}\mathbf{u}_{1}+\cdots+c_{r}\sigma_{r}\mathbf{u}_{r}\\  &=\begin{bmatrix}  \mathbf{u}_1&\cdots&\mathbf{u}_r&\cdots&\mathbf{u}_m    \end{bmatrix}\begin{bmatrix}    \sigma_1&~&~&~&0\\    ~&\ddots&~&~&\vdots\\    ~&~&\sigma_r&~&\vdots\\    ~&~&~&\ddots&~\\    0&\cdots&\cdots&~&0    \end{bmatrix}\begin{bmatrix}    c_1\\    \vdots\\    c_r\\    \vdots\\    0    \end{bmatrix}\\  &=U\Sigma\mathbf{c}.\end{aligned}

上式中,U=\begin{bmatrix}  \mathbf{u}_1&\cdots&\mathbf{u}_m  \end{bmatrix}m\times m 階正交矩陣,U^T=U^{-1},且 \Sigma=\begin{bmatrix}  S&0\\  0&0  \end{bmatrix}m\times n 階對角矩陣,其中 S=\mathrm{diag}(\sigma_1,\ldots,\sigma_r) 是可逆分塊。另一方面,求出 \mathbf{b} 至行空間 C(A) 的正交投影。利用單範正交基底性質,即有

\begin{aligned}  \mathbf{p}&=(\mathbf{b}^{T}\mathbf{u}_{1})\mathbf{u}_{1}+\cdots+(\mathbf{b}^{T}\mathbf{u}_{r})\mathbf{u}_{r}\\  &=\mathbf{u}_1(\mathbf{b}^T\mathbf{u}_1)+\cdots+\mathbf{u}_r(\mathbf{b}^T\mathbf{u}_r)\\    &=\mathbf{u}_1\mathbf{u}_1^T\mathbf{b}+\cdots+\mathbf{u}_r\mathbf{u}_r^T\mathbf{b}\\    &=U\begin{bmatrix}    I_r&0\\    0&0    \end{bmatrix}_{m\times m}U^{T}\mathbf{b}.\end{aligned}

合併以上結果,線性方程 A\mathbf{x}^{+}=\mathbf{p} 可表示為

U\Sigma\mathbf{c}= U\begin{bmatrix}  I_r&0\\    0&0    \end{bmatrix}U^{T}\mathbf{b}

等號兩邊左乘 U^{-1},即得

\Sigma\mathbf{c}=\begin{bmatrix}  I_r&0\\    0&0    \end{bmatrix}U^{T}\mathbf{b}

n\times m 階矩陣 \Sigma^{+}=\begin{bmatrix}  S^{-1}&0\\  0&0  \end{bmatrix}。上式同時左乘 \Sigma^{+},就有

\begin{bmatrix}  I_r&0\\    0&0    \end{bmatrix}_{n\times n}\mathbf{c}=\Sigma^{+}\begin{bmatrix}    I_r&0\\    0&0    \end{bmatrix}_{m\times m}U^{T}\mathbf{b}=\Sigma^{+}U^{T}\mathbf{b}

因為 \mathbf{c} 僅有前 r 個元可為非零值,故得

\mathbf{c}=\Sigma^{+}U^{T}\mathbf{b}

再將上式代入線性組合式子 \mathbf{x}^{+}=V\mathbf{c},最後導出

\mathbf{x}^{+}=V\Sigma^{+}U^{T}\mathbf{b}

 
回顧“線性代數基本定理 (四)”(或見“奇異值分解(SVD)”),矩陣 A 的奇異值分解為

A=U\Sigma V^{T}

發揮一點想像力將逆矩陣的想法予以擴張。我們定義 m\times n 階矩陣 A 的偽逆矩陣 (pseudo inverse) 為下列 n\times m 階矩陣:

A^{+}=V\Sigma^{+}U^{T}=V\begin{bmatrix}  S^{-1}&0\\  0&0  \end{bmatrix}U^T

據此,位於列空間 C(A^T),具有極小範數的近似解向量即為

\mathbf{x}^{+}=A^{+}\mathbf{b}

偽逆矩陣 A^{+}\mathbf{b}-\mathbf{p} 映至 \mathbb{R}^n 的零向量。因為 \mathbf{b}-\mathbf{p}\in N(A^T),對於 i=1,\ldots,r,就有 \mathbf{u}^T_i(\mathbf{b}-\mathbf{p})=0,所以

A^{+}(\mathbf{b}-\mathbf{p})=V\begin{bmatrix}  S^{-1}&0\\  0&0  \end{bmatrix}U^T(\mathbf{b}-\mathbf{p})=V\mathbf{0}=\mathbf{0}

下圖整理了與 A^{+} 有關的一些映射。

pseudoinverse

偽逆矩陣在矩陣四個基本子空間平台的映射

 
由偽逆矩陣的定義不難驗證以下性質 (見“偽逆矩陣與轉置矩陣的二三事”):

  1. (A^{+})^{+}=A
  2. AA^{+}A=A (但 AA^{+} 未必是單位矩陣)
  3. A^{+}AA^{+}=A^{+}
  4. (A^{T})^{+}=(A^{+})^{T}
  5. A^{+}AAA^{+} 都是對稱矩陣。

偽逆矩陣是奇異值分解的一個重要應用,也可以視為線性方程求解問題的結論。在推導過程之初,我們很難聯想偽逆矩陣與奇異值分解竟然有著密切的關係,兩者的聯繫建立於我們所選擇的單範正交基底,這也說明基底不僅為向量空間的核心概念也是相當有效的分析工具。

 
註解:
[1] 在台灣,橫向稱為列,縱向稱為行。在中國大陸,橫向稱為行,縱向稱為列。

相關閱讀:
This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , , , . Bookmark the permalink.

6 則回應給 通過推導偽逆矩陣認識線性代數的深層結構

  1. Kim 說:

    這邊第二個情況是說,Ax!=b且有無限多最小誤差解,所以改求Ax=p的最小範數解(X+)?而最小範數解唯一也就表示這邊第二情況rank(A)=m 囉?其實X+=AT(AAT)-1p ? (+,T,-1都是上標,抱歉不會打數學式~"~)只是要表達也可以寫成pseudoinverse的形式嗎?

  2. ccjou 說:

    第一個問題:這邊第二個情況是說,Ax!=b且有無限多最小誤差解,所以改求Ax=p的最小範數解(X+)?

    是的

    第二個問題:最小範數解唯一也就表示這邊第二情況rank(A)=m 囉?其實X+=AT(AAT)-1p ?只是要表達也可以寫成pseudoinverse的形式嗎?

    我不很確定問題為何,請參閱下文
    https://ccjou.wordpress.com/2009/04/01/%E7%94%B1%E7%B0%A1%E7%B4%84%E5%88%97%E6%A2%AF%E5%BD%A2%E5%BC%8F%E5%88%A4%E6%96%B7%E7%B7%9A%E6%80%A7%E6%96%B9%E7%A8%8B%E8%A7%A3%E7%9A%84%E7%B5%90%E6%A7%8B/
    這或者可以回答你的問題。當rank(A)=n,而非 rank(A)=m,pseudoinverse 解 x+ 即為最小平方解。

  3. Kim 說:

    ATAx=ATb (T為上標)有無限多解不就發生在r(A)<n(情況二)? 而文中"果我們僅打算找出其中的一個特別解,應該選擇哪一個?在所有的特別解中,有一個最為特別,這個解構成的向量具有最小長度,它位於A的列空間內,而且它是唯一存在 (參考“每週問題 May 4, 2009”)"這邊不就指r(A)=m ? 否則最小長度解就不唯一啦(因為最小長度解為x=AT(AAT)-1b (T,-1為上標),若r(A)<m 則(AAT)-1不存在)? 所以我以為情況二是在r(A)<n(最小平方解無限多), r(A)=m(最小長度解唯一)下,討論Ax!=b無解之情況下,改求Ax=p的最小長度解? 不這樣的理解正不正確QQ? 抱歉問題有點多XD

  4. ccjou 說:

    請先參閱"由簡約列梯形式判斷線性方程解的結構"

    https://ccjou.wordpress.com/2009/04/01/%E7%94%B1%E7%B0%A1%E7%B4%84%E5%88%97%E6%A2%AF%E5%BD%A2%E5%BC%8F%E5%88%A4%E6%96%B7%E7%B7%9A%E6%80%A7%E6%96%B9%E7%A8%8B%E8%A7%A3%E7%9A%84%E7%B5%90%E6%A7%8B/

    r=\mathrm{rank}A

    r<mAx=b 未必有解,但正規方程式 A^TA\hat{x}=A^Tb 必定是有解的,因為這等於在解 A\hat{x}=p

    r=n,則 n 階方陣 A^TA 可逆,於是存在唯一解,此即一般所稱最小平方解 \hat{x}=(A^TA)^{-1}A^Tb,此解落在列空間中。

    r<n,則 A^TA 不可逆,故有無限多組解。每週問題 May 4, 2009 曾經證明列空間中的解唯一存在且具有最小長度,此解即為 x^{+}=A^{+}b

  5. 葉學舫 說:

    想請問,如果要求第一種情況的解,是否也可以計算AtA的條件數(Condition number)來判斷系統的敏感性和穩定性?
    取條件數來判斷系統是否是病態的,是否有一個客觀的值來介定計算而得的條件數是大還是小?

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s