第12章 低秩模型与 Robust PCA：核范数、矩阵补全与 L+S 分解

本章摘要： 在高维图像与视频数据中，数据点往往不是均匀分布在整个空间中，而是聚集在低维子空间附近。这种性质被称为“低秩性（Low-Rankness）”。 本章将深入探讨如何利用低秩先验来解决经典的逆问题。我们将重点介绍Robust PCA (RPCA) 模型，它不仅能像传统 PCA 那样降维，还能奇迹般地将图像分解为“干净的低秩背景”与“稀疏的异常前景”。我们将剖析其核心求解算法——奇异值阈值化（SVT），并讨论其在视频监控、去噪和矩阵补全（Matrix Completion）中的广泛应用。

12.1 低秩性的物理直觉：世界是重复的

在学习稀疏性时，我们认为“图像在变换域下大部分系数为零”。而低秩性则提供了另一种极其强大的全局视角：数据的行或列之间存在极强的线性相关性。

12.1.1 为什么图像矩阵是低秩的？

当我们把一系列图像向量化并堆叠成矩阵 $X$（每一列是一张图或一帧视频），矩阵的秩（Rank）揭示了数据的内在复杂度。

  1. 视频监控（静态背景）：

    • 考虑一个监控摄像头拍摄的空旷走廊。如果光照不变，每一帧画面几乎是一模一样的。
    • 数学上，这意味着矩阵的所有列都相等：$x_1 = x_2 = \dots = x_n$。
    • 此时，矩阵的秩为 1。

  2. 人脸图像（光照子空间）：

    • 对于同一个人的面部，尽管光照角度不同，Basri 和 Jacobs (2003) 证明了所有可能的朗伯体（Lambertian）反射图像都可以由 9个球谐基函数 的线性组合很好地近似。
    • 这意味着，哪怕有成千上万张不同光照的人脸图，它们堆叠成的矩阵的秩大约只有 9。

  3. 规则纹理与重复结构：

    • 建筑物表面的窗户、织物的纹理，如果将这些局部 Patch 拉成向量，它们之间也高度相关。

12.1.2 经典 PCA 的崩溃

传统的主成分分析 (PCA) 试图寻找一个低维子空间来拟合数据，其本质是最小化重构误差的 Frobenius 范数（即 $L_2$ 范数）： $$ \min_{L} |X - L|_F^2 \quad \text{s.t. } \text{rank}(L) \le k $$ 这里隐含了高斯噪声假设。然而，图像处理中常见的干扰往往不是微小的高斯噪声，而是大幅度的离群值（Outliers）：

  • 监控视频中突然走过的人（遮挡了背景）。
  • 人脸图像上的墨镜、围巾或阴影。
  • 图像传输中的脉冲噪声。

PCA 的脆弱性：哪怕矩阵中只有一个像素的值被篡改为无穷大，PCA 计算出的主成分方向就会被彻底拉偏。我们需要一种能够“容忍”大幅度恶意干扰的 PCA，这就是 Robust PCA。

12.2 数学基础：矩阵范数与凸松弛

为了设计可求解的优化算法，我们需要将组合性质的“秩”转化为连续、凸的函数。

12.2.1 向量范数与矩阵范数的对应关系

这组类比是理解低秩优化的关键：

| 特性 | 向量 ($x \in \mathbb{R}^n$) | 矩阵 ($X \in \mathbb{R}^{m \times n}$，奇异值 $\sigma$) |

特性 向量 ($x \in \mathbb{R}^n$) 矩阵 ($X \in \mathbb{R}^{m \times n}$，奇异值 $\sigma$)
稀疏度 / 复杂度 $L_0$ 范数 (非零元个数) 秩 (Rank) (非零奇异值个数)
凸松弛 (Convex Envelope) $L_1$ 范数 ($\sum \lvert x_i\rvert$) 核范数 (Nuclear Norm, $|X|_*$) ($\sum \sigma_i$)
欧氏长度 / 能量 $L_2$ 范数 ($\sqrt{\sum x_i^2}$) Frobenius 范数 ($|X|_F$) ($\sqrt{\sum \sigma_i^2}$)
最大幅值 $L_\infty$ 范数 ($\max \lvert x_i\rvert$) 谱范数 (Spectral Norm, $|X|_2$) ($\max \sigma_i$)

12.2.2 核范数 (Nuclear Norm)

矩阵 $X$ 的核范数定义为其奇异值之和： $$ |X|_* = \sum_{i=1}^{\min(m,n)} \sigma_i(X) $$ 由于奇异值总是非负的，核范数本质上就是奇异值向量的 $L_1$ 范数。它是 Rank 函数在谱范数单位球内的最紧凸松弛。这意味着，在许多条件下，最小化核范数等价于最小化秩。

12.3 核心算子：奇异值阈值化 (SVT)

在稀疏编码中，解决 $L_1$ 最小化的关键是软阈值（Soft Thresholding）。同理，在低秩优化中，解决核范数最小化的关键是 奇异值阈值化 (Singular Value Thresholding, SVT)。

12.3.1 优化问题

考虑以下近端算子问题： $$ \min_X \frac{1}{2} |X - Y|_F^2 + \tau |X|_* $$ 我们希望找到一个矩阵 $X$，它既接近观测值 $Y$，又具有较低的秩（由 $\tau$ 控制）。

12.3.2 SVT 算法流程

该问题的闭式解为 $\mathcal{D}_\tau(Y)$：

  1. 对 $Y$ 进行奇异值分解 (SVD)：$Y = U \Sigma V^T$，其中 $\Sigma = \text{diag}(\sigma_i)$。

  2. 对奇异值 $\sigma_i$ 执行软阈值收缩： $$ \hat{\sigma}_i = \max(\sigma_i - \tau, 0) $$

  3. 重构矩阵： $$ X = U \hat{\Sigma} V^T $$

ASCII 图解 SVT：

    原始矩阵 Y              SVD 分解                   软阈值收缩 (Shrinkage)           重构低秩矩阵 X
+---------------+      +---+ +-------+ +---+       +---+ +-----------+ +---+      +---------------+
| . . . . . . . |      |   | |s1     | |   |       |   | |s1-t       | |   |      | . . . . . . . |
| . . 噪 声 . . |  =>  | U | |  s2   | | V'|  =>   | U | |   s2-t    | | V'|  =>  | . 干 净 . . . |
| . . . . . . . |      |   | |    s3 | |   |       |   | |      0    | |   |      | . . . . . . . |
+---------------+      +---+ +-------+ +---+       +---+ +-----------+ +---+      +---------------+
                                ^                            ^
                           含有许多非零奇异值              小的奇异值被“杀”死
                               (高秩)                      变为精确的 0 (低秩)

注意：$\tau$ 越大，被置零的奇异值越多，结果矩阵 $X$ 的秩就越低。

12.4 Robust PCA (RPCA) 模型与求解

12.4.1 PCP 模型 (Principal Component Pursuit)

RPCA 假设观测数据 $M$ 由两部分组成： $$ M = L + S $$

  • $L$ (Low-Rank)：背景、共有结构。
  • $S$ (Sparse)：前景、异常值、脉冲噪声（可以是任意大幅度，但在空间分布上稀疏）。

数学模型为： $$ \min_{L, S} |L|_* + \lambda |S|_1 \quad \text{s.t. } L + S = M $$

这个模型非常优雅：它不需要指定秩是多少，也不需要指定稀疏度是多少，而是通过最小化两个凸函数的加权和自动寻找平衡。

12.4.2 求解算法：增广拉格朗日乘子法 (IALM / ADMM)

这是一个典型的线性约束凸优化问题，ADMM 是最常用的求解器。

构造增广拉格朗日函数： $$ \mathcal{L}(L, S, Y) = |L|_* + \lambda |S|_1 + \langle Y, M - L - S \rangle + \frac{\mu}{2} |M - L - S|_F^2 $$

迭代步骤（交替更新）：

  1. 更新 $L$（低秩部分）： 固定 $S$ 和对偶变量 $Y$，最小化 $L$。这等价于对残差做 SVT。 $$ L_{k+1} = \mathcal{D}_{1/\mu} \left( M - S_k + \frac{1}{\mu} Y_k \right) $$ 直觉：从数据中减去稀疏前景，剩下的做SVT提取背景。

  2. 更新 $S$（稀疏部分）： 固定 $L$ 和 $Y$，最小化 $S$。这等价于对残差做逐元素软阈值（Soft Thresholding）。 $$ S_{k+1} = \mathcal{S}_{\lambda/\mu} \left( M - L_{k+1} + \frac{1}{\mu} Y_k \right) $$ 直觉：从数据中减去低秩背景，剩下的做截断保留前景。

  3. 更新 $Y$（对偶/残差）： $$ Y_{k+1} = Y_k + \mu (M - L_{k+1} - S_{k+1}) $$

12.4.3 黄金准则：参数 $\lambda$ 的选择

Candès 等人的理论证明给出了一个无需调参的通用公式。对于 $n_1 \times n_2$ 的矩阵，只要 $L$ 和 $S$ 满足不相干性（Incoherence）条件，最优 $\lambda$ 为： $$ \lambda = \frac{1}{\sqrt{\max(n_1, n_2)}} $$

  • 物理意义：矩阵越大，区分低秩和稀疏越容易，所需的正则化强度 $\lambda$ 随维度增加而减小。
  • 工程经验：这是绝佳的起始值。如果觉得前景分离得不干净（混入了背景），适当调大 $\lambda$；如果背景中混入了前景，适当调小 $\lambda$。

12.5 矩阵补全 (Matrix Completion)

如果矩阵 $M$ 中只有一部分元素被观测到（记为集合 $\Omega$），其余位置缺失（如损坏的图像像素），我们能否恢复完整的 $X$？

模型

$$ \min_X |X|_* \quad \text{s.t. } P_\Omega(X) = P_\Omega(M) $$ 其中 $P_\Omega(\cdot)$ 是采样算子，只保留 $\Omega$ 内的元素，其余置零。

求解直觉

算法依然基于 SVT，但在每一步迭代中，我们需要强制将观测位置的值“拉回”到真实值 $M_{ij}$，而对未观测位置则保留 SVT 的预测值。

应用：

  • Inpainting：去除文字水印或修复老照片划痕。
  • 推荐系统：Netflix 电影评分预测（用户-电影矩阵极度稀疏且低秩）。

12.6 常见变体与扩展

  1. Stable PCP (含有高斯噪声)： 现实中往往同时存在稀疏的大噪声和稠密的小噪声（高斯）。 模型：$\min_{L, S} |L|_* + \lambda |S|_1 + \frac{1}{2\sigma^2}|M - L - S|_F^2$ 这实际上是把等式约束变成了惩罚项。

  2. Tensor RPCA (TRPCA)： 彩色视频本质上是三维张量（宽 $\times$ 高 $\times$ 时间）甚至四维张量。将张量展开（Unfold）成矩阵会破坏多维结构。基于 Tucker 分解或 t-SVD 的张量核范数方法能获得更好的效果。

  3. Online / Incremental RPCA： 标准 RPCA 需要一次性处理整个视频矩阵，内存消耗巨大。在线算法（如 Grassmannian 子空间追踪）可以一帧一帧地更新背景模型，适合实时监控。

12.7 本章小结

  1. 低秩 $\neq$ 简单：低秩意味着全局相关性，它能捕捉数据中重复出现的模式（背景、纹理、结构）。
  2. 核范数是关键：它是秩函数的凸替身。$|X|_*$ 之于矩阵，犹如 $|x|_1$ 之于向量。
  3. SVT 算子：通过 SVD 收缩奇异值，实现了秩的最小化。这是所有低秩优化的计算引擎。
  4. L+S 分解：RPCA 能够完美分离“静态背景”与“动态前景”，且对大幅度遮挡具有鲁棒性，这是 $L_2$ 范数无法做到的。
  5. 计算瓶颈：SVD 的复杂度为 $O(\min(m^2n, mn^2))$，对大矩阵极慢。工程上常结合随机化 SVD 或分块处理。

12.8 练习题

基础题

Q1: 奇异值与核范数 设矩阵 $A = \begin{bmatrix} 3 & 0 \\ 0 & -4 \end{bmatrix}$。

  1. 计算 $A$ 的奇异值。
  2. 计算 $|A|_*$（核范数）和 $|A|_F$（Frobenius 范数）。
  3. 为什么 $|A|_* > |A|_F$ 总是成立（除非秩为1或0）？
提示

奇异值是 $A^TA$ 特征值的平方根，对于对称阵也是特征值的绝对值。奇异值非负：4, 3。 $|A|_* = 4+3=7$。$|A|_F = \sqrt{3^2+(-4)^2} = 5$。 不等式类似 $L_1$ 与 $L_2$ 的关系：$(a+b)^2 > a^2+b^2$ 当 $a,b>0$。

Q2: RPCA 的物理意义 在视频背景建模中，为什么我们使用 $L_1$ 范数约束前景 $S$，而不是 $L_2$ 范数？如果使用 $L_2$ 范数（即 $\min |L|_* + \lambda |S|_F^2$），结果会有什么不同？

提示

$L_2$ 惩罚倾向于让误差均匀分布在所有像素上（平滑），这会导致前景的“鬼影”融入背景。$L_1$ 允许稀疏的大值，能让前景彻底从背景中“剥离”出来，保持背景的干净。

Q3: 秩的可加性？ $\text{rank}(A+B) = \text{rank}(A) + \text{rank}(B)$ 是否总是成立？这对 RPCA 分解有何启示？

提示

显然不成立（反例 $A=I, B=-I$）。通常 $\text{rank}(A+B) \le \text{rank}(A) + \text{rank}(B)$。RPCA 的目标正是把全秩的 $M$ 分解为低秩的 $L$ 和稀疏（通常也是高秩，但结构特殊）的 $S$。

挑战题

Q4: 不可辨识性 (Incoherence) 考虑一个矩阵，它只有第一行第一列的元素为1，其余为0。

  1. 它是低秩的吗？
  2. 它是稀疏的吗？
  3. RPCA 能否将其分解为 $L$ 和 $S$？为什么？这引出了什么理论假设？
提示

它是秩1矩阵（低秩），也是极度稀疏矩阵。RPCA 无法区分它属于 $L$ 还是 $S$。为了通过 RPCA 恢复，低秩矩阵必须是“不连贯的”（Incoherent），即其奇异向量不能像稀疏向量那样集中在少数几个坐标上（能量必须平铺）。

Q5: 随机化 SVD (Randomized SVD) 当矩阵规模达到 $10000 \times 10000$ 时，标准 SVD 不可行。请调研并简述 Randomized SVD 的基本思想：它是如何利用随机投影将大矩阵映射到小矩阵上计算奇异值的？这对精度有何影响？

提示

思路：用一个随机矩阵 $\Omega$ (瘦长) 乘以 $A$，得到草图 $Y = A\Omega$。计算 $Y$ 的正交基 $Q$，则 $A \approx Q Q^T A$。然后在小矩阵 $B = Q^T A$ 上做 SVD。这对于奇异值衰减快的矩阵（低秩矩阵）精度极高且速度极快。

12.9 常见陷阱与错误 (Gotchas)

1. 盲目做 Full SVD

现象：代码运行极慢，内存溢出。 原因：在 MATLAB/Python 中直接调用 svd(X) 会计算所有奇异值。而 RPCA 中 $L$ 的秩通常很低（例如 10-50），大部分奇异值都会被阈值 $\tau$ 归零。 对策：必须使用 svds (MATLAB) 或 scipy.sparse.linalg.svds (Python)，或者 Randomized SVD，仅计算前 $k$ 个最大的奇异值。如果发现第 $k$ 个奇异值大于 $\tau$，则增大 $k$ 重新计算。

2. 数据的尺度归一化

现象：无论怎么调 $\lambda$，分离出的 $S$ 要么是全零，要么 $L$ 是全零。 原因：核范数和 $L_1$ 范数的量级取决于数据本身。如果像素值范围是 [0, 255]，而公式中的 $\lambda$ 是基于归一化假设推导的。 对策：务必先将图像/视频数据归一化到 [0, 1] 区间，再运行算法。

3. 把 RPCA 当作“万能去噪器”

现象：试图用 RPCA 去除高斯白噪声。 原因：RPCA 的设计初衷是去除稀疏的大噪声（Outliers）。对于全图分布的高斯噪声，RPCA 的核范数会将其视为纹理的一部分保留在 $L$ 中，或者在 $S$ 中留下一堆杂乱的点。 对策：对于高斯噪声，请使用基于 Frobenius 范数的方法（如第4章的 Tikhonov 或第12.6节的 Stable PCP）。

4. 忽视了“对齐”的前提

现象：手持相机拍摄的视频，背景分离失败。 原因：RPCA 假设背景列向量是线性相关的。如果相机抖动，同一物理点在不同列中的位置不同，破坏了低秩性。 对策：必须先进行视频稳像 (Image Registration/Alignment)，将所有帧对齐后，再做 RPCA。或者使用由“RASL (Robust Alignment by Sparse and Low-rank decomposition)”提出的联合对齐与分解模型。