奇异值分解求解线性方程组
奇异值分解（SVD）：
设\(\boldsymbol{A} \in \mathbb{C}^{m \times n}_r\)，则存在正交矩阵\(\boldsymbol{U} \in \mathbb{C}^{m \times m}\)与正交矩阵\(\boldsymbol{V} \in \mathbb{C}^{n \times n}\)使得\(\boldsymbol{A} = \boldsymbol{U} \left[ \begin{matrix} \boldsymbol{\Sigma}_r & \boldsymbol{0} \\ \boldsymbol{0} & \boldsymbol{0} \end{matrix}\right] \boldsymbol{V}^T = \boldsymbol{U} \boldsymbol{D} \boldsymbol{V}^T\)，其中\(\boldsymbol{\Sigma_r}= diag(\sigma_1,...,\sigma_r)\)是矩阵\(\boldsymbol{A}\)的正奇异值
- 通过奇异值分解将原问题转换为最小二乘问题，可以求解超定线性方程组
1 求解齐次线性方程组（\(\boldsymbol{A}\boldsymbol{x}= \boldsymbol{0}\)）
问题等价于\(\min _{\boldsymbol{x}}|| \boldsymbol{A}\boldsymbol{x}||^2\)，则 $$ \[\begin{aligned} & \min _{\boldsymbol{x}}|| \boldsymbol{A}\boldsymbol{x}||^2 \\ = & \min _{\boldsymbol{x}} || \boldsymbol{U} \boldsymbol{D} \boldsymbol{V}^T \boldsymbol{x}||^2 \\ = & \min _{\boldsymbol{x}} || \boldsymbol{D} \boldsymbol{V}^T \boldsymbol{x}||^2 \\ \end{aligned} \tag{1}\]$$ 令\(\boldsymbol{y} = \boldsymbol{V}^T \boldsymbol{x}\)，则\((1)\)式变为\(\min _{\boldsymbol{y}} || \boldsymbol{D} \boldsymbol{y} ||^2 = \min _{\boldsymbol{y}}\left(\sigma_1^2y_1^2 + \sigma_2^2y_2^2 + ... + \sigma_r^2y_r^2\right)\)，其中\(r <= n\)
因为\(\sigma_1 > \sigma_2 > ... > \sigma_r > 0\)，所有不管\(r\)是否等于\(n\)，在\(|| \boldsymbol{x} ||= 1\)的前提下的最优解均在\(\boldsymbol{y}= [0,0,...,1]^T\)时取得（\(r=n\)时存在最小二乘解，\(r<n\)时存在数值解），此时\(\boldsymbol{x} = \boldsymbol{V}\boldsymbol{y}\) ，即\(\boldsymbol{V}\)的最后一列
2 求解非齐次线性方程组（\(\boldsymbol{A}\boldsymbol{x}= \boldsymbol{b}\)）
问题等价于\(\min _{\boldsymbol{x}} || \boldsymbol{A}\boldsymbol{x}-\boldsymbol{b}||^2\)，则 \[ \begin{aligned} & \min _{\boldsymbol{x}}|| \boldsymbol{A}\boldsymbol{x}-\boldsymbol{b}||^2 \\ = & \min _{\boldsymbol{x}} || \boldsymbol{U} \boldsymbol{D} \boldsymbol{V}^T \boldsymbol{x} -\boldsymbol{b} ||^2 \\ = & \min _{\boldsymbol{x}} || \boldsymbol{D} \boldsymbol{V}^T \boldsymbol{x} -\boldsymbol{U}^T\boldsymbol{b} ||^2 \\ \end{aligned} \tag{2} \] 令\(\boldsymbol{y} = \boldsymbol{V}^T \boldsymbol{x}\)，\(\boldsymbol{c} = \boldsymbol{U}^T \boldsymbol{b}\)，则\((2)\)式变为\(\min _{\boldsymbol{y}} || \boldsymbol{D} \boldsymbol{y} - \boldsymbol{c}||^2 = \min _{\boldsymbol{y}}\left( \sum_{i=1}^r(\sigma_i y_i - c_i)^2+\sum_{i=r+1}^m c_i^2 \right)\)
当\(y_i = \frac{c_i}{\sigma_i}(i = 1,...,r)\)而\(y_i(i=r+1,...,n)\)为任意值时求得最优解
参考文献
- 王磊.矩阵基本理论与应用[M]
- https://blog.csdn.net/Ansel_Lee/article/details/107643789
- https://blog.csdn.net/MyArrow/article/details/53780972