台湾 || 语言: 大陆简体港澳繁體台灣正體

矩陣SVD分解（理論部分II——利用SVD求解最小二乘問題）

雪花臺灣 2019-06-10 07:00

對於給定的線性方程組

（LS)

按

的特性分開討論：

是一個方陣；1.1 ，此時線性方程組(LS)有唯一解： $m{x}=A^{-1}m{b}$ 1.2 .1.2.1 如果，此時線性方程組(LS)有無窮多個解

$m{x}=k_1m{xi}_1+cdots+k_{n-r}m{xi}_{n-r}+m{xi}_0$
其中 $k_1,cdots,k_{n-r}$ 是任意常數， $m{xi}_1,cdots,m{xi}_{n-r}$ 是的個線性無關解， $m{xi}_0$ 是滿足 $Am{xi}_0=m{b}$ 的一個向量（也稱為特殊解）這兩種情形都可用 Gauss 消去法求解。
$Ain C^{m imes n},~~m>n$ . 此時方程組(LS)稱為超定方程組（overdetermined systems)，這種方程一般來說無解，但可求其最小二乘解，即所謂的最小二乘問題（Least Square Problem）2.1 ，此時在方程組(LS)的兩端同時左乘有 $A^HAm{x}=A^Hm{b}Rightarrow m{x}=left(A^HA ight)^{-1}A^Hm{x}=A^{dag}m{b}$

其中 $A^{dag}=left(A^HA ight)^{-1}A^H$ 稱為的廣義逆.
這種方法的理論依據(用內積表示2-範數，求其駐點，再證明此駐點必是最小值點即可)是 $m{x}=argmin_{m{z}in C^n}|Am{z}-m{b}|_2Leftrightarrow A^HAm{x}=A^Hm{x}$ $A^HAm{x}=A^Hm{x}$ 稱為線性方程組(LS)的正規方程組 。正規方程組的求解是數值不穩定的。用SVD求解：設的SVD為

$A=USigma V^H=(U_1,U_2)left(egin{array}{c}Sigma_1\ 0end{array} ight)V^H$
記 $V^Hm{x}=m{y}, ~~U_1^Hm{b}=m{b}_1, ~~U_2^Hm{b}=m{b}_2$ 則 $|Am{x}-m{b}|_2^2 =|USigma m{y}-m{b}|_2^2=|Sigma m{y}-U^Hm{b}|_2^2=left|left(egin{array}{c}Sigma_1\ 0end{array} ight)m{y}-left(egin{array}{c} m{b}_1\ m{b}_2end{array} ight) ight|_2^2\ =|Sigma_1m{y}-m{b}_1|_2^2+|m{b}_2|_2^2$ 當給定，則 $|m{b}_2|_2^2=|U_2^Hm{b}|_2^2$ 是一個常數，為使 $|Am{x}-m{b}|_2^2=min$ 只要取

$Sigma_1m{y}=m{b}_1Leftrightarrow m{y}=Sigma_1^{-1}m{b}_1=Sigma_1^{-1}U_1^Hm{b}$
這就得到線性方程組(LS)的最小二乘解 $m{x}=VSigma_1^{-1}U_1^Hm{b}=sum_{k=1}^n frac{m{u}_k^Hm{b}}{sigma_k}m{v}_k$ 2.2 . 此時線性方程組(LS)稱為虧秩方程組. 這樣的方程組有最小二乘解，但最小二乘解不再唯一。此時的SVD可表示為 $A=USigma V^H=(U_1,U_2)left(egin{array}{cc}Sigma_1 & 0\ 0 & 0end{array} ight)left(egin{array}{c}V_1^H\ V_2^Hend{array} ight)=U_1Sigma_1V_1^H,$ 其中 $U_1in C^{m imes r}, U_2in C^{m imes (n-r)}$ 是列標準正交矩陣， $V_1in C^{n imes r},V_2in C^{n imes (n-r)}$ 是列標準正交矩陣，是可逆矩陣, $|Am{x}-m{b}|_2^2=left| left(egin{array}{cc}Sigma_1 & 0\ 0 & 0end{array} ight)left(egin{array}{c}V_1^Hm{x}\ V_2^Hm{x}end{array} ight)-left(egin{array}{c}U_1^Hm{b}\ U_2^Hm{b}end{array} ight) ight|_2^2=|Sigma_1m{y}_1-m{b}_1|_2^2+|m{b}_2|_2^2$ 其中 $m{y}_i=V_i^Hm{x}, m{b}_i=U_i^Hm{b},i=1,2.$ 要使得上式達到極小, 只要 $m{y}=left(egin{array}{c}m{y}_1\ m{y}_2end{array} ight)=left(egin{array}{c}Sigma_1^{-1}m{b}_1\ m{y}_2end{array} ight)$ 其中 $m{y}_2$ 可以任意取. 特別地，如果取 $m{y}_2=m{0}$ ，此時方程組(LS) 有一個解 $m{x}=(V_1 ,V_2 )left(egin{array}{c}m{y}_1\ m{y}_2end{array} ight)= V_1Sigma_1^{-1}U_1^Hm{b}$ 這個解是所有滿足 $|Am{x}-m{b}|_2^2=min$ 的中範數最小的，也稱為最小二乘問題的最小二範數解。
$Ain C^{m imes n},~~m<n$ . 此時線性方程組(LS)稱為欠定方程組（underdetermined systems)。若 , 則的SVD可表示為 $A=U(Sigma_1,0)left(egin{array}{c}V_1^H\ V_2^Hend{array} ight)$ 則 $Am{x}=U(Sigma_1,0)left(egin{array}{c}V_1^Hm{x}\V_2^Hm{x}end{array} ight)=U(Sigma_1,0)left(egin{array}{c} m{y}_1\ m{y}_2end{array} ight)=USigma_1m{y}_1$ 於是 $Am{x}=m{b}Leftrightarrow USigma_1m{y}_1=m{b}Rightarrow m{y}_1=Sigma_1^{-1}U^Hm{b}$ 即 $m{x}=V_1Sigma_1^{-1}U^Hm{b}$

推薦閱讀：

相關文章