本章摘要： 在高维图像与视频数据中，数据点往往不是均匀分布在整个空间中，而是聚集在低维子空间附近。这种性质被称为“低秩性（Low-Rankness）”。 本章将深入探讨如何利用低秩先验来解决经典的逆问题。我们将重点介绍Robust PCA (RPCA) 模型，它不仅能像传统 PCA 那样降维，还能奇迹般地将图像分解为“干净的低秩背景”与“稀疏的异常前景”。我们将剖析其核心求解算法——奇异值阈值化（SVT），并讨论其在视频监控、去噪和矩阵补全（Matrix Completion）中的广泛应用。
在学习稀疏性时，我们认为“图像在变换域下大部分系数为零”。而低秩性则提供了另一种极其强大的全局视角：数据的行或列之间存在极强的线性相关性。
当我们把一系列图像向量化并堆叠成矩阵 $X$（每一列是一张图或一帧视频），矩阵的秩（Rank）揭示了数据的内在复杂度。
传统的主成分分析 (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。
为了设计可求解的优化算法，我们需要将组合性质的“秩”转化为连续、凸的函数。
这组类比是理解低秩优化的关键：
| 特性 | 向量 ($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$) |
矩阵 $X$ 的核范数定义为其奇异值之和： \(\|X\|_* = \sum_{i=1}^{\min(m,n)} \sigma_i(X)\) 由于奇异值总是非负的，核范数本质上就是奇异值向量的 $L_1$ 范数。它是 Rank 函数在谱范数单位球内的最紧凸松弛。这意味着，在许多条件下，最小化核范数等价于最小化秩。
在稀疏编码中，解决 $L_1$ 最小化的关键是软阈值（Soft Thresholding）。同理，在低秩优化中，解决核范数最小化的关键是 奇异值阈值化 (Singular Value Thresholding, SVT)。
考虑以下近端算子问题： \(\min_X \frac{1}{2} \|X - Y\|_F^2 + \tau \|X\|_*\) 我们希望找到一个矩阵 $X$，它既接近观测值 $Y$，又具有较低的秩（由 $\tau$ 控制）。
该问题的闭式解为 $\mathcal{D}_\tau(Y)$：
ASCII 图解 SVT：
原始矩阵 Y SVD 分解 软阈值收缩 (Shrinkage) 重构低秩矩阵 X
+---------------+ +---+ +-------+ +---+ +---+ +-----------+ +---+ +---------------+
| . . . . . . . | | | |s1 | | | | | |s1-t | | | | . . . . . . . |
| . . 噪 声 . . | => | U | | s2 | | V'| => | U | | s2-t | | V'| => | . 干 净 . . . |
| . . . . . . . | | | | s3 | | | | | | 0 | | | | . . . . . . . |
+---------------+ +---+ +-------+ +---+ +---+ +-----------+ +---+ +---------------+
^ ^
含有许多非零奇异值 小的奇异值被“杀”死
(高秩) 变为精确的 0 (低秩)
注意：$\tau$ 越大，被置零的奇异值越多，结果矩阵 $X$ 的秩就越低。
RPCA 假设观测数据 $M$ 由两部分组成： \(M = L + S\)
数学模型为： \(\min_{L, S} \|L\|_* + \lambda \|S\|_1 \quad \text{s.t. } L + S = M\)
这个模型非常优雅：它不需要指定秩是多少，也不需要指定稀疏度是多少，而是通过最小化两个凸函数的加权和自动寻找平衡。
这是一个典型的线性约束凸优化问题，ADMM 是最常用的求解器。
构造增广拉格朗日函数： \(\mathcal{L}(L, S, Y) = \|L\|_* + \lambda \|S\|_1 + \langle Y, M - L - S \rangle + \frac{\mu}{2} \|M - L - S\|_F^2\)
迭代步骤（交替更新）：
更新 $L$（低秩部分）： 固定 $S$ 和对偶变量 $Y$，最小化 $L$。这等价于对残差做 SVT。 \(L_{k+1} = \mathcal{D}_{1/\mu} \left( M - S_k + \frac{1}{\mu} Y_k \right)\) 直觉：从数据中减去稀疏前景，剩下的做SVT提取背景。
更新 $S$（稀疏部分）： 固定 $L$ 和 $Y$，最小化 $S$。这等价于对残差做逐元素软阈值（Soft Thresholding）。 \(S_{k+1} = \mathcal{S}_{\lambda/\mu} \left( M - L_{k+1} + \frac{1}{\mu} Y_k \right)\) 直觉：从数据中减去低秩背景，剩下的做截断保留前景。
更新 $Y$（对偶/残差）： \(Y_{k+1} = Y_k + \mu (M - L_{k+1} - S_{k+1})\)
Candès 等人的理论证明给出了一个无需调参的通用公式。对于 $n_1 \times n_2$ 的矩阵，只要 $L$ 和 $S$ 满足不相干性（Incoherence）条件，最优 $\lambda$ 为： \(\lambda = \frac{1}{\sqrt{\max(n_1, n_2)}}\)
如果矩阵 $M$ 中只有一部分元素被观测到（记为集合 $\Omega$），其余位置缺失（如损坏的图像像素），我们能否恢复完整的 $X$？
\(\min_X \|X\|_* \quad \text{s.t. } P_\Omega(X) = P_\Omega(M)\) 其中 $P_\Omega(\cdot)$ 是采样算子，只保留 $\Omega$ 内的元素，其余置零。
算法依然基于 SVT，但在每一步迭代中，我们需要强制将观测位置的值“拉回”到真实值 $M_{ij}$，而对未观测位置则保留 SVT 的预测值。
应用：
Stable PCP (含有高斯噪声)： 现实中往往同时存在稀疏的大噪声和稠密的小噪声（高斯）。 模型：$\min_{L, S} |L|_* + \lambda |S|_1 + \frac{1}{2\sigma^2}|M - L - S|_F^2$ 这实际上是把等式约束变成了惩罚项。
Tensor RPCA (TRPCA)： 彩色视频本质上是三维张量（宽 $\times$ 高 $\times$ 时间）甚至四维张量。将张量展开（Unfold）成矩阵会破坏多维结构。基于 Tucker 分解或 t-SVD 的张量核范数方法能获得更好的效果。
Online / Incremental RPCA： 标准 RPCA 需要一次性处理整个视频矩阵，内存消耗巨大。在线算法（如 Grassmannian 子空间追踪）可以一帧一帧地更新背景模型，适合实时监控。
Q1: 奇异值与核范数 设矩阵 $A = \begin{bmatrix} 3 & 0 \ 0 & -4 \end{bmatrix}$。
Q2: RPCA 的物理意义 在视频背景建模中，为什么我们使用 $L_1$ 范数约束前景 $S$，而不是 $L_2$ 范数？如果使用 $L_2$ 范数（即 $\min |L|_* + \lambda |S|_F^2$），结果会有什么不同？
Q3: 秩的可加性？ $\text{rank}(A+B) = \text{rank}(A) + \text{rank}(B)$ 是否总是成立？这对 RPCA 分解有何启示？
Q4: 不可辨识性 (Incoherence) 考虑一个矩阵，它只有第一行第一列的元素为1，其余为0。
Q5: 随机化 SVD (Randomized SVD) 当矩阵规模达到 $10000 \times 10000$ 时，标准 SVD 不可行。请调研并简述 Randomized SVD 的基本思想：它是如何利用随机投影将大矩阵映射到小矩阵上计算奇异值的？这对精度有何影响？
现象：代码运行极慢，内存溢出。
原因：在 MATLAB/Python 中直接调用 svd(X) 会计算所有奇异值。而 RPCA 中 $L$ 的秩通常很低（例如 10-50），大部分奇异值都会被阈值 $\tau$ 归零。
对策：必须使用 svds (MATLAB) 或 scipy.sparse.linalg.svds (Python)，或者 Randomized SVD，仅计算前 $k$ 个最大的奇异值。如果发现第 $k$ 个奇异值大于 $\tau$，则增大 $k$ 重新计算。
现象：无论怎么调 $\lambda$，分离出的 $S$ 要么是全零，要么 $L$ 是全零。 原因：核范数和 $L_1$ 范数的量级取决于数据本身。如果像素值范围是 [0, 255]，而公式中的 $\lambda$ 是基于归一化假设推导的。 对策：务必先将图像/视频数据归一化到 [0, 1] 区间，再运行算法。
现象：试图用 RPCA 去除高斯白噪声。 原因：RPCA 的设计初衷是去除稀疏的大噪声（Outliers）。对于全图分布的高斯噪声，RPCA 的核范数会将其视为纹理的一部分保留在 $L$ 中，或者在 $S$ 中留下一堆杂乱的点。 对策：对于高斯噪声，请使用基于 Frobenius 范数的方法（如第4章的 Tikhonov 或第12.6节的 Stable PCP）。
现象：手持相机拍摄的视频，背景分离失败。 原因：RPCA 假设背景列向量是线性相关的。如果相机抖动，同一物理点在不同列中的位置不同，破坏了低秩性。 对策：必须先进行视频稳像 (Image Registration/Alignment)，将所有帧对齐后，再做 RPCA。或者使用由“RASL (Robust Alignment by Sparse and Low-rank decomposition)”提出的联合对齐与分解模型。