第10章 稀疏表示与字典学习：从 Lasso 到 K-SVD

在图像处理的早期历史中，研究人员主要依赖解析字典（Analytical Dictionaries）。例如，傅里叶变换假设图像由正弦波构成，小波变换假设图像由具有紧支集的振荡波构成。这些基底（Bases）是数学家预先定义好的“通用成衣”，虽然鲁棒，但往往无法捕捉特定数据集（如指纹、人脸、医学CT）中独特的复杂结构。

字典学习（Dictionary Learning, DL） 代表了从“模型驱动”向“数据驱动”的一次重要跨越。它的核心哲学是：与其使用固定的基底，不如让数据自己“学习”出一组最适合表达它的“字母表”（原子）。这种思想深受神经科学的启发——哺乳动物初级视觉皮层（V1区）的感受野便呈现出类似通过自然图像训练得到的稀疏边缘特征。

本章将深入探讨如何构建这样的系统。我们将从稀疏编码的几何直觉出发，推导经典的 K-SVD 算法，并将其扩展到处理海量数据的在线学习框架。

10.1 稀疏表示的两种视角：合成与分析

在数学上，我们如何定义“信号 $y$ 是简单的”？稀疏性给出了两个截然不同的答案。

10.1.1 合成模型 (Synthesis Model)

这是字典学习的主流框架。我们认为信号 $y \in \mathbb{R}^n$ 是由字典 $D \in \mathbb{R}^{n \times m}$ 中极少数几个原子（Atoms）加权求和而成的。

$$ y = D \alpha + \eta $$

  • 过完备性 (Overcompleteness)：通常 $m > n$（甚至 $m \gg n$）。这意味着字典里的原子比信号的维度多得多，这给了系统极大的灵活性去选择最合适的原子。
  • 稀疏性 (Sparsity)：$|\alpha|_0 \ll n$。尽管字典很大，但对于任意一个特定信号，只有寥寥几个系数是非零的。
  • 物理直觉：就像用乐高积木搭房子，积木库（字典）里有成千上万种形状，但搭一个特定的房子只需要几十块。

10.1.2 分析模型 (Analysis Model) / 共稀疏模型 (Cosparse Model)

这个视角鲜为人知但同样重要。它认为信号 $y$ 在经过某个分析算子 $\Omega \in \mathbb{R}^{p \times n}$ 投影后，其结果是稀疏的。 $$ |\Omega y|_0 \approx 0 $$

  • 物理直觉：信号“正交”于分析字典中的绝大多数行。
  • 例子：全变分（TV）模型就是典型的分析模型，其中 $\Omega$ 是微分算子。平滑图像经过微分后，大部分位置的值为0。

注：本章后续主要聚焦于合成模型，因为它是 K-SVD、图像去噪和压缩感知等领域的核心基础。

10.2 稀疏编码 (Sparse Coding)

在学习字典之前，我们必须先解决其子问题：稀疏编码。

问题定义：已知字典 $D$ 和观测信号 $y$，求最稀疏的系数 $\alpha$。

这是一个逆问题。由于 $D$ 是胖矩阵（Fat Matrix），方程 $y=D\alpha$ 有无穷多解。我们需要正则项来挑出最稀疏的那个。

10.2.1 几何直觉：为什么 $L_1$ 能诱导稀疏？

我们通常求解 Lasso 问题： $$ \min_\alpha \frac{1}{2}|y - D\alpha|_2^2 + \lambda |\alpha|_1 $$ 为什么使用 $L_1$（绝对值之和）而不是 $L_2$（平方和）？

  • $L_2$ 球（圆形/超球体）：各向同性。当目标函数的等高线接触到 $L_2$ 球时，切点通常在各个坐标轴都有分量（非稀疏）。
  • $L_1$ 球（菱形/多胞体）：具有尖锐的顶点（Corners）和棱边。这些顶点恰好位于坐标轴上。当等高线向外扩张接触 $L_1$ 球时，极大概率会先碰到顶点，从而使某些坐标精确为 0。
ASCII 几何演示：L1 vs L2

      |                   |
      |   /             \ | /
   ---+--/---           - + -  <- L2 (Circle) touches here
    / | / \             / | \     (x1!=0, x2!=0)
   /  |/   \           /  |  \
  *---+-----* x1      *---+---* x1 <- L1 (Diamond) touches here
   \  |    /           \  |  /        (x1!=0, x2=0) -> SPARSE!
    \ |   /             \ | /
      |  /                |
  Optimization          Constraint
   Direction             Geometry

10.2.2 贪婪算法：正交匹配追踪 (OMP)

当我们需要严格控制非零元素个数（$L_0$ 约束：$|\alpha|_0 \leq k$）时，OMP 是工业界的标准选择。它的核心是迭代式地寻找方向。

OMP 算法流程：

  1. 初始化：残差 $r = y$，支撑集 $S = \emptyset$。
  2. 原子选择 (Selection)：计算字典所有原子与当前残差的内积 $|D^T r|$，找出绝对值最大的原子 $d_{best}$。 - 直觉：谁跟残差长得最像，就选谁。
  3. 更新支撑集：$S = S \cup \{best\}$。
  4. 正交投影 (Projection)：这是“正交”二字的来源。求解最小二乘问题，更新所有已选原子的系数： $$ \alpha_S = (D_S^T D_S)^{-1} D_S^T y $$ 并更新残差 $r = y - D_S \alpha_S$。
  • 关键点：这一步保证了新残差 $r$ 与所有已选原子 $D_S$ 正交。这意味着我们彻底榨干了已选原子包含的所有信息，不会反复选择同一个特征。 5. 循环：重复 2-4 直到满足误差要求或达到稀疏度 $k$。

10.2.3 凸优化方法：Lasso / Basis Pursuit

当噪声较大或原子间相关性很高（Coherence high）时，贪婪算法容易选错。此时，求解 $L_1$ 凸优化问题更稳健。

  • ISTA (Iterative Shrinkage-Thresholding)： $$ \alpha_{k+1} = \mathcal{S}_{\lambda t} (\alpha_k - t D^T (D\alpha_k - y)) $$ 其中 $\mathcal{S}$ 是软阈值算子（Soft Thresholding）。

  • FISTA / ADMM：加速版本（详见第6、7章）。

Rule-of-Thumb (经验法则)

  • 实时应用/压缩：选 OMP。速度快，且非零元素个数固定，方便存储索引。
  • 高质量图像恢复：选 Lasso (L1)。它的恢复精度通常比 OMP 高 1-2 dB，且解更稳定。

10.3 字典学习模型的数学形式

现在我们进入本章核心：联合优化。 给定数据集 $Y = [y_1, ..., y_N]$，我们要同时找到字典 $D$ 和稀疏系数矩阵 $A = [\alpha_1, ..., \alpha_N]$。 $$ \min_{D, A} |Y - DA|_F^2 \quad \text{s.t.} \quad \forall i, |\alpha_i|_0 \leq k $$ 或者 $$ \min_{D, A} \frac{1}{2}|Y - DA|_F^2 + \lambda |A|_1 $$ 且必须施加约束：$|d_j|_2 = 1$ (原子归一化)。

为什么必须归一化？ 如果不归一化，算法会通过简单的“作弊”来降低目标函数：将 $D$ 放大 $100$ 倍，将 $A$ 缩小 $100$ 倍。此时重构项 $DA$ 不变，但正则项 $|A|_1$ 变得极小。这导致数值发散且失去物理意义。

10.4 K-SVD：稀疏域的 K-Means

K-SVD (Aharon et al., 2006) 是最经典的字典学习算法。它的名字致敬了 K-Means 聚类。

  • K-Means 可以看作一种极端的稀疏表示：每个信号 $y$ 只能用 1个 原子表示，且系数必须为 1。
  • K-SVD 放宽了限制：每个信号可以用 k个 原子线性组合。

K-SVD 采用 块坐标下降 (Block Coordinate Descent) 策略：

10.4.1 步骤 1：稀疏编码 (Sparse Coding Stage)

固定 $D$，更新 $A$。 这一步很简单：由于各样本相互独立，我们对每个 $y_i$ 并行运行 OMP，得到对应的 $\alpha_i$。

10.4.2 步骤 2：字典更新 (Dictionary Update Stage) —— 核心难点

固定 $A$，更新 $D$。 如果我们直接对 $D$ 求导解最小二乘，会导致 $D$ 的逆矩阵运算，且难以处理原子归一化约束。 K-SVD 的创新在于：一次只更新一个原子 $d_k$ 及其对应的非零系数。

假设我们要更新第 $k$ 个原子 $d_k$。 我们将重构误差矩阵 $Y - DA$ 拆解为： $$ |Y - DA|_F^2 = |Y - \sum_{j \neq k} d_j \alpha_{row, j} - \color{red}{d_k \alpha_{row, k}}|_F^2 = |E_k - \color{red}{d_k \alpha_{row, k}}|_F^2 $$ 其中 $E_k$ 是除去了第 $k$ 个原子贡献后的残差。我们希望找到新的 $d_k$ 和新的系数行 $\alpha_{row, k}$，使它们的乘积最接近 $E_k$。这就是一个 Rank-1 近似问题，通常用 SVD 求解。

但在 SVD 之前，有一个关键步骤！ 稀疏性要求 $\alpha_{row, k}$ 只能在特定的位置非零（即那些使用了原子 $d_k$ 的样本）。如果我们直接对 $E_k$ 做 SVD，得到的 $\alpha_{row, k}$ 可能会在所有位置都有值（破坏了稀疏模式）。

正确做法：

  1. 找出原子 $d_k$ 的使用集 (Active Set)：$\omega_k = \{i \mid \alpha_{row, k}(i) \neq 0\}$。
  2. 构建受限误差矩阵 (Restricted Error Matrix) $E_k^R$：只保留 $E_k$ 中属于 $\omega_k$ 的那些列。
  3. 对 $E_k^R$ 做 SVD：$E_k^R = U \Delta V^T$。
  4. 更新： - 新原子 $\tilde{d}_k = U$ 的第一列。 - 新系数 $\tilde{\alpha}_{row, k}$ 的非零部分 = $\Delta(1,1) \cdot V^T$ 的第一行。
ASCII 图解：K-SVD 更新逻辑

Error Matrix Ek (Fixed)      Atom k    Coeff Row k
[ |  |  |  |  | ]           [ | ]
[ |  |  |  |  | ]      ~=   [ | ]  *  [ 0, x, 0, x, x ]
[ |  |  |  |  | ]           [ | ]
      ^     ^  ^
      Indices using atom k (Active Set)

1. Extract columns from Ek corresponding to Active Set -> Ek_Restricted
2. SVD(Ek_Restricted) -> U, S, V
3. d_k_new = U(:, 1)          <- Atom shape updated to fit residual structure
4. coeff_new = S(1,1) * V(:,1)<- Coefficient values updated simultaneously

K-SVD 的强大之处：它不仅更新了字典的形状，还顺便调整了系数值。这比传统的“先定字典再定系数”收敛得快得多。

10.5 在线字典学习 (Online Dictionary Learning, ODL)

K-SVD 需要多次对整个数据集进行迭代，内存消耗巨大。当样本数 $N$ 达到百万级时（例如处理视频或海量 Patch），批处理不可行。

Mairal 等人 (2009) 提出了 ODL，这是现代大规模稀疏编码的基石。

核心思想：利用随机梯度下降（SGD）和充分统计量。 我们不需要存储所有数据，只需要存储两个累积矩阵：

  1. $H_t = \sum_{i=1}^t \alpha_i \alpha_i^T$ （Hessian 近似，记录原子间的相关性，大小 $m \times m$）
  2. $C_t = \sum_{i=1}^t y_i \alpha_i^T$ （记录数据与原子的相关性，大小 $n \times m$）

算法流程：

  1. 读入一个小批次 (Mini-batch) $Y_t$。
  2. 稀疏编码：用当前字典 $D_{t-1}$ 算出 $A_t$（Lasso/OMP）。

  3. 更新统计量： $H_t \leftarrow H_{t-1} + A_t A_t^T$ $C_t \leftarrow C_{t-1} + Y_t A_t^T$

  4. 更新字典：求解 $\min_D \frac{1}{2} \text{Tr}(D^T D H_t) - \text{Tr}(D^T C_t)$。 这可以通过块坐标下降逐列求解： $$ u_j = \frac{1}{H_t(j,j)} (c_j - D H_t(:, j)) + d_j $$ $$ d_j \leftarrow u_j / \max(1, |u_j|_2) $$ (注：这里巧妙地避开了 SVD，计算非常快)

10.6 进阶：约束与结构化字典

基础字典学习可以扩展以适应不同任务：

  1. 非负字典学习 (Non-negative DL)： 约束 $D \geq 0, \alpha \geq 0$。这实际上连接到了 NMF（第13章），但 DL 通常允许过完备，而 NMF 通常是低秩的。这在光谱分析中很有用。

  2. 判别式字典学习 (Discriminative DL)： 如果目的是分类（如人脸识别），我们希望同一类的信号由同一组原子表示。可以引入标签一致性 (Label Consistency) 正则项，强迫字典原子具有类别区分度。

  3. 多尺度/多层字典： 类似于深度学习，可以学习多层字典 $y \approx D_1 D_2 \alpha$。这被视为深度神经网络的一种数学解释（Deep Dictionary Learning）。

10.7 典型应用与工程流水线

10.7.1 图像去噪 (Denoising)

这是 DL 最成功的战场。 Pipeline:

  1. 分块 (Patch Extraction)：滑动窗口提取 $8\times8$ 或 $10\times10$ 的重叠块。
  2. 去直流 (DC Removal)：关键步骤！
    • 计算每个块的均值 $m_i$。
    • 令 $y_{patch} = y_{raw} - m_i$。
    • 字典应该只学习纹理，不学习亮度。
  3. 稀疏编码：对每个含噪 Patch $y_i$，求 $\alpha_i$ 使得 $|y_i - D\alpha_i|_2^2 \leq C \cdot \sigma^2$。
    • 这里的 $C$ 是常数（如 1.15），$\sigma$ 是噪声标准差。这是一个极其强大的先验：我们不拟合整个信号，只拟合比噪声方差稍大的那部分能量。 剩下的残差被认为是噪声丢弃。
  4. 重构：$\hat{y}_i = D\alpha_i + m_i$。
  5. 聚合 (Aggregation)：将重构的 Patch 放回图像大矩阵。对于重叠像素，取平均或加权平均。这能有效消除块效应并进一步降低方差。

10.7.2 图像修复 (Inpainting)

假设图像 $y$ 有部分像素丢失（由掩膜 $M$ 标记，丢失处为 0，存在处为 1）。 稀疏编码变体： $$ \min_\alpha |\alpha|_0 \quad \text{s.t.} \quad |M \odot (y - D\alpha)|_2^2 \leq \epsilon $$

  • 直觉：我们只在已知像素上计算误差，寻找能解释已知像素的最稀疏原子组合。
  • 填补：一旦找到 $\alpha$，完整的重构 $D\alpha$ 会自动“脑补”出缺失区域的纹理，因为字典原子本身是完整的。

10.8 本章小结

  1. 范式转变：从设计数学基底（小波）转向从数据中学习基底（K-SVD/ODL）。
  2. 稀疏性是关键：$L_1$ 范数（Lasso）和贪婪法（OMP）是求解系数的两把利器。
  3. K-SVD 机制：通过在受限误差矩阵上做 SVD，同时更新原子形状和系数值，实现了高效的字典学习。
  4. 工程细节：去直流（DC removal）和重叠块聚合（Aggregation）是去噪效果好的隐藏功臣。
  5. 局限性：基于 Patch 的方法丢失了全局结构，且 Patch 拉成向量破坏了 2D 几何相关性。这为下一章卷积稀疏编码 (CSC) 埋下了伏笔。

10.9 练习题

基础题

Q1: 冗余的代价 如果使用 $8\times8$ 的 Patch（维度 $n=64$），训练一个包含 $m=256$ 个原子的过完备字典。相比于正交 DCT 基（$m=64$），稀疏编码阶段的计算复杂度大概增加了多少倍？（假设使用 OMP，且稀疏度 $k$ 相同）。

提示

OMP 的每一步主要开销在于计算 $D^T r$。

答案

主要开销在于内积计算。正交基是 $n \times n$，过完备字典是 $n \times m$。复杂度近似线性正比于原子数量。因此复杂度约为 $256/64 = 4$ 倍。如果考虑求逆过程，实际开销可能更大，但主要瓶颈通常在匹配阶段。

Q2: 为什么不能用 $L_2$ 正则化系数？ 在字典学习中，如果我们把 Lasso 的 $\lambda |\alpha|_1$ 换成 $\lambda |\alpha|_2^2$（即岭回归 Ridge Regression），训练出来的字典会变成什么样？

提示

岭回归倾向于让所有系数都比较小，而不是让系数为0。

答案

字典会变成类似 PCA（主成分分析）的成分。因为 $L_2$ 不具有稀疏诱导性，每个信号都会由所有原子共同表示（$\alpha$ 是稠密的）。此时字典学习退化为寻找数据的主子空间，失去了“由少数零件组装”的语义解释能力。

挑战题

Q3: 字典的“死锁”与相干性 (Coherence) 如果初始化的字典中有两个原子非常相似 $d_i \approx d_j$。在 OMP 过程中会发生什么？在 K-SVD 更新中会发生什么？这是否是件坏事？

提示

OMP 挑选原子时看内积。如果 $d_i$ 被选中，残差去掉 $d_i$ 后，它与 $d_j$ 的相关性还大吗？

答案
  1. OMP：一旦 $d_i$ 被选中，残差会在 $d_i$ 方向正交化，由于 $d_j \approx d_i$，残差在 $d_j$ 方向的分量也会变得极小。因此 $d_j$ 很难被再次选中。
  2. K-SVD：由于 $d_j$ 很少被选中，它的 Active Set 几乎为空，导致它变成“死原子”无法更新。
  3. 坏处：这浪费了字典的容量。理想的字典应具有低相干性（Low Coherence，即原子间尽可能正交），以最大化表达能力。

Q4: 缺失数据下的 K-SVD 在做图像修复（Inpainting）时，我们不仅稀疏编码时有 Mask，更新字典 $D$ 时是否也需要考虑 Mask？如果我们直接用完整的 $D$ 拟合带 Mask 的数据，会学到什么？

提示

$Y$ 中有 0（缺失值）。

答案

必须考虑。如果在更新 $D$ 时不忽略缺失位置，字典原子会试图去拟合缺失处的 0 值（或者这种人工造成的边缘），导致原子本身出现黑洞或奇怪的伪影。正确的做法是在 K-SVD 的 SVD 分解步骤前，对误差矩阵 $E_k^R$ 也应用 Mask 权重，或者仅在观测数据上计算 SVD（加权 SVD）。

10.10 常见陷阱与错误 (Gotchas)

  1. 没有去均值 (DC Removal)：这是新手最容易犯的错误。如果不减去 Patch 均值，字典中的第一个原子往往会变成一个全白的方块（用来拟合亮度），其余原子则不得不包含大量的正负波瓣来抵消亮度。这极大地浪费了字典的稀疏表达能力。
    • Fix: 预处理减去均值，重构时加回均值。
  2. 原子未归一化：如果你自己写代码实现梯度下降解 DL，忘记每一步做 $d_k \leftarrow d_k / |d_k|_2$，系数 $\alpha$ 会迅速趋近于 0，字典 $D$ 会爆炸。
  3. K-SVD 更新顺序错误：在 K-SVD 中，必须串行更新原子。不能计算完所有原子的误差矩阵 $E_k$ 后再一次性并行 SVD 更新。因为更新 $d_1$ 后，残差矩阵已经变了，更新 $d_2$ 必须基于新的残差。并行更新会导致发散。
  4. OMP 的数值不稳定性：当求逆 $(D_S^T D_S)^{-1}$ 时，如果选中的原子高度相关，矩阵会接近奇异。
    • Fix: 使用 Cholesky 分解增量更新，或者在对角线加微小扰动（Ridge regularization）。
  5. 重叠步长太小：在去噪时，Patch 的步长（Stride）越小（即重叠越多），效果越好，但计算量是平方级增长。Stride=1 效果最好，Stride=BlockSize 效果最差（会有方块效应）。通常 Stride 选 2 或 3 是速度与质量的折中。