引言

在本章中，我们将考虑 m 行 n 矩阵 A 的奇异值分解（SVD）。我们假设不失一般性，m \geq n；如果 m < n，则考虑 A^*。如第§2.4节所述，这种分解可以写成

A = U \Sigma V^*, \tag{6.1}

其中 U = [u_1,\ldots,u_m] 是一个 m 行 m 列的酉矩阵， V = [v_1,\ldots,v_n] 是一个 n 行 n 列的酉矩阵， 而 \Sigma 是一个 m 行 n 列的对角矩阵，其对角线元素为 \Sigma_{ii} = \sigma_i，i=1,\ldots,n。 u_i 是左奇异向量， v_i 是右奇异向量， \sigma_i 是奇异值。 奇异值是非负的，并按降序排列，即 \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n \geq 0。 非零奇异值的数量 r 是 A 的秩。 如果 A 是实数矩阵，U 和 V 也是实的且正交的。

A = U \Sigma V^* 也可以写成 AV = U \Sigma 或 Av_i = u_i \sigma_i，i=1,\ldots,n。 A = U \Sigma V^* 也可以写成 A^* U= V \Sigma^* 或 A^*u_i = v_i \sigma_i，i=1,\ldots,n 以及 A^*u_i = 0，i=n+1,\ldots,m。

有几种“较小”版本的SVD经常被计算。 设 U_t = [u_1,\ldots,u_t] 是一个 m 行 t 列的矩阵，包含前 t 个左奇异向量， V_t = [v_1,\ldots,v_t] 是一个 n 行 t 列的矩阵，包含前 t 个右奇异向量， 以及 \Sigma_t = {\rm diag}(\sigma_1 ,\ldots, \sigma_t) 是一个 t 行 t 列的矩阵，包含前 t 个奇异值。 那么我们有以下几种SVD类型。

瘦SVD。

A = U_n \Sigma_n V_n^* 是 A 的瘦（或经济型）SVD。 当 n \ll m 时，瘦SVD比全SVD存储更小且计算更快。

紧凑SVD。

A = U_{r} \Sigma_{r} V_{r}^* 是 A 的紧凑SVD。 当 r \ll n 时，紧凑SVD比瘦SVD存储更小且计算更快。

截断SVD。

A_t = U_{t} \Sigma_{t} V_{t}^* 是 A 的秩-t 截断（或部分）SVD， 其中 t < r。 在所有秩-t 矩阵 B 中，B=A_t 是唯一的最小化 \Vert A - B \Vert _F 的矩阵，并且也最小化（可能不唯一） \Vert A - B \Vert _2。 当 t \ll r 时，截断SVD比紧凑SVD存储更小且计算成本更低，是应用中最常见的SVD形式。

瘦SVD也可以写成 A = \sum_{i=1}^n \sigma_i u_i v_i^*。 每个 (\sigma_i, u_i, v_i) 被称为奇异三元组。 紧凑和截断SVD可以类似地写成（求和从 i=1 到 r，或 i=1 到 t）。

A 的SVD与三个相关厄米矩阵的特征分解密切相关，即 AA^*，A^* A，以及 H(A) \equiv [{0 \atop A^*} \; {A \atop 0}]， 这些在第§2.4.7节中描述。 大多数SVD迭代算法相当于应用第4章中的算法到这些厄米矩阵之一，因此我们在这里回顾并扩展了这些内容。 选择 AA^*，A^* A，或 H(A) 取决于计算哪些奇异值和向量。 一些算法的成本，如移位-反转（见下文），对于 AA^*，A^* A，和 H(A) 可能会有显著差异。

1. 考虑 A^* A，这是一个 n 行 n 列的厄米矩阵。 那么 A^*A = V (\Sigma^*\Sigma) V^* 的特征分解， 其中 A = U \Sigma V^* 是 A 的SVD。 注意 \Sigma^*\Sigma = {\rm diag}(\sigma_1^2 , \ldots , \sigma_n^2)。 换句话说，A^* A 的特征向量是 A 的右奇异向量， A^* A 的特征值是 A 的奇异值的平方。

   因此，如果我们找到 AA^* 的特征值 \lambda_i 和特征向量 v_i， 那么我们可以通过取 \sigma_i = \lambda_i^{1/2}，i=1,\ldots,n， 右奇异向量为 v_i，i=1,\ldots,n， 以及前 r 个左奇异向量为 u_i = Av_i / \sigma_i， 来恢复 A 的紧凑SVD。 左奇异向量 u_{r+1} 到 u_m 不是直接确定的，但可以是任何与 u_1 到 u_r 正交的 m-r 个正交向量。 当 \sigma_i \neq 0 非常小，即 0 < \sigma_i \ll \sigma_1， 那么 u_i 将不会被准确确定。

2. 考虑 AA^*，这是一个 m 行 m 列的厄米矩阵。 那么 AA^* = U (\Sigma \Sigma^*) U^* 的特征分解。 注意 \Sigma \Sigma^* = {\rm diag} ( \sigma_1^2,\ldots,\sigma_n^2 , 0,\ldots,0)， 其中 m-n 个零在 \sigma_n^2 之后。 换句话说， AA^* 的特征向量是 A 的左奇异向量， AA^* 的特征值是 A 的奇异值的平方， 再加上 m-n 个0。

   因此，如果我们找到 AA^* 的特征值 \lambda_i 和特征向量 u_i， 那么我们可以通过取 \sigma_i = \lambda_i^{1/2}，i=1,\ldots,n，左奇异向量为 u_i，i=1,\ldots,m，以及 前 r 个右奇异向量为 v_i = A^*u_i / \sigma_i， 来恢复 A 的紧凑SVD。 右奇异向量 v_{r+1} 到 v_n 不是直接确定的，但可以是任何与 v_1 到 v_r 正交的 n-r 个正交向量。 当 \sigma_i \neq 0 非常小，即 0 < \sigma_i \ll \sigma_1， 那么 v_i 将不会被准确确定。

3. 考虑 H(A) = [{0^{m \times m} \atop A^*} \; {A \atop 0^{n \times n}}]， 这是一个 (m+n) 行 (m+n) 列的厄米矩阵。 写 U = [U_n^{m \times n}, \tilde{U}_n^{m \times (m-n)}] 和 \Sigma = [{\Sigma_{n}^{n \times n} \atop 0^{(m-n) \times n}}]。 那么 H(A) = Q \Lambda Q^* 的特征分解，其中 \Lambda = {\rm diag}( \Sigma_n , -\Sigma_n , O^{(m-n) \times (m-n)}) 和
   Q=\begin{bmatrix} \frac{1}{\sqrt{2}} U_n & -\frac{1}{\sqrt{2}} U_n & \widetilde{U}_n \\ \frac{1}{\sqrt{2}} V & +\frac{1}{\sqrt{2}} V &O^{n \times (m-n)} \end{bmatrix}.\tag{6.2}
   换句话说，\pm \sigma_i 是一个特征值，其单位特征向量为 \frac{1}{\sqrt{2}} [{\pm u_i \atop v_i}]，i=1 到 n， 并且0是一个特征值，其特征向量为 [{u_i \atop 0^{n \times 1}}] 对于 i>n。因此，我们可以直接从 H(A) 的特征值和特征向量中提取 A 的奇异值、左奇异向量和右奇异向量。更准确地说，我们可以直接从 H(A) 的特征值和特征向量中提取紧凑SVD。但如果0是 A 的奇异值，那么 0 将是（至少）H(A) 的一个双特征值，因此 Q 不一定具有形式（6.2）。（例如，如果 A=0 使得 H(A)=0，那么 Q 可以是任意正交矩阵，不一定具有形式（6.2）。）在这种情况下，假设 [{\hat{U}^{m \times z} \atop \hat{V}^{n \times z}}] 的列形成 H(A) 的零特征值的特征空间的正交基； 那么右奇异向量可以是任何正交向量，其张成 {\rm span} \hat{V}， 左奇异向量可以是任何正交向量，其张成 {\rm span} \hat{U}。

我们注意到

H(A)^2 = \begin{bmatrix} AA^* & 0 \\ 0 & A^*A \end{bmatrix} =\begin{bmatrix} H_2 & 0 \\ 0 & H_1 \end{bmatrix}

因此，两次乘以 H(A) 相当于乘以 AA^* 和 A^* A。

矩阵 A 的 SVD（奇异值分解）与其特征分解 H(A) 之间的对应关系表明，第 4.1 节和第 4.8 节中关于厄米矩阵特征值和特征向量的摄动理论讨论，可以直接应用于 SVD，具体如下所述。

将 A 扰动为 A+E 时，奇异值的变化最多为 \Vert E\Vert _2：

\vert \sigma_i (A+E) - \sigma_i(A) \vert \leq \Vert E\Vert_2. \tag{6.3}

现在假设 (\hat{\sigma}, \hat{u}, \hat{v}) 是奇异三元组 (\sigma_i, u_i, v_i) 的一个近似，其中 \hat{u} 和 \hat{v} 是单位向量。与 \hat{u} 和 \hat{v} 对应的“最佳” \hat{\sigma} 是瑞利商 \hat{\sigma} = {\rm Re}(\hat{u}^* A \hat{v})，因此我们假设 \hat{\sigma} 取此值。假设 \hat{\sigma} 比其他任何 \sigma_j 更接近 \sigma_i，并设 \delta 为 \hat{\sigma} 与其他奇异值之间的 间隔： \delta = \min_{j \neq i} \vert \hat{\sigma} - \sigma_j \vert。

定义 残差向量 r 为

r = \frac{1}{\sqrt{2}} \begin{bmatrix} A\hat{v} - \hat{\sigma} \hat{u} \\A^*\hat{u} - \hat{\sigma} \hat{v} \end{bmatrix}.

如果 r=0，则 (\hat{\sigma}, \hat{u}, \hat{v}) 是一个精确的奇异三元组，当 \Vert r\Vert _2 较小时，我们的误差界限也会较小。

\hat{\sigma} 与 \sigma_i 之间的差异被限制在

\vert \hat{\sigma} - \sigma_i \vert \leq \min \left\{ \Vert r\Vert _2 ,\frac{\Vert r\Vert _2^2}{\delta} \right\}.

此外，近似奇异向量与真实奇异向量之间的角度 \angle (\hat{v}, v_i) 和 \angle (\hat{u}, u_i) 被限制在

\max \{ \sin \angle (\hat{v}, v_i) , \sin \angle (\hat{u}, u_i) \}\leq \frac{\sqrt{2} \Vert r\Vert _2}{\delta}.

换句话说，近似奇异值 \hat{\sigma} 与其他所有 \sigma_j 之间的间隔 \delta 越大，残差 r 越小，则对 \hat{\sigma}、\hat{u} 和 \hat{v} 的误差界限就越紧。

给定 A、\hat{u} 和 \hat{v}，计算 \Vert r\Vert _2 很容易，但 \delta 需要更多关于奇异值的信息才能近似。通常使用接近 \hat{\sigma} 的计算奇异值来近似 \delta： \delta \approx \min \{ \hat{\sigma} - \hat{\sigma}_- ,\hat{\sigma}_+ - \hat{\sigma} \}， 其中 \hat{\sigma}_- 是比 \hat{\sigma} 小的下一个计算奇异值，\hat{\sigma}_+ 是比 \hat{\sigma} 大的下一个计算奇异值。