This chapter focuses on the proof and operation of SVD, along with the geometric significance and the low-rank approximation of matrices, which are closely connected to the applications of SVD. 本章重点介绍 SVD 的证明和运算,以及矩阵的几何意义和低秩近似,它们与 SVD 的应用密切相关。
Definition 定义
Let A be any m xx nm \times n matrix with real entries, A can be expressed in the product of three matrices 设 A 是任何 m xx nm \times n 具有实数项的矩阵,A 可以用三个矩阵的乘积表示
Where: 哪里:
U is an mxxm\mathrm{m} \times \mathrm{m} orthogonal matrix. Its columns u_(i)\mathrm{u}_{\mathrm{i}} are called the left singular vectors of AA. U 是 mxxm\mathrm{m} \times \mathrm{m} 正交矩阵。它的列 u_(i)\mathrm{u}_{\mathrm{i}} 称为 的 AA 左奇异向量。 Sigma\Sigma is an mxxn\mathrm{m} \times \mathrm{n} diagonal matrix with non-negative real entries sigma_(i)\sigma_{\mathrm{i}} on the diagonal, which are the singular values of A. Generally, we have sigma_(1) >= sigma_(2) >= dots >= sigma_(p) >= 0\sigma_{1} \geq \sigma_{2} \geq \ldots \geq \sigma_{p} \geq 0, p=min(m,n)\mathrm{p}=\min (\mathrm{m}, \mathrm{n}). Sigma\Sigma 是一个 mxxn\mathrm{m} \times \mathrm{n} 对角矩阵,对角线上有非负实数项 sigma_(i)\sigma_{\mathrm{i}} ,它们是 A 的奇异值。通常,我们有 sigma_(1) >= sigma_(2) >= dots >= sigma_(p) >= 0\sigma_{1} \geq \sigma_{2} \geq \ldots \geq \sigma_{p} \geq 0 、 p=min(m,n)\mathrm{p}=\min (\mathrm{m}, \mathrm{n}) 。
V is an mxxn\mathrm{m} \times \mathrm{n} orthogonal matrix. Its columns v_(i)\mathrm{v}_{\mathrm{i}} are called the right singular vectors of A . V 是 mxxn\mathrm{m} \times \mathrm{n} 正交矩阵。它的列 v_(i)\mathrm{v}_{\mathrm{i}} 称为 A 的右奇异向量。
Proof 证明
A^(T)AA^{T} A is positive semidefinite (having all non-negative eigenvalues) A^(T)AA^{T} A 为正半定(具有所有非负特征值)
Proof: Let AinR^(mxxn),x\mathrm{A} \in \mathrm{R}^{\mathrm{m} \times \mathrm{n}}, \mathrm{x} is an n -dimentional column vector, 证明: 设 AinR^(mxxn),x\mathrm{A} \in \mathrm{R}^{\mathrm{m} \times \mathrm{n}}, \mathrm{x} 是一个 n 维列向量,
{:[x^(T)(A^(T)A)x=x^(T)A^(T)Ax],[=(Ax)^(T)(Ax)],[=|Ax|^(2) >= 0]:}\begin{gathered}
x^{T}\left(A^{T} A\right) x=x^{T} A^{T} A x \\
=(A x)^{T}(A x) \\
=|A x|^{2} \geq 0
\end{gathered}
So A^(T)AA^{T} A is positive semidefinite. 正半定也是如此 A^(T)AA^{T} A 。
Creating a set of bases in the column space of A 在 A 的列空间中创建一组基
Suppose AA is an m xx nm \times n real matrix. Since A^(T)AA^{T} A is a real symmetric matrix (diagonalizable and having orthogonal eigenvectors), let the n eigenvalues of A^(T)AA^{T} \mathrm{~A} be lambda_(1) >= lambda_(2) >= dots >= lambda_(n) >= 0\lambda_{1} \geq \lambda_{2} \geq \ldots \geq \lambda_{n} \geq 0 ( A^(T)A\mathrm{A}^{\mathrm{T}} \mathrm{A} is positive semidefinite, proven in step 1 ). From the eigen decomposition of AA, there exists an n xx nn \times n orthogonal matrix VV, such that 假设 AA 是一个 m xx nm \times n 实矩阵。由于 A^(T)AA^{T} A 是一个实对称矩阵(可对角化且具有正交特征向量),因此设 be lambda_(1) >= lambda_(2) >= dots >= lambda_(n) >= 0\lambda_{1} \geq \lambda_{2} \geq \ldots \geq \lambda_{n} \geq 0 的 A^(T)AA^{T} \mathrm{~A} n 个特征值( A^(T)A\mathrm{A}^{\mathrm{T}} \mathrm{A} 是正半定的,在步骤 1 中得到证明)。从 AA 的特征分解 中,存在一个 n xx nn \times n 正交矩阵 VV ,使得
Let V=[v_(1)v_(2)cdotsV_(n)]\mathrm{V}=\left[\mathrm{v}_{1} \mathrm{v}_{2} \cdots \mathrm{~V}_{\mathrm{n}}\right] (the eigenvectors of A^(T)A\mathrm{A}^{\mathrm{T}} \mathrm{A} ). 设 V=[v_(1)v_(2)cdotsV_(n)]\mathrm{V}=\left[\mathrm{v}_{1} \mathrm{v}_{2} \cdots \mathrm{~V}_{\mathrm{n}}\right] ( A^(T)A\mathrm{A}^{\mathrm{T}} \mathrm{A} 的特征向量)。
Since V is an orthogonal matrix, to any n -dimentional column vector x , there is a unique set of value ( c_(1),c_(2),cdots,c_(n)c_{1}, c_{2}, \cdots, c_{n} ), such that 由于 V 是正交矩阵,因此对于任何 n 维列向量 x ,都有一组唯一的值 ( c_(1),c_(2),cdots,c_(n)c_{1}, c_{2}, \cdots, c_{n} ),使得
Else, to any i,j(i!=j)\mathrm{i}, \mathrm{j}(\mathrm{i} \neq \mathrm{j}), we have 否则,对于任何 i,j(i!=j)\mathrm{i}, \mathrm{j}(\mathrm{i} \neq \mathrm{j}) ,我们都有
(Av_(i))^(T)(Av_(j))=(A^(T)Av_(j))=lambda_(j)v_(j)=0\left(A v_{i}\right)^{T}\left(A v_{j}\right)=\left(A^{T} A v_{j}\right)=\lambda_{j} v_{j}=0
So Av_(i)_|_Av_(j)A v_{i} \perp \mathrm{Av}_{j}. That means {Av_(1),Av_(2),cdots,Av_(r)}\left\{\operatorname{Av}_{1}, \mathrm{Av}_{2}, \cdots, \mathrm{Av}_{\mathrm{r}}\right\} is a set of orthogonal bases of the column space of AA. 所以 Av_(i)_|_Av_(j)A v_{i} \perp \mathrm{Av}_{j} .这意味着 {Av_(1),Av_(2),cdots,Av_(r)}\left\{\operatorname{Av}_{1}, \mathrm{Av}_{2}, \cdots, \mathrm{Av}_{\mathrm{r}}\right\} 是 的列空间的一组正交基 AA 数。
Computing the length of Av_(i)\mathrm{Av}_{\mathrm{i}}, 计算 Av_(i)\mathrm{Av}_{\mathrm{i}} 的长度 ,
|Av_(i)|=sqrt(|Av_(i)|^(2))=sqrt(A^(T)Av_(i))=sqrt(lambda_(i)v_(i))=sqrt(lambda_(i))\left|A v_{i}\right|=\sqrt{\left|A v_{i}\right|^{2}}=\sqrt{A^{T} A v_{i}}=\sqrt{\lambda_{i} v_{i}}=\sqrt{\lambda_{i}}
So {(Av_(1))/(sqrt(lambda_(1))),(Av_(2))/(sqrt(lambda_(2))),cdots,(Av_(r))/(sqrt(lambda_(r)))}\left\{\frac{\mathrm{Av}_{1}}{\sqrt{\lambda_{1}}}, \frac{\mathrm{Av}_{2}}{\sqrt{\lambda_{2}}}, \cdots, \frac{\mathrm{Av}_{\mathrm{r}}}{\sqrt{\lambda_{\mathrm{r}}}}\right\} is a set of orthogonal bases with a length of 1 in the column space of A. 在 A 的列空间中,一组长度为 1 的正交底也是如此 {(Av_(1))/(sqrt(lambda_(1))),(Av_(2))/(sqrt(lambda_(2))),cdots,(Av_(r))/(sqrt(lambda_(r)))}\left\{\frac{\mathrm{Av}_{1}}{\sqrt{\lambda_{1}}}, \frac{\mathrm{Av}_{2}}{\sqrt{\lambda_{2}}}, \cdots, \frac{\mathrm{Av}_{\mathrm{r}}}{\sqrt{\lambda_{\mathrm{r}}}}\right\} 。
The final step 最后一步
To all i in{1,2,cdots,r}i \in\{1,2, \cdots, r\}, let u_(i)=(Av_(i))/(sqrt(lambda_(i)))u_{i}=\frac{\mathrm{Av}_{i}}{\sqrt{\lambda_{i}}}, and extend the set of bases to {u_(1),u_(2),cdots,u_(r),u_(r+1),cdots,u_(m)},u_(r+1)∼u_(m)\left\{u_{1}, u_{2}, \cdots, u_{r}, u_{r+1}, \cdots, u_{m}\right\}, u_{r+1} \sim u_{m} are the orthogonal bases of the null space of A (with a length of 1). The new set of bases is an orthogonal bases set of R^(mxxm)\mathrm{R}^{\mathrm{m} \times \mathrm{m}}. Computing AV: 对于所有 i in{1,2,cdots,r}i \in\{1,2, \cdots, r\} ,let u_(i)=(Av_(i))/(sqrt(lambda_(i)))u_{i}=\frac{\mathrm{Av}_{i}}{\sqrt{\lambda_{i}}} 和 extend 的基数集是 {u_(1),u_(2),cdots,u_(r),u_(r+1),cdots,u_(m)},u_(r+1)∼u_(m)\left\{u_{1}, u_{2}, \cdots, u_{r}, u_{r+1}, \cdots, u_{m}\right\}, u_{r+1} \sim u_{m} A 的零空间(长度为 1)的正交基数。新的基集是 R^(mxxm)\mathrm{R}^{\mathrm{m} \times \mathrm{m}} 的正交基集。计算 AV:
Let U=[u_(1)u_(2)cdotsu_(m)],sigma_(i)=sqrt(lambda_(i))U=\left[\mathrm{u}_{1} \mathrm{u}_{2} \cdots \mathrm{u}_{\mathrm{m}}\right], \sigma_{\mathrm{i}}=\sqrt{\lambda_{\mathrm{i}}}, so AV=U Sigma\mathrm{AV}=U \Sigma, so that 设