7-2-图像压缩与低秩逼近
一句话概括
由 ,只保留最大的前 项就得到一个秩 的矩阵
称为 的截断 SVD(truncated SVD)或低秩逼近(low-rank approximation)。Eckart–Young 定理保证:在所有秩不超过 的矩阵中, 在 2-范数与 Frobenius 范数下同时是最优逼近,而且误差恰好是下一个奇异值 。
本篇覆盖:低秩逼近的问题设定、Eckart–Young 定理的完整表述与证明、图像作为矩阵(灰度图/彩色图/存储量)、压缩比公式与真实数值表格、奇异值衰减曲线与能量占比、可运行的 numpy 代码、去噪原理、矩阵补全与潜在语义索引,以及三个最容易犯的误解。
一、定义与问题设定
1.1 低秩逼近问题
定义 7.2.1(低秩逼近问题,low-rank approximation problem) 给定 与正整数 ,求
其中 是某种矩阵范数。
也就是说:用一个"简单的"(秩不超过 )矩阵去代替 ,使得误差尽可能小。
"秩 "为什么等于"简单"?回忆秩的定义: 意味着 的列空间维数不超过 ,等价地 可以写成
即 只需要 个"基本模式"就能完全描述。这正是"压缩"的数学含义。
1.2 截断 SVD
定义 7.2.2(截断 SVD,truncated SVD) 设 是 7-1-SVD的构造与几何意义 中的奇异值分解,。对 定义
则
称为 的截断 SVD(保留前 个奇异值)。
截断 SVD 是"秩 矩阵"
(当 时)。因为它由 个秩一矩阵相加而成,且 全为正,所以秩恰好是 。
另外注意 、(缩减 SVD 的性质,见 7-1-SVD的构造与几何意义 定义 7.1.2),但 ——它一般不是单位矩阵,而是到 维子空间的投影矩阵。
1.3 残差矩阵的奇异值
后面反复用到一条简单但关键的事实。
引理 7.2.3 设 ,则残差
本身就是一个 SVD(只是缺少前 项),因此它的奇异值恰好是
证明。 与 分别是两组标准正交向量,可以补全为正交矩阵 。把它们按 的顺序配对,即得 的一个合法 SVD,故其(非零)奇异值就是 。
推论。 由 7-1-SVD的构造与几何意义 的定理 7.1.11、7.1.12:
这两条公式就是本篇的两个核心结论的"上界一半"——Eckart–Young 定理要证明的是,任何秩 的矩阵都不可能比 做得更好。
二、几何直观
2.1 奇异值是"重要性"的度量
回忆 7-1-SVD的构造与几何意义 的几何图像: 把单位球映成椭球, 是椭球的第 个半轴长。
可以读作: 的全部"内容"被分解成 个互相独立的模式,第 个模式的强度是 。
- 大:这个模式在 中占的分量重,是 的"主要成分";
- 小:这个模式只是 的一点"细节"或"抖动",去掉它 看起来几乎不变;
- :这个模式完全不存在。
于是"把小的奇异值丢掉"在几何上就是:只保留椭球最长的前 根半轴,把其余的压成 。 得到的椭球"扁"了一些,但形状的主体还在。
一句话理解 Eckart–Young
丢掉最小的那些奇异值,是"最省"的降秩方式。 任何其他降秩方法(比如随便把 的某几列改成 、或者用某种经验公式)造成的误差都不会比"丢掉最小的奇异值"更小。
2.2 为什么是"秩 "而不是"挑 列"
一个自然的疑问:想压缩,为什么不直接只保留 的 列(或 行)?
因为那样得到的矩阵仍然是秩 的(保留 列后秩最多 ,确实降秩了),但误差通常远大于截断 SVD。原因: 的列之间几乎总是不正交的、"信息重叠"的——保留 列并不意味着保留了 个独立的方向。而 SVD 给出的 项是严格正交、互不重叠的,所以每一项都带来"全新"的信息量,前 项之和自然就是最好的秩 逼近。
用一个具体的数字感受一下:本篇 5.4 节的实验中, 图像的 截断 SVD 已经保住了 99.468% 的能量;而"随便保留 50 列"远达不到这个效果,因为被丢掉的 206 列里含有大量与保留列相关的信息。
2.3 从"降秩"看"降维"
低秩逼近还有一种读法:,其中 。
- 把输入 压到 维(只保留前 个方向);
- 在这 维里伸缩;
- 再升回 。
所以 是一个"降维再升维"的复合:信息在中间过程中被压缩到 维。这正是所有降维方法(PCA、自编码器、潜在语义索引)的共同结构。
三、Eckart–Young 定理
3.1 定理的完整表述
定理 7.2.4(Eckart–Young 定理,Eckart–Young theorem) 设 的奇异值为 (),。则对任意满足 的矩阵 ,有
并且 时两个不等式同时取等号。因此
最优解都是 。
适用条件:
- 是任意实(或复)矩阵,不要求方阵、不要求对称、不要求满秩;
- 结论中的 取 ; 时 ,误差为 ;
- 两个范数下的最优解相同(都是 ),但最优误差值不同;
- 若 (即奇异值不重复),则最优的秩 矩阵是唯一的,就是 ;若 则最优解不唯一(可以在这个重奇异值对应的子空间里任意旋转)。
为什么这条定理重要
它把"找一个最好的秩 逼近"这个看似需要优化求解的问题,变成一个不需要优化的问题:直接做 SVD,取前 项,就结束了。
换句话说:截断 SVD 不只是"一种"逼近方法,而是"最好的"那一种。 这就是它在图像压缩、推荐系统、去噪里成为标准工具的全部理由。
3.2 2-范数情形的完整证明
这是最容易讲清楚的一半,用的工具只有:维数公式与奇异值的变分刻画(7-1-SVD的构造与几何意义 定理 7.1.15)。
证明()。
设 是任意 的 矩阵。
第一步:找一个同时"躲开" 的零空间、又落在前 个右奇异方向里的单位向量。
考虑两个子空间:
由维数公式(两个子空间之和的维数不超过全空间维数):
所以交集不是零空间,存在非零向量 。取
(这是本篇唯一一处"巧妙"的地方:两个维数之和超过 的子空间必然相交。)
第二步:利用 把 消掉。
因为 ,
(第一个不等号用了 2-范数的定义 ,取 只是一个"可行点",所以是""。)
第三步:用 给出 的下界。
因为 标准正交,把 展开:,且
于是
(用了 ;注意 对 成立,若 则相应项为零)。由于 标准正交,
因为 ,所以 对一切 成立。于是
第四步:合并。
由于 是任意秩 的矩阵,这给出了所有秩 矩阵的下界。
等号可达。 取 ,由引理 7.2.3 知 的奇异值是 ,故其最大奇异值为 ,即 。下界被达到,故 是最优解。
3.3 Frobenius 范数情形:证明思路
Frobenius 情形的证明需要一条奇异值的扰动不等式。
引理 7.2.5(奇异值的次可加性) 设 是同型实矩阵,则对任意 ,
证明思路。 由 7-1-SVD的构造与几何意义 定理 7.1.15 的变分刻画,
对任一固定的 (维数 )与单位向量 ,用三角不等式 。再把 拆成两项之和(第一项用 型估计,其中 是 中"对 最不利"的 维子空间,第二项同理),最后对 取下确界即得。这是标准的奇异值不等式(Horn 不等式的一个特例),细节可查 Horn & Johnson《Matrix Analysis》。
证明(Frobenius 情形)。 设 ,记 。
第一步:把 写成 并用引理 7.2.5。
在引理 7.2.5 中取 、、、 任意:
而 意味着 的第 个奇异值为零(7-1-SVD的构造与几何意义 定理 7.1.9:非零奇异值个数 = 秩),即 。于是得到关键式
第二步:两边平方求和。
(中间用了 7-1-SVD的构造与几何意义 定理 7.1.12:。)
第三步:等号可达。 取 ,由引理 7.2.3, 的奇异值恰为 ,故
记住这个结构
Eckart–Young 的两个范数情形共用同一个结论"最优解是 ",但下界的来源不同:
- 2-范数:靠"维数相交"的构造性论证,只用到 ;
- Frobenius 范数:靠奇异值的次可加性引理,把所有 逐个"转移"到 的奇异值上,再整体平方求和。
工程上更常用 Frobenius 版本,因为它能逐项累加,可以直接算出"保留 项后还差多少",而 2-范数只告诉你"最坏方向差多少"。
3.4 误差公式汇总
| 范数 | 最优误差 | 用代码算 |
|---|---|---|
| 谱范数(2-范数) | s[k](numpy 中 s 从 0 开始索引) | |
| Frobenius 范数 | np.sqrt((s[k:]**2).sum()) | |
| 相对误差(F) | 见 5.4 节代码 | |
| 能量占比 | (s[:k]2).sum()/(s2).sum() |
注意能量占比 + 相对误差的平方 = 1:
这条恒等式在下面反复使用。
四、图像作为矩阵
4.1 灰度图就是一个矩阵
一张灰度图(grayscale image)由 个像素排成矩形,每个像素的亮度用一个数表示。于是
- 是行数(图像高度,单位像素);
- 是列数(图像宽度);
- 是第 行第 列像素的灰度值(gray level),常用 8 位无符号整数,取值 (纯黑)到 (纯白),共 级。
存储量: 一张 的 8 位灰度图需要
例如 的灰度图需要 字节 KB。
4.2 彩色图是三个矩阵
彩色图用三通道(RGB)表示:红(red)、绿(green)、蓝(blue)各一个矩阵,
存储量为 字节。对彩色图做压缩,标准做法是对三个通道分别做 SVD 与截断,因为通道之间的相关性较弱,分开处理效果已经足够好(更好的做法是先做色彩空间变换,但那是图像处理的专门话题)。
其他通道数: 带透明度(alpha)的图是 4 个矩阵(RGBA);医学影像(如 CT、MRI 的切片序列)和高光谱图像可能有几十到几百个通道,这时可以把"通道"当作额外维度,用张量分解处理——那是 SVD 的高维推广。
4.3 图像矩阵为什么近似低秩
自然图像有两个特点使它的奇异值衰减很快:
- 空间相关性:相邻像素的灰度值高度相关(一条边界不会在一像素内突变)。这种"光滑性"意味着图像矩阵的行与行、列与列高度相似,线性无关的方向很少。
- 结构性:图像里通常只有少量"大尺度结构"(天空、人脸、建筑轮廓),细节只占很小一部分能量。
结果是:前几十个奇异值就能抓住图像的绝大部分能量。这正是压缩可行的原因,也是本篇 5.4 节实测数据要展示的现象。
这里有一个重要的概念区分
精确的秩与有效的秩(numerical rank / effective rank)不是一回事。
一张自然图像的矩阵在数学上几乎总是满秩的()——因为噪声、量化误差、纹理细节让所有奇异值都严格大于 。但它的奇异值从 到 衰减极快,后面成千上万个奇异值都小到无关紧要。
所以"图像是低秩的"这句话的准确含义是:图像可以被一个低秩矩阵很好地逼近,而不是"图像矩阵的秩很小"。
五、图像压缩的完整流程
5.1 存储量与压缩比
原始存储量。 灰度图需要存储 个数。
压缩后的存储量。 只保留前 项需要存储:
| 要存的东西 | 形状 | 元素个数 |
|---|---|---|
| 左奇异向量 | 是 | |
| 奇异值 | 一维, 个 | |
| 右奇异向量 | 是 | |
| 合计 |
压缩比公式
当 (即 )时才有压缩效果;对 的方图,这个条件是 。
存储量从 降到 ——这就是"图像压缩"的全部算术。
5.2 的压缩比表
以 为例,:
| 存储量 | 压缩比 | 说明 | |
|---|---|---|---|
| 1 | 1 025 | 255.75 | 只剩最强的单一模式 |
| 5 | 5 125 | 51.15 | 只够看出大致轮廓 |
| 10 | 10 250 | 25.58 | 主体结构已经可见 |
| 20 | 20 500 | 12.79 | 细节开始出现 |
| 25 | 25 625 | 10.23 | 约 10 倍压缩 |
| 26 | 26 650 | 9.84 | 压缩比首次跌破 10 |
| 50 | 51 250 | 5.12 | 视觉上已相当接近原图 |
| 100 | 102 500 | 2.56 | 压缩收益明显下降 |
| 200 | 205 000 | 1.28 | 已几乎不压缩 |
请特别注意这张表里的一处常见口误
的图像取 时,压缩比约为 倍,而不是 倍。 想达到约 倍压缩,需要取 ()。
这个"差一倍"的直觉错误很常见,原因是把 粗略估成 时算对了,但若误用 就漏掉了因子 。记住公式里的 里有两项,不要漏。
反过来看也很有启发:当 接近 时压缩比降到 ——此时"压缩"完全失效。这说明 SVD 压缩有明确的适用范围:只有当奇异值衰减足够快、少数几项就能抓住大部分能量时才有意义。
5.3 完整流程(八步)
图像压缩的可操作步骤
1. 读入图像为矩阵:灰度图直接读成一个 矩阵;彩色图读成三个矩阵(RGB 三个通道)。
2. (可选)归一化:把灰度值转为浮点数(例如除以 255 或减去均值),避免数值范围过大导致的精度问题。
3. 做完整 SVD:,得到 。
4. 画奇异值衰减曲线:把 对 作图(或画 )。曲线"拐弯"的位置就是合适的 。
5. 计算能量占比:对若干候选 算 ,选出达到目标(如 99%)的最小 。
6. 截断并重构:。
7. 报告压缩比与误差:,相对误差 。
8. (若需要真正存储/传输)量化:把 的元素量化成定点数或 8 位整数,再交给通用的熵编码器(如 Huffman、算术编码)压缩。这一步才是"图像文件格式"(JPEG 等)做的事,见 10.1 节的说明。
5.4 真实数值: 合成图的实验结果
下面这组数据来自本篇 7.2 节给出的代码对一张 合成灰度图( 频谱纹理 + 低频结构 + 一个高斯亮斑 + 一个暗矩形块)的实际计算结果:
- 图像尺寸 ,(满秩,符合 4.3 节的说明);
- ,,,,;
- (条件数很大,说明奇异值跨度极大 → 衰减快 → 适合压缩)。
| 能量占比 | 相对误差 | 压缩比 | ||
|---|---|---|---|---|
| 1 | 90.170% | 31.353% | 6 957.26 | 127.75 |
| 2 | 94.224% | 24.033% | 4 272.97 | 63.88 |
| 3 | 95.754% | 20.607% | 2 912.92 | 42.58 |
| 5 | 96.851% | 17.745% | 1 919.02 | 25.55 |
| 10 | 97.878% | 14.566% | 1 179.98 | 12.78 |
| 20 | 98.675% | 11.513% | 778.24 | 6.39 |
| 25 | 98.896% | 10.505% | 643.67 | 5.11 |
| 50 | 99.468% | 7.293% | 398.96 | 2.56 |
| 100 | 99.835% | 4.066% | 214.58 | 1.28 |
| 150 | 99.956% | 2.088% | 125.52 | 0.85 |
| 200 | 99.994% | 0.768% | 61.76 | 0.64 |
从这张表可以读出三件事:
- 能量集中得极快: 就抓住 90.17%, 已到 97.88%。这就是"图像近似低秩"的量化证据。
- 相对误差下降得比能量上升慢:从 到 ,能量从 90.17% 升到 99.994%,但相对误差只从 31.35% 降到 0.77%。原因:相对误差的平方 能量占比,所以能量占比从 到 时,误差平方从 到 ,误差本身从 到 ——误差是"平方根尺度"的量,天然下降得慢。这就是为什么数值上"误差降到 10% 以下"需要 ,而不是 。评价压缩质量时,用能量占比比用相对误差更直观。
- 谱范数误差恰好等于下一个奇异值:表中第 4 列的每一个数都精确等于对应的 ——这是 Eckart–Young 定理在数值上的直接体现。
5.5 奇异值衰减曲线如何指导选择
由于 的误差完全由"被丢掉的奇异值"决定,唯一真正重要的信息就是奇异值的衰减速度。工程上有四种常用的选 方法:
方法一:能量占比阈值法(最常用)
选定阈值 (如 或 ),取最小的 使
优点:直接对应"保住了多少信息",可解释性强。上表中取 会得到 ()或 ()。
方法二:碎石图(scree plot)找拐点
把 对 作图(通常用对数纵轴)。曲线通常先陡降、后平缓,转折点("肘部",elbow)就是合适的 ——因为过了拐点之后奇异值下降变慢,说明剩下的都是"噪声级别"的分量。也可以画 :若后段近似为直线,说明奇异值按指数衰减。
方法三:Hardy 阈值 / 相对阈值法
固定一个相对阈值 (如 ),保留所有满足 的奇异值。等价于"丢掉比最大奇异值小三个数量级的分量"。numpy 的 np.linalg.matrix_rank 与 np.linalg.pinv 内部就采用这种"相对阈值"判据。
方法四:按目标压缩比反解
若给定压缩比目标 ,由 反解:
例如 、目标 ,得 ,故 。
实用建议
真实项目里通常同时看三条曲线:奇异值衰减曲线(判断可压缩性)、能量占比曲线(判断 取多少)、相对误差曲线(判断视觉质量)。只盯一个指标容易做出错误决策。另外注意:视觉质量与数值误差不是线性关系——相对误差 10% 的图像看起来可能"还可以",而 5% 的误差在平坦区域(天空)会表现为明显的块状失真。
六、计算方法与步骤
6.1 手算小矩阵的秩 逼近
手算五步
1. 做完整 SVD:(用 7-1-SVD的构造与几何意义 的七步法)。
2. 读出奇异值:排序后取前 个。
3. 写出秩一展开:。
4. 截断:,逐项算 (注意 是 的外积矩阵)。
5. 报误差:,,并可验证 。
6.2 大矩阵的数值实践
- 永远用
np.linalg.svd,不要算 的特征值(原因见 7-1-SVD的构造与几何意义 7.3 节:条件数会平方)。 - 大矩阵用
full_matrices=False:默认的full_matrices=True会算出完整的 的 ,当 时要额外算 个数,纯属浪费。取缩减形式只需要 的前几列。 - 只要前 项时,可以用随机算法:对超大矩阵(例如 的稀疏矩阵),完整 SVD 的代价 太高。此时用随机 SVD(randomized SVD)——先乘一个随机矩阵把列数降到 ,再对小矩阵做精确 SVD。这能把代价降到 量级。
- 只想要奇异值不想要向量:
np.linalg.svdvals(A)比np.linalg.svd(A)快得多。
6.3 可运行代码(只用 numpy)
import numpy as np
# ---------- 1. 构造一张 256x256 的合成灰度图 ----------
rng = np.random.default_rng(7)
n = 256
# 1/f 幅度谱的随机纹理:模拟自然图像的慢衰减奇异值
fy = np.fft.fftfreq(n)[:, None]
fx = np.fft.fftfreq(n)[None, :]
r = np.sqrt(fx ** 2 + fy ** 2)
r[0, 0] = 1.0
phase = rng.uniform(0, 2 * np.pi, size=(n, n))
field = np.real(np.fft.ifft2(np.exp(1j * phase) / r ** 1.15))
field = (field - field.mean()) / field.std()
# 叠加低频结构、一个高斯亮斑、一个暗矩形块
x = np.linspace(0, 1, n)
X, Y = np.meshgrid(x, x)
img = (128
+ 42 * field
+ 45 * np.sin(2 * np.pi * X) * np.cos(2 * np.pi * Y)
+ 55 * np.exp(-((X - 0.32) ** 2 + (Y - 0.68) ** 2) / 0.012)
- 40 * (X > 0.62) * (Y < 0.38))
img = np.clip(img, 0, 255)
m, nn = img.shape
print("图像尺寸:", img.shape, " 矩阵秩:", np.linalg.matrix_rank(img))
# ---------- 2. 做 SVD ----------
U, s, Vt = np.linalg.svd(img, full_matrices=False) # 缩减 SVD
print("前 10 个奇异值:", np.round(s[:10], 2))
# ---------- 3. 按不同 k 重建,打印压缩比与相对误差 ----------
tot_energy = (s ** 2).sum()
norm_A = np.linalg.norm(img, 'fro')
print(f"{'k':>4} {'能量占比%':>10} {'相对误差%':>10} {'||A-Ak||_2':>12} {'压缩比':>8}")
for k in [1, 2, 3, 5, 10, 20, 25, 50, 100, 150, 200]:
A_k = (U[:, :k] * s[:k]) @ Vt[:k]
energy = (s[:k] ** 2).sum() / tot_energy
rel_err = np.linalg.norm(img - A_k, 'fro') / norm_A
spec_err = np.linalg.norm(img - A_k, 2)
ratio = m * nn / (k * (m + nn + 1))
print(f"{k:>4} {energy * 100:>10.3f} {rel_err * 100:>10.3f} {spec_err:>12.3f} {ratio:>8.2f}")
# ---------- 4. 验证 Eckart-Young:误差恰为 sigma_{k+1} ----------
for k in [1, 10, 50]:
A_k = (U[:, :k] * s[:k]) @ Vt[:k]
print(f"k={k}: ||A-A_k||_2 = {np.linalg.norm(img - A_k, 2):.6f}, "
f"sigma_(k+1) = {s[k]:.6f}, "
f"相等? {np.isclose(np.linalg.norm(img - A_k, 2), s[k])}")
# ---------- 5. 随机秩 k 矩阵不可能更优(数值验证定理 7.2.4) ----------
k = 20
best2 = np.linalg.norm(img - (U[:, :k] * s[:k]) @ Vt[:k], 2)
bestF = np.linalg.norm(img - (U[:, :k] * s[:k]) @ Vt[:k], 'fro')
better = sum(
np.linalg.norm(img - rng.normal(size=(m, k)) @ rng.normal(size=(k, nn)), 2) < best2 - 1e-9
or np.linalg.norm(img - rng.normal(size=(m, k)) @ rng.normal(size=(k, nn)), 'fro') < bestF - 1e-9
for _ in range(2000)
)
print(f"2000 个随机秩 {k} 矩阵中,比 A_k 更优的个数: {better}")
6.4 显示重建结果(需要 matplotlib)
本示例需要 matplotlib:pip install matplotlib
import numpy as np
import matplotlib.pyplot as plt
# 沿用上一段代码的 img, U, s, Vt
fig, axes = plt.subplots(2, 3, figsize=(12, 8))
for ax, k in zip(axes.ravel(), [1, 5, 10, 25, 50, 200]):
A_k = (U[:, :k] * s[:k]) @ Vt[:k]
energy = (s[:k] ** 2).sum() / (s ** 2).sum() * 100
ratio = img.size / (k * (img.shape[0] + img.shape[1] + 1))
ax.imshow(A_k, cmap='gray', vmin=0, vmax=255)
ax.set_title(f"k={k} 能量 {energy:.2f}% 压缩比 {ratio:.1f}")
ax.axis('off')
plt.tight_layout()
plt.show()
# 奇异值衰减曲线(对数纵轴)
plt.figure()
plt.semilogy(np.arange(1, len(s) + 1), s, 'o-', markersize=3)
plt.xlabel('i')
plt.ylabel('sigma_i')
plt.title('奇异值衰减曲线')
plt.grid(True, which='both', alpha=0.3)
plt.show()
读代码的一点提醒
(U[:, :k] s[:k]) @ Vt[:k]里的U[:, :k] s[:k]用的是 numpy 的广播:s[:k]形状是(k,),广播到(m, k)时按每一列乘,恰好等价于 。这与 7-1-SVD的构造与几何意义 中提到的(u * s[..., None, :]) @ vh是同一个技巧。若写成U[:, :k] @ np.diag(s[:k]) @ Vt[:k]结果完全相同,只是多建了一个对角矩阵。
七、例题
7.1 例题 1( 矩阵的完整低秩逼近)
设 (与 7-1-SVD的构造与几何意义 例题 2 同一个矩阵)。求它的最佳秩 逼近 ,并验证 Eckart–Young 定理。
解。
第 1 步:回忆该矩阵的 SVD。
在 7-1-SVD的构造与几何意义 中已求得
第 2 步:写出秩一展开。
第 3 步:算第一项 。
先算外积 ( 乘 ,得 ):
再乘 :
第 4 步:算第二项 (用于验证)。
第 5 步:验证秩一展开。
第 6 步:读出最佳秩 逼近。
第 7 步:验证 Eckart–Young 的误差公式。
第 8 步:讨论。
- 误差 ,相对误差 ——因为 只有两个奇异值,丢掉一个就丢了一半的能量(,所以能量占比 ,相对误差 )。
- Eckart–Young 保证:任何秩 的 矩阵 ,都满足 且 。 同时达到两个下界。
- 注意 的两列完全相同(都是 ),这正是"秩 "的体现:秩 矩阵的列空间只有一维,所有列必须共线。
7.2 例题 2(压缩比与 的选择)
某 的灰度图,其奇异值满足近似规律 (即每个奇异值是前一个的 倍)。
(a) 求 时的压缩比。
(b) 求 时的能量占比。
(c) 若要求能量占比不低于 ,求最小的 。
(d) 若要求压缩比不低于 ,求允许的最大 。
解。
(a) 压缩比。
,,,。
答:约 倍压缩。
(b) 能量占比。
令 。则 ,是公比为 的等比数列。
(这里用了等比级数求和;因为 收敛极快,用无穷和近似有限和误差可以忽略。)
答:能量占比约 (顺带得到相对误差 )。
(c) 求 的最小 。
要 ,即 。两边取自然对数(注意 ,不等号反向):
所以最小整数 。
校验: ✓; ✓。而 时 , ✗。
答:。
(d) 求 的最大 。
所以最大整数 。
校验: ✓; ✗。
答:。
综合讨论。 (c) 给出 (质量要求),(d) 给出 (大小要求),两者有交集,所以同时满足两个目标是可以做到的。例如取 :,。这是一个"两边都很宽裕"的折中。
从这道题学到的
压缩比与质量是同一个参数 的两端,压缩比随 单调递减、质量随 单调递增。 实际选择 就是在"我要多小"和"我要多清楚"之间取折中。这也解释了为什么这个衰减规律()的图像特别好压缩: 就已经到 99% 能量,而压缩比还有 倍。
八、去噪原理
8.1 为什么小奇异值常常是噪声
设含噪图像为
其中 是干净图像(近似低秩,能量集中在少数奇异值上), 是随机噪声。
典型的随机噪声(如高斯白噪声、传感器热噪声)有一个关键性质:它在所有方向上强度大致相同,没有偏好方向。用矩阵的语言说:噪声矩阵近似是"满秩、各向同性"的——它的奇异值不会衰减,而是均匀地摊在很宽的范围内。
两条性质合起来给出结论:
- 干净信号的能量 → 集中在少数大奇异值;
- 噪声的能量 → 分散在大量小奇异值上。
于是对 做 SVD,大的奇异值主要来自信号,小的奇异值主要来自噪声。把小于阈值的奇异值置零再重构,就得到去噪结果:
8.2 真实数值:去噪实验结果
对上节那张 图加标准差为 的高斯噪声(含噪图相对干净图的误差为 ),再做截断 SVD 重构:
| 与干净图的相对误差 | 与含噪图的相对误差 | |
|---|---|---|
| (含噪原图,未处理) | 0.1607 | 0 |
| 5 | 0.1804 | 0.2327 |
| 10 | 0.1529 | 0.2081 |
| 20 | 0.1337 | 0.1831 |
| 30 | 0.1300 | 0.1660 |
| 50 | 0.1337 | 0.1392 |
| 80 | 0.1433 | 0.1059 |
| 120 | 0.1527 | 0.0703 |
怎么读这张表:
- 第 2 列才是真正关心的量(我们想看的是"离干净图有多远")。它先下降、在 处达到最小 ,然后又上升。
- 太小():信号本身也被削掉了(欠拟合),误差 反而比不处理()还差——去噪做过头比不去噪更糟。
- 太大():噪声被保留下来(过拟合),误差回到 。
- 存在一个最优的 (这里约 ),它在"丢掉信号"和"保留噪声"之间取得平衡。去噪效果最好时误差从 降到 ,改善了约 。
- 第 3 列随 单调下降是必然的(重构得越"接近含噪图",离含噪图就越近),但它不能用来选 ——这正是"过拟合"在数值上的表现:一味追求接近含噪数据,就会把噪声一起学进去。
去噪的关键难点
最优 是未知的,因为干净图 在现实中拿不到。 上表第 2 列在真实场景中无法计算。实际做法包括:交叉验证、基于噪声方差的阈值估计(如 Marchenko–Pastur 律给出的噪声奇异值上界)、或干脆由人工按视觉质量调参。
另外,低秩去噪只对"近似低秩信号 + 各向同性噪声"有效。若噪声本身有结构(如条纹噪声、固定模式噪声),或者信号本身不低秩(如纯随机纹理),这个方法会失效甚至变差。
8.3 与其他方法的对比
| 方法 | 思路 | 适用情形 | 局限 |
|---|---|---|---|
| 截断 SVD 去噪 | 丢弃小奇异值 | 信号低秩、噪声各向同性 | 需要选 ;纹理细节会被削掉 |
| 均值/中值滤波 | 邻域平滑 | 孤立噪点 | 同时模糊边缘 |
| 小波阈值去噪 | 在小波域丢弃小系数 | 分段光滑信号 | 需要选小波基与阈值 |
| 全变分(TV)去噪 | 最小化全变分 | 分段常数图像(卡通) | 数值优化较慢;产生阶梯效应 |
截断 SVD 的优势在于完全没有参数化的先验假设(不需要指定滤波器形状、小波基),只依赖"信号低秩"这一条——这也正是它的局限所在。
九、其他低秩应用
9.1 推荐系统与矩阵补全
问题。 一个视频网站有 个用户、 个视频,评分矩阵 中 是用户 对视频 的评分。现实中绝大多数格子是空的(用户只看过极少数视频),所以只知道 在一个小集合 上的元素。
假设。 用户的偏好由少数几个隐含因子(喜欢科幻/喜欢慢节奏/……)决定,因此真实的完整评分矩阵是近似低秩的。
问题(矩阵补全,matrix completion)。 求
与 SVD 的关系。 这是低秩逼近的"带缺失数据"版本,比低秩逼近更难(不能直接做 SVD,因为矩阵有缺失项)。标准做法是:
- 用核范数(nuclear norm) 代替秩——它是秩的凸包络,使得问题变成可解的凸优化;
- 或者用交替最小化(alternating least squares):固定 解 、固定 解 ,反复迭代,其中 ,、。
核范数取代秩这个想法与 SVD 的关系:,即"奇异值之和",正如 、"秩 "。三个量都是奇异值的函数,分别对应 、、 型度量——这也是压缩感知里" 取代 "的同一套思想。
9.2 潜在语义索引(LSI)
问题。 在文本检索中,直接按词匹配会失败:用户搜"汽车",一篇只写"轿车"的文档匹配不到,因为两篇文档没有共同词汇。
做法。 构造词—文档矩阵 : 是词表大小, 是文档数, 是词 在文档 中的权重(常用 TF-IDF 权重)。
对 做 SVD 并截断到前 项:
解读。 就是潜在语义空间的维数(latent semantic space dimension),通常是几百(远小于词表大小 与文档数 )。
- 的第 行给出词 在 维语义空间中的坐标;
- 的第 行给出文档 在同一个语义空间中的坐标;
- 两者在同一个空间里,于是可以直接算余弦相似度。
为什么能解决同义词问题。 截断 SVD 把"只在少数文档里共现的词"这类噪声维度丢掉,保留下来的 个方向是共现模式的"主成分"。同义词(汽车/轿车)在同一批文档中出现,它们在这个空间里会落到相近的位置——即使从未在任何一篇文档中同时出现。检索时把查询也投影到该空间,就能匹配上语义相近的文档。
与 PCA 的关系。 LSI 的数学结构与 7-3-主成分分析PCA 完全一致:都是"对数据矩阵做截断 SVD"。差别只在解释:PCA 里行是样本、列是特征,主方向是"样本变化最大的方向";LSI 里行是词、列是文档,潜在方向是"词共现的主要模式"。
9.3 其他应用一览
| 应用 | 矩阵 | "低秩"意味着 | 截断后得到 |
|---|---|---|---|
| 图像压缩 | 像素矩阵 | 空间相关性强 | JPEG 类压缩的数学基础 |
| 图像去噪 | 含噪图像 | 信号低秩、噪声各向同性 | 干净图像估计 |
| 推荐系统 | 用户—物品评分 | 偏好由少数隐含因子驱动 | 缺失评分的预测 |
| 潜在语义索引 | 词—文档 | 主题数量有限 | 词的语义坐标 |
| 系统辨识 | 脉冲响应(Hankel 矩阵) | 系统的阶数低 | 降阶模型 |
| 阵列信号处理 | 协方差矩阵 | 信号源数量少 | 波达方向估计(MUSIC 类算法) |
| 背景建模 | 视频帧矩阵 | 背景静止(低秩) | 前景(稀疏)分离 |
| 神经网络压缩 | 权重矩阵 | 权重冗余 | 低秩因子分解 |
"背景建模"值得多说一句。 把一段视频的每一帧拉成一个列向量,排成矩阵 (列 = 帧),则静止背景在每一帧中几乎相同,对应 的低秩部分;运动前景(走动的人、车辆)只在少数像素上非零,对应 的稀疏部分。于是
这就是鲁棒主成分分析(robust PCA)。有趣的是:普通的 PCA(截断 SVD)在这里会失败——因为运动的物体往往幅度很大、能量很高,会被算进"主要成分"里;只有把低秩与稀疏同时约束,才能正确分离。这说明"低秩"是一个有适用范围的假设,不是万能钥匙。
十、易错点与常见误解
七个高频错误
1. "被压缩的是图像文件"。 这是最大的误解。SVD 压缩的是图像矩阵的存储量(从 个数降到 个数),得到的 还是浮点数,每个通常占 4 或 8 字节,而原始灰度图的每个像素只占 1 字节。所以:
- 按"元素个数"算, 取 是 倍的压缩;
- 按实际字节数算(原始 1 字节/像素, 与 用 4 字节浮点),实际大小是 字节,只有 倍的"压缩";
- 真正的图像文件格式(如 JPEG)还要再做量化与熵编码,把 的元素也压成低位定点数。"SVD 压缩"是原理演示,不是可以直接替代 JPEG 的产品技术。 这一点必须在理解上分清楚,否则会得出"SVD 比 JPEG 好"的错误结论。
2. 舍入误差导致奇异值不会精确为 。 理论上 时 ,但浮点运算下算出来的小奇异值一般不是精确的 ,而是 量级的小正数。后果:
-
np.linalg.matrix_rank(A)不能简单地数"非零奇异值个数",它内部默认用相对阈值max(M,N) eps s[0]来判断(可传tol参数调整);- 判断两个奇异值是否"相等"必须用容差,不能用
==;- 若 的构造本身带误差(例如由实验数据组装), 的数值结果可能远大于理论值。这就是 4.3 节说的"精确秩"与"有效秩"的区别。
3. 误以为秩 逼近可以保留 个"特征"。 是奇异值的个数,不是"原始列/特征的个数"。 的列是新的正交方向,一般是原始数据的线性组合,没有"第 3 列"这样的直接对应。所以截断 SVD 不能当特征选择用(这一点在 7-3-主成分分析PCA 中会再次强调)。
4. 忘记
full_matrices=False。 对 的图,默认的full_matrices=True会额外算出 的完整 ( 个数),而其实只需要前 列。大数据集上这是巨大的浪费,甚至直接内存溢出。5. 用相对误差评价压缩质量。 相对误差 是"平方根尺度"的,从 到 只把误差从 31.6% 降到 3.2%,看起来"提升很小",但视觉上差别巨大。评价压缩质量应该看能量占比与视觉结果,而不是只看相对误差的数值。
6. 以为 唯一。 Eckart–Young 定理只保证"最优误差是 ",最优矩阵在奇异值有重复时不唯一(定理 7.2.4 的适用条件)。例如 时,在这个重奇异值子空间里任意旋转都给出同一个最优误差。实践影响很小(误差值一样),但不要用两次运行的 逐元素比对来判断算法是否正确。
7. 对稀疏矩阵直接用截断 SVD。 若 是稀疏的(如推荐系统的评分矩阵),
np.linalg.svd会把稀疏结构破坏掉——它会先把 稠密化,然后做 的分解。 的稀疏矩阵这样做是不可行的。应该用随机 SVD、Lanczos 双对角化或交替最小二乘等专用方法(这些算法不在 numpy 的linalg里,需要专门的库)。
十一、练习题
练习 1(基础) 某 灰度图的奇异值满足 。
(a) 求 时的压缩比;
(b) 求 时的能量占比与相对误差;
(c) 求使能量占比 的最小 ,以及此时的压缩比。
练习 2(基础) 已知 是 矩阵,奇异值为 。写出 的秩,以及 、、 的值。
练习 3(进阶) 设 。求它的 SVD(提示: 是对角矩阵),写出 ,并验证 、。
练习 4(进阶) 证明:若 ,则 ,且对一切 有 。再证明:对一般的 , 当且仅当 。
练习 5(进阶) 证明能量占比与相对误差的关系
并说明为什么这个式子对任意 都成立(不依赖 Eckart–Young 定理)。
练习 6(思考) 设 是 矩阵, 都很大。有人说:"既然 是最优秩 逼近,那么取 就可以用极小的误差把秩降低 ,反复这样做就能把任意矩阵压缩到很低秩而误差很小。"请指出这段话的错误。提示: 考虑奇异值衰减速度;构造一个反例(例如 )。
练习 7(思考) 在 8.2 节的去噪实验里,为什么"与含噪图的相对误差"随 增大而单调下降,却不能用来选择 ?请从"过拟合"的角度解释,并说明这与 Eckart–Young 定理是否矛盾。
十二、常见问题 FAQ
Q1:Eckart–Young 定理说 是最优的,那为什么实际图像压缩(JPEG)不用 SVD?
因为计算成本与工程约束。
- SVD 的代价是 ,对一张 的照片是 量级,太慢;JPEG 用的 DCT(离散余弦变换)有快速算法,复杂度低得多,而且可以分块()并行处理。
- SVD 需要整幅图像才能算出 ,无法边读边压;JPEG 分块处理可以流式进行。
- SVD 的 元素是实数,量化后还需要额外编码;DCT 系数有成熟的量化表与熵编码方案。
- 更重要的是:Eckart–Young 最优性是在"秩 "这个约束类里最优,而 JPEG 的约束类(分块 DCT + 量化 + 熵编码)与"秩 "完全不同,两者不在同一个赛道上。最优性只在给定的约束类内有意义。
SVD 在图像处理研究中依然常用:去噪、背景建模、人脸识别(Eigenfaces)、图像修复等,因为它的数学结构清晰、无需调参。
Q2: 取多大才"够"?有没有理论公式?
没有通用的理论公式,因为"够"取决于你要什么。三种常见判据:
- 能量占比阈值(如 99%):最常用,可解释性强;
- 碎石图拐点:看奇异值衰减曲线的转折位置;
- 压缩比约束: 反解 。
理论上有两个相关的界可以参考:若数据由"真实秩 的信号 + 方差 的噪声"构成,则由随机矩阵理论(Marchenko–Pastur 律),噪声的奇异值大致分布在 区间内,超过这个上界的奇异值才"可信"。这是统计上选 的一个有原则的依据。
Q3:为什么 2-范数下的最优误差恰好是 ,而 Frobenius 下是一整串平方和?
因为两个范数度量的是"最坏情况"与"整体情况"。
- 2-范数 只关心最大的那一个奇异值,所以残差 的 2-范数就是它最大的奇异值 。它回答的是"在某个方向上误差最大能到多少"。
- Frobenius 范数 把所有奇异值平方相加,所以它累加了全部残差方向的贡献。它回答的是"总体上误差有多大"。
工程上更常用 Frobenius,因为它可以逐项累加、便于设定阈值;2-范数(谱范数)更多用于理论分析(如条件数、扰动界)。用哪个范数,取决于问题关心"最坏方向"还是"整体能量"。
Q4:截断 SVD 与 PCA 是同一件事吗?
数学运算完全相同,解释与使用方式不同。
- 都有"对矩阵做 SVD 再截断"这一步;
- PCA 必须先中心化(每列减去均值),否则第一步主成分会被数据的均值方向占据,得到的不是"方差最大方向";截断 SVD 通常不中心化。
- PCA 的行是样本、列是特征,主方向解释为"样本变化最大的方向",方差是 ;截断 SVD 用在图像/词—文档矩阵上时,行与列的含义完全不同,"方差"这个词往往没有意义。
所以:PCA = 中心化 + 截断 SVD + 统计解释。 全部细节见 7-3-主成分分析PCA。
Q5:如果一个矩阵的奇异值不衰减(所有 差不多大),还能压缩吗?
不能,而且这是原理性的不可能。 若 ,则:
- 能量占比 ——保留 项只能保住 的能量,收益与 成正比,毫无"集中"优势;
- 由 Eckart–Young,误差 也几乎不下降。
直觉:奇异值全相等意味着椭球是"球"——矩阵在所有方向上同等重要,没有任何方向可以被牺牲。这时的矩阵(乘一个正交矩阵后的倍数)本质上就是"随机噪声",没有可压缩的结构。这也正好解释了 8.1 节"噪声的奇异值不衰减"的说法,以及练习 6 想让你发现的问题:低秩逼近的效果完全取决于奇异值衰减速度,没有任何方法能绕过这一点。
本篇小结
核心结论
- 低秩逼近问题:给定 (),在所有秩不超过 的矩阵中找与 最接近的那个。这是「用更少的信息概括一个矩阵」的数学表述。
- 截断 SVD 就是答案:,只保留前 个奇异值及其左右奇异向量。
- Eckart–Young 定理(本篇的核心定理): 在 2-范数与 Frobenius 范数下同时是最优的,且误差有精确公式:
- 误差可预测:不需要真的构造 再算误差——看第 个奇异值就知道 2-范数误差,看尾部奇异值的平方和就知道 Frobenius 误差。
- 能量占比 是选 的主要依据;相对重构误差是它的平方根:。
- 存储量公式:。元素个数意义上的压缩比是
- 奇异值 = 重要性: 度量第 个方向的能量大小。奇异值衰减越快,低秩逼近越有效——这正是图像、文本、评分矩阵都近似低秩的原因。
- 去噪原理:噪声通常贡献小的、分散的奇异值,图像的主要结构集中在少数大的奇异值上,截断即去噪。
- 图像即矩阵:灰度图是 个矩阵,彩色图是 个矩阵(R/G/B)。这个对应关系是 SVD 能用于图像处理的前提。
- 它是原理演示,不是产品技术:JPEG 等格式还要做量化与熵编码;理解 SVD 压缩的意义在于看穿「低秩 = 少量信息」,而不是去替代 JPEG。
易混概念对照
| 容易混淆的一对 | 区别 | 一句话记住 |
|---|---|---|
| 元素个数压缩比 与 实际字节压缩比 | 算的是数的个数,实际存储还要乘浮点字节数(4 或 8 字节),而原图每像素只占 1 字节 | 按元素算是几倍,按字节算可能只有一点几倍 |
| 与 | 前者 (单个最大误差),后者是尾部平方和开根 | 2-范数看一个,F 范数看一片 |
| 能量占比 与 相对误差 | ,是平方关系 | 对应 ,不是 |
| 秩 与「挑了 个特征」 | 是奇异值个数, 是新的正交方向,不对应原始某列 | 截断 SVD 不是特征选择 |
| 精确秩 与 有效秩 | 浮点下小奇异值不为精确 (约 量级),故数值秩需用阈值判定 | 数「非零奇异值」是错的 |
| 最优误差唯一 与 最优矩阵唯一 | 误差值唯一,但当 时最优矩阵不唯一 | 别用两次运行逐元素比对 |
自学检查清单
- 能不能写出 Eckart–Young 定理的完整表述,并说明为什么 同时是 2-范数与 F 范数下的最优?
- 给定 ,求 时的 2-范数误差、F 范数误差、能量占比与相对重构误差。
- 如果去掉「秩不超过 」这个约束会怎样?(答:只剩 自己,误差为 ,但毫无压缩意义——约束才是问题的全部价值。)
- 的图取 ,元素个数压缩比是多少?按字节算又是多少?为什么两者差这么多?
- 为什么去噪时截断掉小奇异值能去掉噪声?如果噪声的能量也集中在某个大奇异值上,这个方法还成立吗?
- 为什么对稀疏矩阵不能直接用
np.linalg.svd?应该用什么替代思路? - 用 numpy 对一张图做 的截断 SVD,画出奇异值衰减曲线,说明你在哪里「拐弯」。
相关笔记
- 7-1-SVD的构造与几何意义 —— 的推导、奇异值性质、伪逆
- 7-3-主成分分析PCA —— 同一套截断 SVD 运算的数据分析视角
- 6-4-对称矩阵与正定矩阵 —— 谱定理与二次型,理解"能量 "的基础
- 11-2-范数与条件数 —— 2-范数、Frobenius 范数、条件数的系统讨论
- 4-3-最小二乘逼近 —— 另一种"用低维子空间逼近数据"的思路
- 9-3-快速傅里叶变换FFT —— 另一种"换基"压缩(JPEG 的 DCT 与 FFT 同源)
- 附录-矩阵分解总览 —— 、、、 的对比
参考来源
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley–Cambridge Press, 2016. §7.2 "Image Compression" 与 §7.3(教材,文字引用)
- MIT OpenCourseWare 18.06 Linear Algebra, Spring 2010,Lecture 31: Change of basis; image compression;Lecture 29: Singular value decomposition;课程主页
- Strang 教材官网(含免费章节 PDF):<https://math.mit.edu/~gs/linearalgebra/>
- NumPy 官方文档:
numpy.linalg.svd;numpy.linalg.matrix_rank - Wolfram MathWorld:Frobenius Norm;Matrix Norm;Singular Value Decomposition
- C. Eckart & G. Young, "The approximation of one matrix by another of lower rank," Psychometrika 1 (1936), 211–218(原始文献,文字引用)
- G. H. Golub & C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013(数值算法与奇异值扰动不等式,文字引用)