奇异值分解（SVD）｜集智百科

导语

在线性代数中，奇异值分解（Singular value decomposition）是一种通过旋转、缩放和再次旋转来对实矩阵（real matrix 元素都是实数的矩阵）或复矩阵（complex matrix 元素有复数的矩阵）进行因式分解的方法，如下图。它把具有标准正交基（orthonormal eigenbasis）的 方阵 特征分解 （eigen decomposition 矩阵分解为 特征向量 和 特征值 ）推广到了任意 m × n 矩阵，并与 极分解 （polar decomposition）密切相关。

具体而言，我们可以将一个 m × n 复矩阵 M 分解为 M = U Σ V ^∗ 。在这里， U 是 m × m 复酉矩阵（complex unitary matrix 共轭转置为其逆的复数矩阵）， Σ 是 m × n 矩形对角矩阵（rectangular diagonal matrix），其对角线元素为非负实数， V 是 n × n 复酉矩阵，而 V ^∗ 是 V 的共轭转置（conjugate transpose）。这种分解适用于任何复矩阵。若 M 为实矩阵，则 U 和 V 必为实正交矩阵（real orthogonal matrices）；此时，我们通常将SVD表示为 M = U Σ V ^T 。

Σ 的对角元素 σ _i = Σ _{i i} 由 M 唯一确定，称为 M 的奇异值。非零奇异值的数量等于 M 的 秩 （rank）。我们把 U 的列和 V 的列分别叫做 M 的左奇异向量和右奇异向量。它们分别构成两组 标准正交基 （orthonormal bases） u ₁ , … , u _m 和 v ₁ , … , v _n 。如果我们将值为零的奇异值 σ _i 排在最后，奇异值分解就可以写成：

这里 r ≤ min { m , n } 是 M 的秩。

虽然SVD不是唯一的，但我们总是可以选择让奇异值 Σ i i 按降序排列。这样一来， Σ （而非 U 和 V ）就由 M 唯一确定了。

有时，我们也把SVD称为紧凑SVD（compact SVD）。紧凑型SVD是与之类似的一个分解，形如 M = U _r Σ _r V _r ^∗ ，其中 Σ 是 r × r 的方形对角矩阵， r ≤ min { m , n } ， r 就是 M 的秩，只包含非零奇异值。在这种变体中， U 是 m × r 半酉矩阵（semi-unitary matrix 非方阵的酉矩阵）， V 是 n × r 半酉矩阵，满足 U ∗ U = V ∗ V = I _r （单位矩阵）。

SVD在数学上有多种应用，包括计算 伪逆 （pseudoinverse）、矩阵近似（matrix approximation）以及确定矩阵的 秩 （rank 线性无关向量的最大个数）、 值域 （range）和 零空间 （null space）。此外，SVD在科学、工程和统计学的各个领域都很有用，比如 信号处理 （signal processing）、 数据最小二乘拟合 （least squares fitting of data）和过程控制等。

近年来，张江老师带领研究组开始聚焦基于新兴 AI 技术进行数据驱动的自动建模研究，并立志破解复杂系统的涌现之谜。我们希望创建一个叫做 “复杂AI次方”的开放实验室 ，实现思想共享、资源共享、跨学科交叉，共同为复杂系统自动建模而奋进。欢迎对复杂系统自动建模领域有热情，且认可这个领域发展前景的朋友一起来合作，促进这一领域的快速发展。

关键词：奇异值分解，谱分解

刘宇康 | 作者

张江、王志鹏 | 审校

目录

1. 直观解释

1.1 旋转、坐标缩放和反射

1.2 奇异值作为椭圆或椭球体的半轴

1.3 U 和V的列构成标准正交基

1.4 与四个基本子空间的关系

1.5 几何意义

2. 案例

3. 奇异值分解（SVD）和谱分解

3.1 奇异值、奇异向量及其与SVD的关系

3.2 与特征值分解的关系

4. 奇异值分解的应用

4.1 伪逆

4.2 求解齐次线性方程

4.3 总体最小二乘最小化

4.4 值域、零空间和秩

4.5 低秩矩阵近似

4.6 可分离模型

4.7 最近正交矩阵

4.8 Kabsch算法

4.9 信号处理

4.10 其他例子

5. 存在性证明

5.1 基于谱定理

5.2 基于变分表征（variational characterization）

6. 计算奇异值分解（SVD）

6.1 单边雅可比算法（One-sided Jacobi algorithm）

6.2 双边雅可比算法（Two-sided Jacobi algorithm）

6.3 数值方法

6.4 2 × 2 SVD的解析结果

7. 简化奇异值分解

7.1 薄SVD (Thin SVD)

7.2 紧凑SVD (Compact SVD)

7.3 截断SVD (Truncated SVD)

8. 范数

8.1 Ky Fan范数

8.2 希尔伯特-施密特范数

9. 变体和推广

9.1 尺度不变奇异值分解

9.2 希尔伯特空间上的有界算子

9.3 奇异值和紧算子

10. 历史

1. 直观解释

1.1 旋转、坐标缩放和反射

特殊情况下，当 M 是 m × m 的实方阵时，我们也可以将矩阵 U 和 V ^∗ 选为实 m × m 矩阵。此时，“酉矩阵”和“正交矩阵”实际上是一回事。我们可以将这两个酉矩阵和对角矩阵 （这里统称为 A ） 解读为空间 的线性变换 （linear transformation） x ↦ Ax 。其中，矩阵 U 和 V ^∗ 代表空间的旋转 （rotations） 或反射 （reflection） ，而 Σ 则表示对每个坐标 x _i 按因子 σ _i 进行的缩放变换 （scaling） 。这样，奇异值分解就把 的任何线性变换分解成了三个几何变换的组合：先旋转或反射（ V ^∗ ），然后逐坐标缩放（ Σ ），最后再旋转或反射（ U ）。

特别地，如果 M 的行列式为正， U 和 V ^∗ 需要同时带反射或同时都不带反射。若行列式为负，则只有一个会带反射。若行列式为零，我们可以随意选择每个矩阵的类型。

当 M 是实矩阵但非方阵，即 m × n 且 m ≠ n 时 （如下图） ，我们可以将其视为从 到 的线性变换。这时，我们可以选择 U 和 V ^∗ 分别为 和 的旋转/反射；而 Σ 除了缩放前 min { m , n } 个坐标外，还会用零扩展向量或删除尾部坐标，从而将 转换 为 。

1.2 奇异值作为椭圆或椭球体的半轴

如下图所示，我们可以将奇异值理解为二维椭圆半轴的长度。这一概念可以推广到 n 维欧几里得空间 （Euclidean space） ：任何 n × n 方阵的奇异值都可以看作 n 维椭球体半轴的长度。同理，任何 m × n 矩阵的奇异值可以视为 m 维空间中 n 维椭球体半轴的长度，比如三维空间中 （倾斜的） 二维平面上的椭圆。奇异值编码了半轴的长度，而奇异向量则编码了方向。详见下文：

1.3 U 和 V 的列构成标准正交基

由于 U 和 V ^∗ 都是酉矩阵，它们的列分别形成一组标准正交向量 （orthonormal vectors 模为1且彼此正交的向量） ，我们可以将其视为基向量 （basis vectors 张成向量空间的一组线性无关向量） 。矩阵 M 把基向量 V _i 映射到拉伸后的单位向量 σ _i U _i 上。根据酉矩阵的定义，它们的共轭转置 U ^∗ 和 V 也具有相同性质，只是失去了奇异值作为拉伸的几何解释。简言之， U 、 U ^∗ 、 V 和 V ^∗ 的列都构成标准正交基 （orthonormal bases 模为1且正交的基向量集合） 。

当 M 是半正定厄米矩阵 （positive-semidefinite Hermitian matrix） 时， U 和 V 都等同于用于对角化 M 的酉矩阵。然而，如果 M 不是半正定厄米矩阵但仍可对角化的时候，那么其特征分解 （矩阵分解为特征值与特征向量） 和奇异值分解就会有所不同。

1.4 与四个基本子空间的关系：

• U 的前 r 列构成了 M 的列空间 （矩阵列向量张成的空间） 的基。
• U 的后 m − r 列则构成 M ^∗ 的零空间 （矩阵映射中被映射到零的所有向量集合） 的基。
• V 的前 r 列构成 M ^∗ 列空间的基 （在实数情况下即为 M 的行空间（矩阵行向量张成的空间）的基） 。

• V 的后 n − r 列构成 M 的零空间的基。

1.5 几何意义：

由于 U 和 V 是酉矩阵， U 的列 U ₁ , … , U _m 构成 K ^m 的标准正交基， V 的列 V ₁ , … , V _n 构成 K ⁿ 的标准正交基 （基于这些空间的标量积（scalar products 两个向量间的内积）） 。

我们可以定义一个线性变换为：

则该映射在这些标准正交基下有一个简洁的描述：

其中 σ _i 是 Σ 的第 i 个对角元素，当 i > min ( m , n ) 时， T ( V _i ) = 0 。

所谓的SVD定理的几何含义可以概括为：对于每个线性映射 T : K ⁿ → K ^m ，我们能找到 K ⁿ 和 K ^m 的标准正交基，使 T 将 K ⁿ 的第 i 个基向量映射到 K ^m 的第 i 个基向量的非负倍数，并将剩余基向量映射到零。在这些基下，映射 T 表现为一个具有非负实数对角元素的对角矩阵。

为了更直观地理解奇异值和SVD分解 （至少在实向量空间中） ，我们可以考虑 R ⁿ 中半径为1的球面 S 。线性映射 T 将这个球面映射到 R ^m 中的一个椭球体。非零奇异值就是这个椭球体半轴 （semi-axes） 的长度。特别地，当 n = m 且所有奇异值都不同且非零时，线性映射 T 的SVD可以分解为三个连续步骤：

1. 考虑椭球体 T ( S ) 及其轴，然后找出 R ⁿ 中被 T 映射到这些轴上的方向。这些方向恰好相互正交。首先应用等距变换 V ^∗ ，将这些方向映射到 R ⁿ 的坐标轴。

2. 应用沿坐标轴对角化的自同态 （endomorphism 映射自身到自身的线性变换） D ，在每个方向上进行拉伸或收缩，使用 T ( S ) 的半轴长度作为拉伸系数。组合 D ∘ V ^∗ 将单位球面映射到与 T ( S ) 等距的椭球体。

3. 最后，对这个椭球体应用等距变换 U 以得到 T ( S ) 。

可以验证，组合 U ∘ D ∘ V ^∗ 与 T 一致。

2. 案例

让我们来看一个 4 × 5 矩阵的例子：

我们可以通过 U Σ V ^∗ 对该矩阵进行奇异值分解：

注意，缩放矩阵 Σ 在对角线以外的元素都为零 （用灰色斜体表示） ，且有一个对角线元素为零（用红色粗体表示）。由于 U 和 V ^∗ 都是酉矩阵，将它们分别与其共轭转置相乘会得到单位矩阵 （identity matrices 对角线为1，其余为0的矩阵） 。在这个例子中， U 和 V ^∗ 都是实值矩阵，因此它们都是正交矩阵 （列向量互相正交且单位长度） 。我们可以验证：

值得注意的是，这个奇异值分解并非唯一。我们还可以选择另一个 V ，使得：

这同样是一个有效的奇异值分解。

3. 奇异值分解（SVD）和谱分解

3.1 奇异值、奇异向量及其与SVD的关系

非负实数 σ 称为 M 的奇异值，当且仅当存在 K ^m 中的单位长度向量 u 和 K ⁿ 中的单位长度向量 v ，满足：

我们称向量 u 和 v 分别为 σ 的左奇异向量和右奇异向量。

在奇异值分解 M = U Σ V ^∗ 中， Σ 的对角线元素即为 M 的奇异值。 U 和 V 的前 p = min ( m , n ) 列分别对应各奇异值的左奇异向量和右奇异向量。因此，上述定理表明：

• 一个 m × n 矩阵 M 最多有 p 个不同的奇异值。
• 我们总能在 ⁠ K ^m ⁠ 空间中找到一组酉基 （即一组基向量，它们构成的矩阵是酉矩阵） U ⁠ ⁠，其中部分基向量，张成了矩阵 ⁠ M ⁠ 中每个奇异值对应的左奇异向量。

• 同样地，在 ⁠ K ⁿ ⁠ 空间中也存在一组酉基 V ⁠ ⁠，其中部分基向量，张成了矩阵 M ⁠ 中每个奇异值对应的右奇异向量。

当我们能找到两个线性独立的左 （或右） 奇异向量时，我们称该奇异值为简并 （degenerate） 的。如果 u ₁ 和 u ₂ 是对应奇异值 σ 的两个左奇异向量，那么这两个向量的任何归一化线性组合也是对应奇异值 σ 的左奇异向量。右奇异向量也有类似性质。独立的左奇异向量和右奇异向量数量相同，它们分别出现在 U 和 V 的对应列中，这些列对应着 Σ 中值为 σ 的对角元素。

特别地，奇异值为0的左奇异向量和右奇异向量分别包括 M 的余核 （cokernel 未被矩阵覆盖的输出空间） 和核 （kernel 矩阵映射为零的输入空间） 中的所有单位向量。根据秩-零化度定理 （rank–nullity theorem） ，如果 m ≠ n ，它们的维数不可能相同。即使所有奇异值都非零，当 m > n 时，余核是非平凡 （nontrivial） 的，此时 U 用余核中的 m − n 个正交向量填充。相反，当 m < n 时， V 由核中的 n − m 个正交向量填充。然而，如果存在0的奇异值， U 或 V 的额外列已经作为左奇异向量或右奇异向量出现。

非简并奇异值总有唯一的左奇异向量和右奇异向量，只能乘以单位相位因子 （unit-phase factor） e ^{i φ} （实数情况下，只能乘以正负号） 。因此，如果方阵 M 的所有奇异值都是非简并且非零的，那么它的奇异值分解是唯一的，只能对 U 的一列乘以单位相位因子，同时对 V 的相应列乘以相同的单位相位因子。总的来说，SVD 在对 U 和 V 的列向量 （这些列向量张成每个奇异值的子空间） 统一应用任意酉变换，以及对 U 和 V 的向量 （这些向量分别张成 M 的核和余核） 应用任意酉变换的情况下是唯一的。

3.2 与特征值分解的关系

奇异值分解具有广泛适用性，可用于任何 m × n 矩阵，而特征值分解 （eigenvalue decomposition） 仅限于可对角化的方阵。尽管如此，这两种分解方法仍有密切联系。

设 M 的SVD为 M = U Σ V ^∗ ，则以下两个等式成立：

等式右侧描述了左侧的特征值分解。由此可得：

• V 的列 （即右奇异向量） 是 M ^∗ M 的特征向量 （eigenvectors 矩阵变换不改变方向的向量） 。
• U 的列 （即左奇异向量） 是 M M ^∗ 的特征向量。

• Σ 的非零元素 （即非零奇异值） 是 M ^∗ M 或 M M ^∗ 非零特征值 （矩阵变换后缩放的因子） 的平方根。

当 M 为正规矩阵 （normal matrix 与其共轭转置可交换的矩阵） 时，根据谱定理 （spectral theorem） ，我们可以用特征向量的基对其进行酉对角化，得到分解 M = U D U ^∗ 。其中 U 是酉矩阵， D 是对角线上有复数元素 σ _i 的对角矩阵。若 M 为半正定 （positive semi-definite 所有特征值非负的矩阵） 矩阵，则 σ _i 为非负实数，此时分解 M = U D U ^∗ 也是一个奇异值分解。否则，我们可以将每个 σ _i 的相位 e ^{i φ} 移到相应的 V _i 或 U _i 中，从而重新表示为SVD形式。SVD与非正规矩阵的联系主要体现在极分解定理： M = S R ，其中 S = U Σ U ^∗ 是半正定且正规的， R = U V ^∗ 是酉的。

因此，除半正定矩阵外， M 的特征值分解和SVD虽有关联，但并不相同：特征值分解形如 M = U D U ^{- 1} ，其中 U 不一定是酉的， D 不一定是半正定的；而SVD形如 M = U Σ V ^∗ ，其中 Σ 是对角的且半正定的， U 和 V 是酉矩阵，它们除了通过矩阵 M 外不一定有关联。值得注意的是，只有非亏损 （non-defective 矩阵行列式不为零） 方阵才有特征值分解，而任何 m × n 矩阵都存在SVD。

4. 奇异值分解的应用

4.1 伪逆

我们可以利用奇异值分解计算矩阵的伪逆 （矩阵的广义逆，用于求解方程） 。设矩阵 M 的奇异值分解为 M = U Σ V ^∗ ，则其伪逆为：

这里， Σ ⁺ 是 Σ 的伪逆，我们通过将每个非零对角元素取倒数并转置来得到它。伪逆在解决线性最小二乘问题 （linear least squares problems） 时常常派上用场。

4.2 求解齐次线性方程

我们可以将一组齐次线性方程 （homogeneous linear equations） 表示为 A x = 0 ，其中 A 是矩阵， x 是向量。通常，我们已知 A ，需要找出满足方程的非零 x 。这样的 x 属于 A 的零空间，也称为 A 的 （右） 零向量。我们可以将向量 x 描述为与 A 的零奇异值对应的右奇异向量。这意味着，如果 A 是方阵且没有零奇异值，则方程没有非零解。若有多个零奇异值，那么对应的右奇异向量的任意线性组合都是有效解。类似地，满足 x ^∗ A = 0 的非零 x （其中 x ^∗ 是 x 的共轭转置） 被称为 A 的左零向量。

4.3 总体最小二乘最小化

总体最小二乘问题 （total least squares） 旨在找到一个向量 x ，使得在 ‖ x ‖ = 1 的约束下（用双竖线 "||" 包围向量表示对该向量求范数）， A x 的2-范数（2-norm）最小。结果表明，解就是 A 最小奇异值对应的右奇异向量。

4.4 值域、零空间和秩

SVD还能为矩阵 M 的值域和零空间提供明确表示。 M 零奇异值对应的右奇异向量张成 （span） 其零空间，非零奇异值对应的左奇异向量张成其值域。例如，在前面的例子中，零空间由 V ^∗ 的最后 ( n − r ) 列张成，值域由 U 的前 r 列张成，其中 r 是矩阵 M 的秩。

因此， M 的秩等于非零奇异值的个数，也就是 Σ 中非零对角元素的个数。在数值线性代数中，我们可以用奇异值确定矩阵的有效秩，因为舍入误差 （rounding error） 可能导致秩亏矩阵 （rank deficiency matrix） 出现小但非零的奇异值。我们通常认为超过显著间隙的奇异值在数值上等同于零。

4.5 低秩矩阵近似

一些实际应用需要用另一个特定秩 r 的矩阵 （称为截断矩阵truncated） 来近似矩阵 M 。如果我们要在 rank ( ) = r 的约束下最小化 M 和 之间差的Frobenius范数，那么解就由 M 的SVD给出：

这里， 与 Σ 相同，但只保留 r 个最大的奇异值 （其他奇异值置零） 。这就是Eckart–Young定理，由这两位作者于1936年证明 （尽管后来发现早期学者已经了解这一结果） [1]。

4.6 可分离模型

我们可以将SVD视为把矩阵分解成加权、有序的可分离矩阵之和。所谓可分离，指的是矩阵 A 可以表示为两个向量的外积 （outer product 两个向量的反对称积，生成矩阵） A = u ⊗ v ，用坐标表示即 A _{i j} = u _i v _j 。具体来说，矩阵 M 的分解如下：

这里， U _i 和 V _i 分别是SVD矩阵的第i列， σ _i 是有序奇异值，每个 A _i 都是可分离的。在图像处理中，我们常用SVD将滤波器分解为水平和垂直的可分离滤波器。值得注意的是，非零 σ _i 的数量恰好等于矩阵的秩。

可分离模型在生物系统中很常见，SVD分解在分析这些系统时非常有用。例如，我们可以用空间域的Gabor滤波器乘以时间域的调制函数来很好地描述一些视觉区V1简单细胞的感受野[2]。因此，如果我们通过反向相关 （reverse correlation） 等方法评估得到线性滤波器，就可以将两个空间维度重排为一个维度，得到一个二维滤波器 （空间，时间） ，然后进行SVD分解。在SVD分解中， U 的第一列就是Gabor，而 V 的第一列代表时间调制 （或反之） 。

我们可以定义一个可分离性指数：

该指数表明在矩阵 M 的幂次中，第一个可分离矩阵所占的比例。[3]。

4.7 最近正交矩阵

我们可以利用方阵 A 的SVD来找出最接近 A 的正交矩阵 （列向量互相正交且单位长度） O 。这里，我们用 O − A 的Frobenius范数来衡量接近程度。解是 U V ^∗ 的乘积[4]。这个结果在直觉上是合理的，因为正交矩阵会有分解 U I V ^∗ ，其中 I 是单位矩阵。所以如果 A = U Σ V ^∗ ，那么乘积 A = U V ^∗ 相当于用1替换所有奇异值。等价地，解就是极分解 M = R P = P ′ R 中的酉矩阵 R = U V ^∗ ，无论拉伸和旋转的顺序如何。

在形状分析中，有一个类似的问题叫做正交普鲁克问题 （orthogonal Procrustes problem） ，它涉及找到一个最接近将 A 映射到 B 的正交矩阵 O 。具体来说：

其中 ‖ ⋅ ‖ _F 表示Frobenius范数。

这个问题等同于为给定矩阵 M = A ^T B 找到最近的正交矩阵。

4.8 Kabsch算法

Kabsch算法 （在其他领域称为Wahba问题） 运用SVD来计算最优旋转 （关于最小二乘最小化） ，以将一组点与相应的另一组点对齐。这种算法在多个领域都有应用，比如用于比较分子结构。

4.9 信号处理

研究者已成功将SVD和伪逆应用于信号处理 [5]、图像处理 [6]和大数据 （如基因组信号处理） [7][8][9][10] 。

4.10 其他例子

奇异值分解 (SVD) 在线性反问题 （inverse problems） 研究中广泛应用，分析Tikhonov正则化等方法时颇有助益。统计学界普遍使用它，与主成分分析 （principal component analysis） 和对应分析 （correspondence analysis） 密切相关，信号处理和模式识别领域也常见其身影。此外，它还用于仅输出模态分析 （modal analysis） ，可从奇异向量确定非缩放模态形状 （mode shapes） 。自然语言文本处理中的潜在语义索引 （latent semantic indexing） 也离不开它。

在涉及线性或线性化系统的一般数值计算中，常用一个普遍常数来刻画问题的规律性或奇异性，即系统的"条件数" κ := σ _max / σ _min 。这个数值通常决定了给定计算方案在这些系统上的误差率或收敛速度[11][12]。

量子信息 （quantum information） 领域中，SVD以Schmidt分解的形式发挥着关键作用。通过它，我们可以自然地分解两个量子系统的状态，从而提供了它们纠缠的充要条件：只要 Σ 矩阵的秩大于1。

数值天气预报 （numerical weather prediction） 中，SVD对大型矩阵也有重要应用。利用Lanczos方法，可以估算在给定初始前向时间段内，对中心数值天气预报线性增长最快的几个扰动。这些扰动实际上是该时间间隔内全球天气线性化传播子对应最大奇异值的奇异向量。在这种情况下，输出奇异向量代表整个天气系统。随后，这些扰动通过完整的非线性模型运行，生成集合预报 （ensemble forecast） ，为当前中心预测周围的不确定性提供了处理方法。

降阶建模 （reduced-order modeling） 中也少不了SVD的身影。降阶建模旨在减少复杂系统中的自由度数量。研究人员将SVD与径向基函数 （radial basis functions） 结合，用于插值三维非稳态流问题的解[13]。值得一提的是，科学家们已经利用SVD改进了地面引力波干涉仪aLIGO的引力波形建模 （gravitational wave modeling ）[14]。SVD有助于提高波形生成的准确性和速度，支持引力波搜索和更新两种不同的波形模型。

推荐系统 （Recommender systems） 中，SVD用于预测用户对项目的评分[15]。为了在商品机器集群上高效计算SVD，研究人员开发了分布式算法[16]。

低秩SVD在从时空数据中检测热点方面表现出色，已应用于疾病爆发检测[17]。研究人员还将SVD和高阶SVD结合起来，用于疾病监测中从复杂数据流(具有空间和时间维度的多变量数据)进行实时事件检测[18]。

在天体动力学 （astrodynamics） 领域，科学家们运用SVD及其变体来确定转移轨道设计[19]和轨道站保持的合适机动方向[20]。

5. 存在性证明

矩阵 M 的特征值 λ 满足代数关系 M u = λ u 。当 M 是厄米矩阵 （Hermitian matrix 自共轭矩阵等于其共轭转置） 时，我们还可以用变分特征来描述它。假设 M 是一个 n × n 的实数对称矩阵 （矩阵等于其转置） ，我们定义函数：

极值定理告诉我们，当这个连续函数限制在单位球面 { ‖ x ‖ = 1 } 上时，必在某点 u 处达到最大值。根据拉格朗日乘数定理， u 必然满足：

这里 λ 是某个实数，而 ∇ 表示相对于 x 的del微分算子。利用 M 的对称性，我们得到：

因此， M u = λ u ，这说明 u 是 M 的单位长度特征向量。对 M 的每个单位长度特征向量 v ，其特征值就是 f ( v ) ，所以 λ 是 M 的最大特征值。在 u 的正交补上重复这个过程，我们就能得到次大特征值，依此类推。

复数厄米矩阵的情况，处理方法类似，只是此时 f ( x ) = x ^∗ M x 变成了 2n 个实变量的实值函数。

奇异值的描述方法与特征值相似，我们可以用代数或变分原理来刻画它们。不过，与特征值不同，这里的 M 不必是厄米矩阵或对称矩阵。

接下来，我们将从两个角度论证奇异值分解的存在性。

5.1 基于谱定理

设 M 为 m × n 复矩阵。由于 M ^∗ M 是半正定厄米矩阵，根据谱定理，我们可以找到一个 n × n 酉矩阵 V ，使得：

这里 D 是 ℓ × ℓ 维的对角正定矩阵， ℓ 表示 M ^∗ M 非零特征值的个数（可以证明 ℓ ≤ min ( n , m ) ）。我们将 V 定义为一个矩阵，其第 i 列是 M ^∗ M 对应特征值 的特征向量。当 j > ℓ 时， V 的第 j 列是 M ^∗ M 零特征值（即 ）对应的特征向量。我们可以将 V 写成 V = [ V ₁ V ₂ ] ，其中 V ₁ 和 V ₂ 的列分别包含 M ^∗ M 非零和零特征值对应的特征向量。用这种形式重写 V ，方程就变成：

这意味着：

进一步，第二个方程表明 M V ₂ = 0 。此外， V 的酉性质在 V ₁ 和 V ₂ 方面体现为：

这里单位矩阵的下标用来表示它们的不同维度。

现在我们定义：

那么，

因为 M V ₂ = 0 。这也可以看作 的直接结果。换个角度看，如果 是 M ^∗ M 对应非零特征值 的特征向量集，那么 就是一组正交向量，而 则是一组 （通常不完全的） 正交单位向量。这与上面使用的矩阵形式相符，其中 V ₁ 表示列为 的矩阵， V ₂ 表示列为 M ^∗ M 零特征值对应特征向量的矩阵， U ₁ 表示列为向量 的矩阵。

我们发现这几乎就是所需的结果，只是 U ₁ 和 V ₁ 通常不是酉矩阵，因为它们可能不是方阵。然而，我们知道 U ₁ 的行数不小于列数，因为 D 的维度不大于 m 和 n。此外，由于

U ₁ 中的列是正交单位的，可以扩展成一个正交基。这意味着我们可以选择 U ₂ ，使得 U = [ U ₁ U ₂ ] 成为酉矩阵。

对于 V ₁ ，我们已经有 V ₂ 使其成为酉矩阵。现在，我们定义

其中我们添加或删除额外的零行，使零行的数量等于 U ₂ 的列数，从而使 Σ 的整体维度等于 m × n 。那么

这就是我们要证明的结果：

值得注意的是，这个论证也可以从对角化 M M ^∗ 而不是 M ^∗ M 开始 （这直接显示 M M ^∗ 和 M ^∗ M 具有相同的非零特征值） 。

5.2 基于变分表征（variational characterization）

奇异值可描述为 u ^T M v 的最大值，这是 U 和 V 在特定子空间上的函数。当达到这些最大值时， U 和 V 的值就是奇异向量。

设 M 为 m × n 实矩阵。定义 S ^{k − 1} 为 中的单位 ( k − 1 ) -球面，并令 σ ( u , v ) = u ^T M v ，其中 u ∈ S ^{m − 1} ， v ∈ S ^{n − 1} 。

考虑函数 σ 在 S ^{m − 1} × S ^{n − 1} 上的限制。由于 S ^{m − 1} 和 S ^{n − 1} 都是紧集 （compact sets） ，它们的乘积也是紧集。又因 σ 连续，它必在 S ^{m − 1} 中的某向量 u 和 S n − 1 中的某向量 v 处达到最大值。我们将这个最大值记为 σ ₁ ，相应的向量记为 u ₁ 和 v ₁ 。由于 σ ₁ 是 σ ( u , v ) 的最大值，它必为非负。若为负，改变 u ₁ 或 v ₁ 的符号就能使其变为正值，从而更大。

现在我们提出以下陈述: u ₁ 和 v ₁ 是 M 的左右奇异向量，对应的奇异值为 σ ₁ 。

证明如下：类似于特征值的情况，根据假设，这两个向量满足拉格朗日乘数方程:

经过一些代数运算，我们得到:

从左侧将第一个方程乘以 ，第二个方程乘以 ，并考虑到 ‖ u ‖ = ‖ v ‖ = 1 ，我们得到：

σ ₁ = 2 λ ₁ = 2 λ ₂ .

将此代入上面的一对方程中，得:

这就证明了该陈述。

要找到更多的奇异向量和奇异值，我们可以在正交于 u ₁ 和 v ₁ 的归一化 u 和 v 上最大化 σ ( u , v ) 。

从实数到复数的过渡与特征值的情况类似。

6. 计算奇异值分解（SVD）

6.1 单边雅可比算法（One-sided Jacobi algorithm）

单边雅可比算法是一种迭代算法[21]，它通过反复转换使矩阵列正交化。其基本迭代步骤由雅可比旋转 （Jacobi rotation） 给出：

M ← M J ( p , q , θ ) ,

这里，我们选择雅可比旋转矩阵 J ( p , q , θ ) 的角度 θ ，使旋转后第 p 列和第 q 列正交。指标 ( p , q ) 按 ( p = 1 … m , q = p + 1 … m ) 循环扫描，其中 m 为列数。

算法收敛后，我们可以这样恢复奇异值分解 M = U S V ^T ：矩阵 V 是雅可比旋转矩阵的累积，将转换后矩阵 M 的列归一化得到矩阵 U ，而奇异值则由转换后矩阵 M 列的范数给出。

6.2 双边雅可比算法（Two-sided Jacobi algorithm）

双边雅可比SVD算法是雅可比特征值算法 （Jacobi eigenvalue algorithm） 的推广，它通过迭代将方阵转换为对角矩阵。对于非方阵，我们先进行QR分解，然后对 R 矩阵应用此算法。其基本迭代步骤如下：先用Givens旋转使一对非对角元素对称，再用雅可比变换 （Jacobi transformation） 使它们归零，

M ← J ^T G M J

这里， G 是Givens旋转矩阵，我们选择适当的角度使指定的非对角元素对在旋转后相等； J 是雅可比变换矩阵，用于将这些非对角元素置零。迭代过程与雅可比特征值算法相同：对所有非对角元素循环扫描。

算法收敛后，结果对角矩阵包含奇异值。矩阵 U 和 V 的累积如下： U ← U G ^T J ， V ← V J 。

6.3 数值方法

我们可以利用以下观察结果计算奇异值分解：

• M 的左奇异向量是 M M ^∗ 的一组正交归一化特征向量。
• M 的右奇异向量是 M ^∗ M 的一组正交归一化特征向量。

• M 的非零奇异值 （在 Σ 的对角线上） 等于 M ^∗ M 和 M M ^∗ 的非零特征值的平方根。

通常，我们通过两步计算矩阵 M 的SVD。第一步将矩阵简化为双对角矩阵 （bidiagonal matrix） ，假设 m ≥ n ，需要 O ( m n ² ) 次浮点运算 （flop） 。第二步计算双对角矩阵的SVD，且只能通过迭代方法完成。实际上，计算到机器精度就足够了。如果将这个精度视为常数，第二步需要 O ( n ) 次迭代，每次迭代花费 O ( n ) 次flop。因此，第一步耗时更长，总体成本为 O ( m n ² ) 次flop[22]。

如果只需计算奇异值，第一步可用Householder反射以 4 m n ² − 4 n ³ / 3 次flop完成。当 m 远大于 n 时，先用QR分解将矩阵 M 简化为三角矩阵，再用Householder反射进一步简化为双对角形式更有优势；总成本为 2 m n ² + 2 n ³ 次flop[22]。

第二步可用QR算法的变体完成，该变体由Golub & Kahan[23]首次描述。LAPACK子程序DBDSQR[24]实现了这种迭代方法，并针对奇异值非常小的情况进行了改进[25]。结合使用Householder反射的第一步和适当情况下的QR分解，构成了计算奇异值分解的DGESVD[24]例程。

GNU科学库 （GSL） 也实现了相同算法，并提供了一种替代方法，在第2步中使用单边雅可比正交化[26]。这种方法通过求解一系列 2 × 2 的SVD问题来计算双对角矩阵的SVD，类似于雅可比特征值算法求解一系列 2 × 2 的特征值问题[27]。第2步的另一种方法借鉴了分治特征值算法 （divide-and-conquer eigenvalue algorithms） 的思想[22]。

还有一种不显式使用特征值分解的替代方法[28]。通常，我们将矩阵 M 的奇异值问题转换为等价的对称特征值问题，如 M M ^∗ ， M ^∗ M ，或 。

使用特征值分解的方法基于QR算法，该算法已发展得稳定且快速。注意，奇异值是实数，右奇异向量和左奇异向量不需要形成相似变换。我们可以在QR分解和LQ分解之间迭代交替以找到实对角厄米矩阵。QR分解给出 M