奇异值分解与矩阵近似

【矩阵的最优近似】

F 范数意义下的奇异值分解

奇异值分解是一种矩阵近似的方法，这个近似是在 F 范数意义下对矩阵的最优近似，本质上是进行了数据压缩，紧奇异值分解是在 F 范数意义下的无损压缩，截断奇异值分解是由低秩矩阵实现对原始矩阵的有损压缩

设矩阵 $A\in C^{m\times n}$，$A$ 的奇异值分解为 $U\Sigma V^T$，则有：

$$||A||_F = (\sigma_1^2+\sigma_2^2+\cdots \sigma_n^2)^{\frac{1}{2}}$$

其中，$\Sigma = \text{diag}(\sigma_1,\sigma_2,\cdots,\sigma_n)$

最优近似

设矩阵 $A\in C^{m\times n}$，矩阵的秩 $\text{rank } A=r>0$，令 $\mathcal{M}$ 为 $C^{m\times n}$ 中所有秩不超过 $k$ 的矩阵集合，$0<k<r$，则存在一个秩为 $k$ 的矩阵 $X\in \mathcal{M}$，使得

$$||A-X||_F = \min_{S\in \mathcal{M}} ||A-S||_F$$

此时，称矩阵 $X$ 为矩阵 $A$ 在 F 范数意义下的最优近似

进一步，对于 $||A-X||_F$，有：

$$||A-X||_F = (\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_{n}^2)^{\frac{1}{2}}$$

特别地，若 $A’=U\Sigma’ V^T$，则：

$$||A-A'||_F = (\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_{n}^2)^{\frac{1}{2}} = \min_{S\in \mathcal{M}} ||A-S||_F$$

其中

$$\Sigma' = \begin{bmatrix} \Sigma_{k} & O \\ O & O \\ \end{bmatrix}$$

上述定理表明，在秩不超过 $k$ 的 $m\times n$ 矩阵的集合中，存在矩阵 $A$ 的 F 范数意义下的最优近似矩阵 $X$，$A’=U\Sigma’ V^T$ 是达到最优值的一个矩阵

【矩阵的外积展开式】

矩阵 $A$ 的奇异值分解 $U\Sigma V^T$ 也可以由外积形式表示

将 $A$ 的奇异值分解 $U\Sigma V^T$ 看作矩阵 $U\Sigma$ 与 $V^T$ 的乘积，将 $U\Sigma$ 按列向量分块，将 $V^T$ 按行向量分块，即得：

$$\begin{array}{cc} U\Sigma = \begin{bmatrix} \sigma_1 u_1 & \sigma_2 u_2 & \cdots & \sigma_n u_n \end{bmatrix} \\ V^T = \begin{bmatrix} v_1^T & v_2^T & \cdots & v_n^T \end{bmatrix}^T \\ \end{array}$$

则：

$$A = \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_nu_nv_n^T$$

上式被称为矩阵 $A$ 的外积展开式，其中 $u_kv_k^T$ 为 $m\times n$ 矩阵，是列向量 $u_k$ 和行向量 $v_k^T$ 的外积，其第 $i$ 行第 $j$ 列元素为 $u_k$ 的第 $i$ 个元素与 $v_k^T$ 的第 $j$ 的元素的乘积，即：

$$u_iv_j^T = \begin{bmatrix} u_{1i} \\ u_{2i} \\ \cdots \\ u_{mi} \end{bmatrix}\begin{bmatrix} v_{1j} & v_{2j} & \cdots & v_{ni} \end{bmatrix} = \begin{bmatrix} u_{1i}v_{1j} & u_{1i}v_{2j} & \cdots & u_{1i}v_{nj} \\ u_{2i}v_{1j} & u_{2i}v_{2j} & \cdots & u_{2i}v_{nj} \\ \vdots & \vdots & \ddots & \vdots \\ u_{mi}v_{1j} & u_{mi}v_{2j} & \cdots & u_{mi}v_{nj} \\ \end{bmatrix}$$

此外，矩阵 $A$ 的外积展开式也可写为下述将 $A$ 分解为矩阵的有序加权和的形式：

$$A=\sum_{k=1}^n A_k = \sum_{k=1}^n \sigma_k u_k v_k^T$$

其中，$A_k=\sigma_k u_k v_k^T$ 是 $m\times n$ 矩阵

设 $A_{k}$ 的秩为 $k$，且 $A_{k}$ 是秩为 $k$ 矩阵在 F 范数意义下 $A$ 的最优近似矩阵，即

$$A_{k} = \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + \cdots + \sigma_{k}u_{k}v_{k}^T$$

那么，矩阵 $A_k$ 就是 $A$ 的截断奇异值分解

通常来说，由于奇异值 $\sigma_i$ 递减很快，所以在 $k$ 取很小值时，$A_k$ 可以对 $A$ 有很好的近似