仓库源文站点原文


title: "用 SVD 进行图像压缩" categories: Mathematics updated: 2020-09-15 comments: true

mathjax: true

简单复习.

<!-- more -->

考虑 $m\times n$ 的实矩阵 $A$, 秩为 $r$, 记 SVD (singular value decomposition) 的一般形式为

$$A = U\Sigma V',$$

其中 $U=(u_1,\dots,u_m)$, $V=(v_1,\dots,v_n)$ 为正交阵,

$$ \Sigma = \begin{pmatrix} S & O\ O & O \end{pmatrix}, $$

其中 $S = \text{diag}\{\sigma_1,\dots,\sigma_r\}$, $\sigma_1\ge\cdots\sigma_r> 0$ 是 $A$ 的非零奇异值.

Proof. 由于 $A'A$ 是对称半正定矩阵, 故存在正交对角化

$$ A'A = V\Lambda V', $$

其中 $V$ 是正交阵, $\Lambda = \text{diag}\{\lambda_1,\dots,\lambda_n\}$, 且特征值非负, 不妨设 $\lambda_1\ge\cdots\ge\lambda_n$.

另外 $r = \text{rank}(A) = \text{rank}(A'A)$. 事实上, $Ax = 0$ 的解都是 $A'Ax = 0$ 的解; 而若 $A'Ay = 0$, 则 $y'A'Ay = 0$ 意味着 $Ay = 0$. 因此只有 $r$ 个非零特征值, 记 奇异值 $\sigma_j = \sqrt{\lambda_j}$.

下面记

$$ u_j = Av_j / \sigma_j, \quad j=1,\dots, r. $$

显然 $u_1, \dots, u_r$ 是一组单位正交基, 将它扩张为 $m$ 维的单位正交基, 最后整理即得 SVD. $\square$

Note:

把 $A$ 视为 中心化后 的样本矩阵, 每一行为一个样本 ($m$ 个样本), 每一列代表一个特征 ($n$ 个特征). 则样本协方差矩阵为 $A'A/m$, 而主成分 (principal component) $Av_j$ 的样本方差为 $\sigma_j/m$. 奇异值 $\sigma_j$ 越大意味着对应的样本方差越大, 我们把方差大视为提供了更多信息.

$A$ 可写为

$$ A = \sum_{k=1}^r \sigma_k u_kv_k', $$

把带有较少信息的小的奇异值扔掉便达到了压缩 (减少需要存储的东西) 的目的, 比如图像压缩.

PCA (principal component analysis) 降维也是同样的. 不过 PCA 还有若干种不同的 formulation.

从几何意义直观的展示就是, 奇异值大的那个轴数据更散布, 从而方差更大.

src: https://en.wikipedia.org/wiki/Singular_value_decomposition

Lenna 照片保留前 k 个奇异值的压缩结果

References

Images: