SVD 於剖析線性方程的應用

本文的閱讀等級:高級

考慮線性方程 A\mathbf{x}=\mathbf{b},其中 Am\times n 階實矩陣,\mathbf{b}m 維向量,並設 \mathrm{rank}A=r。在一般情況下,高斯消去法是最普及的標準求解演算法,但假設我們已知矩陣 A 的奇異值分解 (SVD),那該如何運用這個優勢來計算方程式解?在“通過推導偽逆矩陣認識線性代數的深層結構”,我們曾經討論過這個問題,並從奇異值分解導出僞逆矩陣,本文則針對該文提出迴響及補充,用意是藉由奇異值分解產生的基底剖析線性方程的解。對奇異值分解陌生的讀者,請先參考“奇異值分解 (SVD)”。

 
A 的奇異值分解為 A=U\Sigma V^T,其中 Um\times m 階正交矩陣,U^{-1}=U^TVn\times n 階正交矩陣,V^{-1}=V^T\Sigmam\times n 階對角矩陣,主對角元為 r 個非零奇異值 \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0

\Sigma=\begin{bmatrix}    \sigma_1&~&~&\vline&~\\    ~&\ddots&~&\vline&0\\    ~&~&\sigma_r&\vline&~\\\hline    ~&0&~&\vline&0    \end{bmatrix}

UV 以行向量形式表示:

U=\begin{bmatrix}    \mathbf{u}_1&\cdots&\mathbf{u}_m    \end{bmatrix},~ V=\begin{bmatrix}    \mathbf{v}_1&\cdots&\mathbf{v}_n    \end{bmatrix}

因為 UV 是正交矩陣,左奇異向量集 \mathfrak{U}=\{\mathbf{u}_1,\ldots,\mathbf{u}_m\} 構成向量空間 \mathbb{R}^m 的一組單範正交基底 (orthonormal baiss),同樣地,右奇異向量集 \mathfrak{V}=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\} 則為 \mathbb{R}^n 的一組單範正交基底。矩陣四個相關子空間的的基底向量分別為

  • 列空間:\mathbf{v}_1,\ldots,\mathbf{v}_r
  • 零空間:\mathbf{v}_{r+1},\ldots,\mathbf{v}_n
  • 行空間:\mathbf{u}_1,\ldots,\mathbf{u}_r
  • 左零空間: \mathbf{u}_{r+1},\ldots,\mathbf{u}_m

下圖說明了各基底向量的關係,以及所屬的子空間,詳細推論過程請見“線性代數基本定理 (三)”。

orthonormal basis vectors

奇異值分解的分析平台

 
下面我們討論如何由矩陣的奇異值分解解析線性方程。將奇異值分解式代入給出的線性方程,

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

同時左乘 U^T

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

上式可解讀為由解向量 \mathbf{x} 參考基底 \mathfrak{V} 的座標向量 [\mathbf{x}]_{\mathfrak{V}}=V^T\mathbf{x} 與常數向量 \mathbf{b} 參考基底 \mathfrak{U} 的座標向量 [\mathbf{b}]_{\mathfrak{U}}=U^T\mathbf{b} 所構成的線性方程:

\Sigma[\mathbf{x}]_{\mathfrak{V}}=[\mathbf{b}]_{\mathfrak{U}}

上面這個等價方程式完全分離各變數間的耦合關係,接下來的求解工作因此非常簡單。

 
m>rA 不具有線性獨立的列向量,或者說 A 的行空間 C(A) 未能充滿整個 \mathbb{R}^m。在此情況下,\Sigma 的最底 m-r 列皆為零列,方程式存在解的充分與必要條件是 [\mathbf{b}]_{\mathfrak{U}} 的最末 m-r 個元全部為零。等價的說法是,當 m>r,方程式 A\mathbf{x}=\mathbf{b} 有解的充要條件是 \mathbf{b} 正交於 A 的最後 m-r 個左奇異向量,即 \mathbf{u}_{k}^T\mathbf{b}=0k=r+1,r+2,\ldots,m

 
情況一,如果 \mathbf{b} 滿足上述方程式的有解條件,則

U^T\mathbf{b}=\begin{bmatrix}    \mathbf{u}_1^T\mathbf{b}&\cdots&\mathbf{u}_r^T\mathbf{b}&0&\cdots&0    \end{bmatrix}^T

借助 \Sigma 是對角矩陣的特性,立即有

[\mathbf{x}]_{\mathfrak{V}}=V^T\mathbf{x}=\begin{bmatrix}    \displaystyle\frac{\mathbf{u}_1^T\mathbf{b}}{\sigma_1}&\cdots&\displaystyle\frac{\mathbf{u}_r^T\mathbf{b}}{\sigma_r}&0&\cdots&0    \end{bmatrix}^T

將上式左乘 V,便得到解向量

\begin{aligned}  \mathbf{x}&=V[\mathbf{x}]_{\mathfrak{V}}=\begin{bmatrix}    \mathbf{v}_1&\cdots&\mathbf{v}_r&\mathbf{v}_{r+1}&\cdots&\mathbf{v}_n    \end{bmatrix}\begin{bmatrix}    \displaystyle\frac{\mathbf{u}_1^T\mathbf{b}}{\sigma_1}\\[0.3em]    \vdots\\[0.3em]    \displaystyle\frac{\mathbf{u}_r^T\mathbf{b}}{\sigma_r}\\  0\\  \vdots\\  0  \end{bmatrix}\\    &=\frac{\mathbf{u}_1^T\mathbf{b}}{\sigma_1}\mathbf{v}_1+\cdots+\frac{\mathbf{u}_r^T\mathbf{b}}{\sigma_r}\mathbf{v}_r\end{aligned}

 
情況二,如果 \mathbf{b} 不屬於 A 的行空間 C(A),不存在滿足滿足 A\mathbf{x}=\mathbf{b} 的解,最小平方近似解發生於 A\hat{\mathbf{x}}=\mathbf{p}\mathbf{p}\mathbf{b}C(A) 的投影,以座標向量表示的方程式為

\Sigma[\hat{\mathbf{x}}]_{\mathfrak{V}}=[\mathbf{p}]_{\mathfrak{U}}

座標向量 [\mathbf{p}]_{\mathfrak{U}} 唾手可得,不過就是捨去 U^T\mathbf{b} 的最後 m-r 個元,因此與前述情況一滿足有解條件時使用的式子相同!換言之,最小平方近似解也有下面這個形式:

\hat{\mathbf{x}}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i

所以不論方程式是否有確定解或近似解,我們都可以使用上式計算。

 
n>rA 不具有線性獨立的行向量,或者說 A 的列空間 C(A^T) 未能充滿整個 \mathbb{R}^n,對於 j>r,就有

A\mathbf{v}_j=U\Sigma V^T\mathbf{v}_j=U\Sigma\mathbf{e}_j=\mathbf{0}

因為 \Sigma 的最右 n-r 行皆為零行,\mathbf{e}_j 是第 j 元為 1 的標準基底向量。所以,向量集 \{\mathbf{v}_{r+1},\mathbf{v}_{r+2},\ldots,\mathbf{v}_n\} 構成了 A 的零空間基底,故其線性組合仍屬於零空間 N(A)。當 n>r 時,不存在唯一的確定解或最小平方近似解,合併特殊解與齊次解,方程式 A\mathbf{x}=\mathbf{b} 的一般最小平方解為

\hat{\mathbf{x}}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i+\sum_{i=r+1}^n c_i\mathbf{v}_i

上式中權重 c_{r+1},\ldots,c_n 為任意數。當然,如果 n=r,第二個加總項消失,方程式便有唯一解。

 
下面用一個例子來說明,給出

A=\begin{bmatrix}    1&0&0&0&2\\    0&0&3&0&0\\    0&0&0&0&0\\    0&4&0&0&0    \end{bmatrix}

奇異值分解的 U\SigmaV 分別為

U=\begin{bmatrix}    0&0&1&0\\    0&1&0&0\\    0&0&0&1\\    1&0&0&0    \end{bmatrix},~ \Sigma=\begin{bmatrix}    4&0&0&0&0\\    0&3&0&0&0\\    0&0&\sqrt{5}&0&0\\    0&0&0&0&0    \end{bmatrix},~ V=\begin{bmatrix}    0&0&1/\sqrt{5}&0&-2/\sqrt{5}\\    1&0&0&0&0\\    0&1&0&0&0\\    0&0&0&1&0\\    0&0&2/\sqrt{5}&0&1/\sqrt{5}    \end{bmatrix}

此例 m=4n=5r=3,給出 \mathbf{b}=\begin{bmatrix}    1&1&1&1    \end{bmatrix}^TA\mathbf{x}=\mathbf{b} 無解,最小平法近似為

\hat{\mathbf{x}}=\frac{1}{4}\begin{bmatrix}    0\\    1\\    0\\    0\\    0    \end{bmatrix}+\frac{1}{3}\begin{bmatrix}    0\\    0\\    1\\    0\\    0\end{bmatrix}+\frac{1}{\sqrt{5}}\begin{bmatrix}    1/\sqrt{5}\\    0\\    0\\    0\\    2/\sqrt{5}\end{bmatrix}+c_4\begin{bmatrix}    0 \\    0\\    0\\    1\\    0\end{bmatrix}+c_5\begin{bmatrix}    -2/\sqrt{5}\\    0 \\    0\\    0\\    1/\sqrt{5}    \end{bmatrix}

 
我們知道 \mathbf{v}_1,\ldots,\mathbf{v}_n 是單範正交基底向量,任意屬於 \mathbb{R}^n 空間的向量有唯一表示式:

\mathbf{v}=d_1\mathbf{v}_1+\cdots+d_n\mathbf{v}_n

且向量長度平方為

\Vert\mathbf{v}\Vert^2=\mathbf{v}^T\mathbf{v}=d_1^2+\cdots+d_n^2

在一般解中,要得到具有最小長度的解向量可設所有 c_i=0,由此也推論出屬於 A 列空間的方程式解是唯一的,且該解是所有解中長度最小者,以 \mathbf{x}^{+} 表示,亦即

\mathbf{x}^{+}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i

將上式表示為矩陣乘法

\mathbf{x}^{+}=\begin{bmatrix}    \mathbf{v}_1&\cdots&\mathbf{v}_r&\cdots&\mathbf{v}_n    \end{bmatrix}\begin{bmatrix}    1/\sigma_1&~&~&~&~\\    ~&\ddots&~&~&~\\    ~&~&1/\sigma_r&~&~\\    ~&~&~&~&~    \end{bmatrix}\begin{bmatrix}    \mathbf{u}_1^T\\    \vdots\\    \mathbf{u}_r^T\\    \vdots\\    \mathbf{u}_m^T    \end{bmatrix}\mathbf{b}

n\times m 階對角矩陣 \Sigma^{+} 的前 r 個主對角元為 1/\sigma_1,\ldots,1/\sigma_r,就有

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

A 的僞逆矩陣 (pseudoinverse) 即定義為下面的 n\times m 階矩陣:

A^{+}=V\Sigma^{+}U^T

我們稱它為僞逆矩陣的原因是,對於任意矩陣 A,總是存在長度最小的近似解 \mathbf{x}^{+}=A^{+}\mathbf{b}。上例中,

\hat{\mathbf{x}}^{+}=A^{+}\mathbf{b}=\begin{bmatrix}    1/5&0&0&0\\    0&0&0&1/4\\    0&1/3&0&0\\    0&0&0&0\\    2/5&0&0&0    \end{bmatrix}\begin{bmatrix}    1\\1\\1\\1    \end{bmatrix}=\begin{bmatrix}    1/5\\    1/4\\    1/3\\    0\\    2/5    \end{bmatrix}

 
最後,我將四種線性方程解的結構整理於下,相關的討論請見“由簡約列梯形式判斷線性方程解的結構”。考慮線性方程 A\mathbf{x}=\mathbf{b}Am\times n 階矩陣,\mathrm{rank}A=r

 
(1) r=m=n

方程式有唯一解

{\mathbf{x}}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i

也就是 \mathbf{x}=A^{-1}\mathbf{b}

 
(2) m>rn=r

方程式有唯一解 (若 \mathbf{b} 屬於行空間 C(A)) 或唯一最小平方近似解 (若 \mathbf{b} 不屬於行空間 C(A)),形式皆為

\hat{\mathbf{x}}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i

也就是 \hat{\mathbf{x}}=(A^TA)^{-1}A^T\mathbf{b},參見“從線性變換解釋最小平方近似”。

 
(3) m=rn>r

方程式有無窮多解,一般解為

\mathbf{x}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i+\sum_{i=r+1}^n c_i\mathbf{v}_i

其中特殊解 \mathbf{x}_p=\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i 屬於列空間 C(A^T),也可以表示為 \mathbf{x}_p=A^T(AA^T)^{-1}\mathbf{b},參見“每週問題 May 4, 2009”。

 
(4) m>rn>r

這是最一般的情況,方程式可能有無限多解 (若 \mathbf{b} 屬於行空間 C(A)) 或無限多最小平方解 (若 \mathbf{b} 不屬於行空間 C(A)),形式為

\hat{\mathbf{x}}=\displaystyle\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i+\sum_{i=r+1}^n c_i\mathbf{v}_i

其中特殊最小平方解 \mathbf{x}^{+}=\sum_{i=1}^r\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i 屬於列空間 C(A^T),也可以表示為 \mathbf{x}^{+}=A^{+}\mathbf{b}

Advertisements
This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , , . Bookmark the permalink.

3 則回應給 SVD 於剖析線性方程的應用

  1. Liang Dai 說:

    非常好的阐述,svd是灵魂。谢谢于老师!

  2. Jerry Huang 說:

    如果b是一零向量,那x除了是零向量外,還會有其他的解嗎?

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s