矩阵分析与应用-6.2-奇异值分解-Section1
前言
本文学习过程来源是《矩阵分析与应用-张贤达》一书. 可以通过 z-lib 下载.
一、奇异值分解及其解释
1. 奇异值分解定义
对于任意复长方矩阵都可以进行奇异值分解.
定理 1 (矩阵的奇异值分解) : 令 \(A \in R^{m \times n}\) ( 或 \(C^{m \times n}\) ), 则存在正交 (或酉) 矩阵 \(U \in R^{m \times m}\) 和 \(V \in R^{n \times n}\) ( 或 \(C^{n \times n}\) ) 使得
\[ A = U \Sigma V^{\mathrm{T}} \ ( \ 或 \ U \Sigma V^{\mathrm{H}} ) \tag{1} \]
式子中
\[ \Sigma = \begin{bmatrix} \Sigma_1& O\\ O&O \end{bmatrix} \tag{2} \]
且 \(\Sigma_1 = \mathrm{diag}(\sigma_1,\sigma_2,\cdots,\sigma_r)\), 其对角元素按照顺序
\[ \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0, \quad r = \mathrm{rank}(A) \tag{3} \]
排列, 这些值自然也被称作奇异值.
定义 1 : 矩阵 \(A_{m \times n}\) 的奇异值 \(\sigma_i\) 称为单奇异值, 若 \(\sigma_i \neq \sigma_j, \forall j \neq i\)
2. 奇异值和奇异值分解解释及其标记
\(n \times n\) 矩阵 \(V\) 为酉矩阵, 用 \(V\) 右乘式 \(A = U \Sigma V^{\mathrm{T}}\) 得到 \(AV=U\Sigma\), 其列向量形式为
\[ Av_i = \left\{\begin{matrix} \sigma_iu_i& i=1,2,\cdots,r\\ 0& i=r+1,r+2,\cdots,n \end{matrix}\right. \tag{4} \]
因此, \(V\) 的列向量 \(v_i\) 称为矩阵 \(A\) 的右奇异向量, \(V\) 称为 \(A\) 的右奇异向量矩阵.
\(m \times m\) 矩阵 \(U^{\mathrm{H}}\) 为酉矩阵, 用 \(U^{\mathrm{H}}\) 左乘式 \(A = U \Sigma V^{\mathrm{T}}\) 得到 \(U^{\mathrm{H}}A=\Sigma V\), 其列向量形式为
\[ u_i^{\mathrm{H}}A = \left\{\begin{matrix} \sigma_iv_i^{\mathrm{T}}& i=1,2,\cdots,r\\ 0& i=r+1,r+2,\cdots,n \end{matrix}\right. \tag{5} \]
因此, \(U\) 的列向量 \(u_i\) 称为矩阵 \(A\) 的左奇异向量, \(U\) 称为 \(A\) 的左奇异向量矩阵.
矩阵 \(A\) 的奇异值分解式子也可以改成向量形式
\[ A= \sum_{i=1}^{r}\sigma_i u_i v_i^{\mathrm{H}} \tag{6} \]
这种叫 \(A\) 的并向量 (奇异值) 分解
观察到奇异值分解式子, 有
\[ AA^{\mathrm{H}} = U \Sigma^2U^{\mathrm{H}} \tag{7} \]
表明, \(m \times n\) 矩阵 \(A\) 的奇异值 \(\sigma_i\) 是矩阵乘积 \(AA^{\mathrm{H}}\) 的特征值的正平方根.
当矩阵 \(A\) 的秩 \(r = \mathrm{rank}(A) < \min\{m,n\}\) 时, 由于奇异值 \(\sigma_{r+1} = \sigma_{r+2} = \cdots =\sigma_h = 0, h = \min\{m,n\}\), 奇异值分解公式可以简化为
\[ A=U_r\Sigma_rV_r^{\mathrm{H}} \tag{8} \]
式子中
\[ U_r = [u_1,u_2,\cdots,u_r], \quad V_r = [v_1,v_2,\cdots,v_r], \quad \Sigma_r = \mathrm{diag}[\sigma_1,\sigma_2,\cdots,\sigma_r] \]
式子 (7) 称为矩阵 \(A\) 的截尾奇异值分解或薄奇异值分解. 那么之前那个就叫做全奇异值分解.
如果矩阵 \(A_{m \times n}\) 具有秩 \(r\), 则
\(m \times m\) 酉矩阵 \(U\) 的前 \(r\) 列组成矩阵 \(A\) 的列空间的标准正交基
\(n \times n\) 酉矩阵 \(V\) 的前 \(r\) 列组成矩阵 \(A\) 的行空间 (或 \(A^{\mathrm{H}}\) 的列空间) 的标准正交基
\(V\) 的后 \(n - r\) 列组成矩阵 \(A\) 的零空间的标准正交基
\(U\) 的后 \(m - r\) 列组成矩阵 \(A^{\mathrm{H}}\) 的零空间的标准正交基
3. 矩阵的秩亏缺
定理 2 : 令 \(A \in C^{m \times n} (m > n)\) 的奇异值为
\[ \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r \ge 0 \]
则
\[ \sigma_k = \min_{E \in C^{m \times n}} \{ \lVert E \rVert_{\mathrm{F}} : {\mathrm{rank}}(A+E) \le k -1\}, \quad k=1,2,\cdots,n \tag{9} \]
并且存在一满足 \(\lVert E \rVert_{\mathrm{F}} = \sigma_k\) 的误差矩阵 \(E\) 使得
\[ \mathrm{rank}(A+E_k) = k-1, \quad k = 1,2,\cdots,n \]
矩阵的奇异值如果为零, 说明这个矩阵一定不是行满秩或者列满秩. 这就叫矩阵的秩亏缺.
对于方阵用行列式就可以很直观看出来, 对于非方阵就需要考虑线性变换.
二、奇异值的性质
1. 矩阵变形与奇异值变化
令矩阵 \(A\) 和矩阵 \(B\) 均为 \(m \times n\) 矩阵, 并且 \(r_A = \mathrm{rank}(A), p = \min\{m,n\}\)
设矩阵 \(A\) 的奇异值排列为
\[ \sigma_{\mathrm{max}} = \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_{p-1} \ge \sigma_p = \sigma_{\mathrm{min}} \ge 0 \tag{10} \]
并且用 \(\sigma_i(B)\) 表示矩阵 \(B\) 的第 \(i\) 个奇异值.
矩阵的各种变形与奇异值的变化有以下关系.
\(m \times n\) 矩阵 \(A\) 的共轭转置 \(A^\mathrm{H}\) 的奇异值分解为
\[ A^\mathrm{H} = V \Sigma^\mathrm{T} U^\mathrm{H} \tag{11} \]
即 \(A\) 和 \(A^\mathrm{H}\) 有完全相同的奇异值.
\(P\) 和 \(Q\) 分别为 \(m \times m\) 和 \(n \times n\) 酉矩阵时, \(PAQ^\mathrm{H}\) 的奇异值分解由
\[ PAQ^\mathrm{H} = \bar{U} \Sigma \bar{V}^\mathrm{H} \tag{12} \]
给出, 其中, \(\bar{U} = PU, \bar{V}=QV\). 就是说, 矩阵 \(PAQ^\mathrm{H}\) 与 \(A\) 具有相同的奇异值, 即奇异值具有酉不变性, 但奇异向量不同. 这个性质和特征值、特征向量之间的关系非常相似.
\(A^\mathrm{H}A, AA\mathrm{H}\) 的奇异值分解分别为
\[ AA^\mathrm{H} = V \Sigma^\mathrm{T}\Sigma V^\mathrm{H}, \quad AA^\mathrm{H} = U \Sigma\Sigma^\mathrm{T} U^\mathrm{H} \tag{13} \]
其中
\[ \Sigma^\mathrm{T}\Sigma = \mathrm{diag}(\sigma_1^2,\sigma_2^2,\cdots,\sigma_r^2,\overbrace{0,\cdots,0}^{n - r个}) \tag{14} \]
\[ \Sigma\Sigma^\mathrm{T} = \mathrm{diag}(\sigma_1^2,\sigma_2^2,\cdots,\sigma_r^2,\overbrace{0,\cdots,0}^{m - r个}) \tag{15} \]
\(m \times n\) 矩阵 \(A\) 的奇异值分解与 \(n \times m\) 维 \(\mathrm{Moore-Penrose}\) 广义逆矩阵 \(A^\dagger\) 之间存在下列关系
\[ A^\dagger = V \Sigma^\dagger U^\mathrm{H} \tag{16} \]
其中 \(\Sigma^\dagger = \begin{bmatrix} \Sigma^{-1}& O\\ O&O \end{bmatrix}\)
2. 奇异值和矩阵性质之间的关系
定理 3 : 令 \(A\) 是一个 \(m \times n\) 矩阵, 其奇异值 \(\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r\), 其中, \(r = \min\{m,n\}\). 若 \(p \times q\) 矩阵 \(B\) 是 \(A\) 的子矩阵, 其奇异值 \(\gamma_1 \ge \gamma_2 \ge \cdots \ge \gamma_{\min\{p,q\}}\) 则
\[ \sigma_i \ge \gamma_i , \quad i=1,2,\cdots,\min\{p,q\} \tag{17} \]
并且
\[ \gamma_i \ge \sigma_{i+(m-p)+(n-1)}, \quad i \le \min\{p+1-m,p+1-n\} \tag{18} \]
奇异值与范数的关系
矩阵 \(A\) 的谱范数等于 \(A\) 的最大奇异值, 即
\[ \lVert A \rVert_{\mathrm{spec}} = \sigma_1 \tag{19} \]
又有 \(\lVert U^{\mathrm{H}}AV \rVert_{\mathrm{F}} = \lVert A \rVert_{\mathrm{F}}\), 故有
\[ \lVert A \rVert_{\mathrm{F}} = \left [ \sum_{i=1}^{m} \sum_{j=1}^{n}|a_{ij}|^2 \right ] ^{1/2} \tag{20} \]
\[ \lVert A \rVert_{\mathrm{F}} = \sqrt{\sigma_1^2+\sigma_2^2+\cdots+\sigma_r^2} \tag{21} \]
考虑矩阵 \(A\) 的秩 \(k\) 近似, 并将其记作 \(A_k\), 其中, \(k < r = \mathrm{rank}(A)\). 矩阵 \(A_k\) 定义如下:
\[ A_k = \sum_{i=1}^{k}\sigma_iu_iv_i^{\mathrm{H}}, \quad k < r \]
则 \(A\) 与秩为 \(k\) 的任一矩阵 \(B\) 之差的 \(l_1\) 和 \(\mathrm{Frobineus}\) 范数分别为
\[ \min_{\mathrm{rank}(B)=k} \lVert A-B \rVert_1 = \lVert A-A_k \rVert_1 =\sigma_{k+1} \tag{22} \]
和
\[ \min_{\mathrm{rank}(B)=k} \lVert A-B \rVert_{\mathrm{F}}^2 = \lVert A-A_k \rVert_{\mathrm{F}}^2 =\sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots + \sigma_{r}^2 \tag{23} \]
奇异值与行列式的关系
\[ |\mathrm{det}(A)| = |\mathrm{det}\Sigma| = \sigma_1 \sigma_2 \cdots \sigma_n \tag{24} \]
还有一些不等式关系, 对于一个 \(n \times n\) 矩阵 \(A\)
\[ \left.\begin{matrix} n\sigma_1 \ge \lVert A \rVert_{\mathrm{F}} \ge \sigma_1 \\ \sigma_1^n \ge \sigma_1^{n-1}\sigma_n \ge |\mathrm{det}(A)| \ge \sigma_n^n\\ \lVert A \rVert_{\mathrm{F}} \ge \sigma_1 \ge |\mathrm{det}(A)|^{1/n} \\ |\mathrm{det}(A)|^{1/n} \ge \sigma_n \ge |\mathrm{det}(A)| / \lVert A \rVert_{\mathrm{F}}^{n-1}\\ \lVert A \rVert_{\mathrm{F}}^n / |\mathrm{det}(A)| \ge \sigma_1 / \sigma_2 \ge \max \{1, \frac{1}{n} \lVert A \rVert_{\mathrm{F}}/ |\mathrm{det}(A)|^{1/n}\} \end{matrix}\right\} \tag{25} \]
奇异值与条件数的关系
对于一个 \(m \times n\) 矩阵 \(A\), 其条件数也可以利用奇异值定义为
\[ \mathrm{cond}(A) = \sigma_1/\sigma_p, \quad p = \min\{m,n\} \tag{26} \]
条件数在之前也没有接触过, 就写到这里作罢.
奇异值与特征值的关系
设 \(n \times n\) 对称方阵 \(A\) 的特征值为 \(\lambda_1,\lambda_2,\cdots,\lambda_n (|\lambda_1| \ge |\lambda_2| \ge \cdots \ge |\lambda_n|)\), 奇异值为 \(\sigma_1,\sigma_2,\cdots,\sigma_n(\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0)\), 则 \(\sigma_1 \ge |\lambda_i| \ge \sigma_n (i=1,2,\cdots,n), \mathrm{cond}(A) \ge |\lambda_1| / |\lambda_n|\)