【线性代数】SVD 分解及简单应用

· · 个人记录

本文仅讨论实矩阵。

SVD

Definition

对于任意矩阵 A \in \mathbb{R}^{m \times n}，存在正交矩阵 P, Q 及对角矩阵 \Sigma，满足

A = P\Sigma Q^T

其中 P \in \mathbb{R}^{m \times m}, \Sigma \in \mathbb{R}^{m \times n}, Q \in \mathbb{R}^{n \times n}。

通常，\Sigma 主对角线上元素均为正，且以降序排列，此时 \Sigma 由 A 唯一确定，且这些元素被称作\boldsymbol{A} 的奇异值。

令 P = \begin{bmatrix} p_1 &p_2 &\cdots &p_m \end{bmatrix}，Q = \begin{bmatrix} q_1 &q_2 &\cdots &q_n \end{bmatrix}，则 p_i 被称作 \Sigma_{ii} 的左奇异向量，q_i 被称作 \Sigma_{ii} 的右奇异向量，且

A = \sum_i \Sigma_{ii}p_iq_i^T

以上整个过程，被称作奇异值分解，即 SVD(Singular Value Decomposition)。

Relation to Spectral Theoem

Spectral Theorem 指出，任意实对称矩阵均可对角化。换言之，当 \boldsymbol{A = A^T} 时，存在正交矩阵 Q 及对角矩阵 \Lambda，满足

A = Q\Lambda Q^T

可以看出，由于实对称矩阵有更好的性质，其在 SVD 的基础上，能够进一步满足 P = Q。

Proof

下面，我们将尝试构造 SVD。根据 Spectral Theorem

A^TA = Q\Sigma^2 Q^T

由于 A^TA 半正定，容易得到实矩阵 Q, \Sigma。

根据 A = P\Sigma Q^T 有

AQ = P\Sigma

即

\begin{bmatrix} Aq_1 &Aq_2 &\cdots &Aq_n \end{bmatrix} = \begin{bmatrix} p_1\Sigma_{11} &p_2\Sigma_{22} &\cdots &p_m\Sigma_{mm} \end{bmatrix}

超出范围的 \Sigma_{ii} 记作 0。

显然，若 \Sigma_{ii} \neq 0，有 p_i = \frac {Aq_i} {\Sigma_{ii}}；显然，这些 p_i 标准正交。否则，A 与 p_i 无关，直接将 p_1, p_2, \cdots, p_m 扩充为 \mathbb{R}^m 的标准正交基底即可。

值得一提的是，若令 r 为 A 的秩，可仅保留 P, Q 的前 r 列和 \Sigma 的前 r 行、前 r 列，此时 \Sigma 主对角线上元素均为正数。相比 Normal SVD，这种分解方法更加 compact，因此得名 Compact SVD。

Applications

Semiaxes of an ellipse or ellipsoid

令 X = \{x \ | \ ||x||_2 = 1\}，则不难证明：AX 形如高维椭圆，且 A 的所有奇异值均对应该椭圆的半长轴长度。

Pseudoinverse Computation

对于任意矩阵 A = U \Sigma V^T，其伪逆为

M^{+} = V\Sigma^{+}U^T

其中 \Sigma^{+} 为 \Sigma 的伪逆：将 \Sigma 转置后，将主对角线上各非零元素改为其倒数，所有零元素不变。

Matrix Norms

定义矩阵 A 的 p-范数为

||A||_p = \sup_{x \neq 0}\left\{\frac {||Ax||_p} {||x||_p}\right\}

不难证明，||A||_2 即为 A 的最大奇异值。

Low-Rank Matrix Approximation

考虑如下问题：找到秩 =r_0(r_0 \le r) 的矩阵 A_0，并最小化 A - A_0 的 F 范数。

可以证明，若令 \Sigma_0 为将 \Sigma 的第 r_0 行、r_0 列往后的所有元素均改为 0 的结果，则 U\Sigma_0 V^T 为最优低秩近似。

Polar Decomposition

若 A 为方阵，令 P = (UV^T)，Q = (V\Lambda V^T)，显然 P 为正交矩阵，Q 为半正定对称矩阵，且 U = PQ。

极分解：将任意方阵拆分为正交矩阵与半正定对称矩阵的乘积。