第七章：字典学习与稀疏编码的率失真

本章用率失真理论重新解读字典学习和稀疏编码：稀疏性对应"率"，重建误差对应"失真"。我们将理解过完备表示、稀疏正则化、K-SVD等算法的信息论本质，并探索其在图像处理中的应用。

学习目标：

• 理解字典学习的率失真框架
• 掌握$\ell_0$/$\ell_1$正则化与码率的对应
• 了解K-SVD、MOD等算法
• 建立稀疏编码与压缩的联系

7.1 稀疏表示基础

7.1.1 字典与稀疏编码

字典学习的目标：给定信号集合$\\{\mathbf{x}_i\\}$，找到字典$\mathbf{D} \in \mathbb{R}^{n \times m}$（$m > n$，过完备）和稀疏系数$\\{\mathbf{s}_i\\}$，使得

$$\mathbf{x}_i \approx \mathbf{D}\mathbf{s}_i$$ 其中$\mathbf{s}_i$是稀疏的（多数元素为0）。

术语：

• $\mathbf{D}$：字典（$m$个原子，每个$n$维）
• $\mathbf{d}_j$：第$j$个原子（字典的列）
• $\mathbf{s}_i$：信号$\mathbf{x}_i$的稀疏表示
• $|\mathbf{s}_i|_0$：非零元素个数（稀疏度）

示例：图像块$\mathbf{x} \in \mathbb{R}^{64}$（8×8块），字典$\mathbf{D} \in \mathbb{R}^{64 \times 256}$，稀疏表示$\mathbf{s} \in \mathbb{R}^{256}$且$|\mathbf{s}|_0 \leq 5$（最多5个非零系数）。

深入理解字典学习的本质：

字典学习可以看作是一种高度灵活的特征提取和表示方法。与传统的正交变换（如DCT、DFT）不同，字典学习有以下几个重要特点：

1. 过完备性的优势： - 当$m > n$时，字典提供的"基"比信号维度还多 - 这意味着每个信号可以有多种表示方式，我们可以选择最稀疏的那个 - 类比：用一个包含256个单词的词典来表达64维的概念，远比只有64个单词更灵活

2. 表示的多样性： 假设我们有一个8×8图像块（64维），考虑三种不同类型的结构：

类型A：水平边缘    类型B：垂直边缘    类型C：对角纹理
════════           ║║║║║║║║           ╱╱╱╱╱╱╱╱
════════           ║║║║║║║║           ╱╱╱╱╱╱╱╱
────────           ║║║║║║║║           ╱╱╱╱╱╱╱╱
────────           ║║║║║║║║           ╱╱╱╱╱╱╱╱

一个过完备字典可以同时包含：

• 水平方向的原子：$\mathbf{d}_1, \mathbf{d}_2, ...$
• 垂直方向的原子：$\mathbf{d}_{20}, \mathbf{d}_{21}, ...$
• 对角方向的原子：$\mathbf{d}_{40}, \mathbf{d}_{41}, ...$
• 以及各种角度和频率的原子

3. 稀疏性的数学直觉： 稀疏表示意味着： $$\mathbf{s} = [0, 0, ..., s_5, 0, ..., 0, s_{23}, 0, ..., s_{47}, 0, ..., 0]^T$$ 仅有少数几个非零元素（如$s_5, s_{23}, s_{47}$）。这三个系数对应的字典原子的线性组合就能很好地重建原信号： $$\mathbf{x} \approx s_5 \mathbf{d}_5 + s_{23} \mathbf{d}_{23} + s_{47} \mathbf{d}_{47}$$ 具体数值例子：

考虑一个简化的2D例子（便于可视化）。假设信号$\mathbf{x} \in \mathbb{R}^2$，字典$\mathbf{D} \in \mathbb{R}^{2 \times 4}$（4个原子，每个2维）： $$\mathbf{D} = \begin{bmatrix} 1 & 0 & 0.7 & 0.7 \\ 0 & 1 & 0.7 & -0.7 \end{bmatrix}$$ 这4个原子对应方向：

• $\mathbf{d}_1 = [1, 0]^T$：水平方向
• $\mathbf{d}_2 = [0, 1]^T$：垂直方向
• $\mathbf{d}_3 = [0.7, 0.7]^T$：45°方向
• $\mathbf{d}_4 = [0.7, -0.7]^T$：-45°方向

现在给定信号$\mathbf{x} = [3, 3]^T$，有多种表示：

• 正交基表示（仅用$\mathbf{d}_1, \mathbf{d}_2$）：$\mathbf{s} = [3, 3, 0, 0]^T$，$|\mathbf{s}|_0 = 2$
• 稀疏表示（仅用$\mathbf{d}_3$）：$\mathbf{s} \approx [0, 0, 4.24, 0]^T$，$|\mathbf{s}|_0 = 1$

第二种表示更稀疏！这就是过完备字典的威力：它可以找到更简洁的表示。

与码本量化的类比：

字典学习类似于向量量化（VQ），但有重要区别：

| 特性 | 向量量化（VQ） | 稀疏编码 |

Rule of thumb：对于自然图像的8×8块，字典大小通常选择$m = 256$到$m = 512$（是信号维度64的4到8倍）。稀疏度通常设置为$k = 3$到$k = 10$，在表示能力和码率之间取得良好平衡。更大的字典提供更好的表示能力，但计算成本也更高，且容易过拟合。

7.1.2 过完备表示

为什么过完备（$m > n$）？

正交基（如DCT、FFT，$m = n$）：每个信号有唯一表示，但可能不稀疏。

过完备字典（$m > n$）：

• 表示不唯一，但可以选择最稀疏的
• 更灵活，适应信号的多样结构
• 类比：用256个"单词"表达64维"句子"，比用64个更灵活

字典 vs 变换：

| 特性 | 正交变换（如DCT） | 过完备字典 |

深入理解过完备性：

过完备表示的核心优势在于"冗余度带来灵活性"。从线性代数的角度看：

1. 正交基的限制： - 当$m = n$且字典是正交基时（如DCT），表示是唯一的：$\mathbf{s} = \mathbf{D}^{-1}\mathbf{x} = \mathbf{D}^T\mathbf{x}$ - 每个信号只有一种表示方式，无法根据稀疏性进行优化 - 例如，DCT将图像块分解为64个频率分量，但无法选择"只用5个"而保持低失真——你必须接受DCT给出的那个特定分解

2. 过完备的自由度： - 当$m > n$时，系统是欠定的（under-determined） - 存在无穷多个解满足$\mathbf{x} = \mathbf{D}\mathbf{s}$（零空间非空） - 我们可以在这些解中选择最稀疏的：$\min_{\mathbf{s}} |\mathbf{s}|_0 \quad \text{s.t.} \quad \mathbf{x} = \mathbf{D}\mathbf{s}$

几何直觉：

在2D空间中考虑一个过完备字典（4个原子）：

         d₂ ↑
            |    / d₃ (45°)
            |  /
            |/
  d₄ ──────●────── d₁
     (-45°) |
            |

给定目标点$\mathbf{x}$，可以用不同的原子组合到达：

• 路径1：$\mathbf{x} = s_1 \mathbf{d}_1 + s_2 \mathbf{d}_2$（2个原子）
• 路径2：$\mathbf{x} = s_3 \mathbf{d}_3$（1个原子，如果$\mathbf{x}$在45°方向）
• 路径3：$\mathbf{x} = s_1 \mathbf{d}_1 + s_3 \mathbf{d}_3 + s_4 \mathbf{d}_4$（3个原子）

过完备性让我们选择最短的路径（最少的原子）。

数值对比例子：

考虑一个8×8图像块（64维），分别用DCT和过完备字典表示：

场景A：平滑区域

原始块（均匀灰度值100）：
100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100
...

• DCT表示：DC分量很大，其他63个分量接近0，$|\mathbf{s}|_0 \approx 1$（已经很稀疏）
• 过完备字典：类似，$|\mathbf{s}|_0 \approx 1$（没有明显优势）

场景B：单一方向边缘

原始块（垂直边缘）：
0   0   0   0  255 255 255 255
0   0   0   0  255 255 255 255
...

• DCT表示：需要多个频率分量组合（DC + 多个AC），$|\mathbf{s}|_0 \approx 10$
• 过完备字典：如果有专门的"垂直边缘"原子，$|\mathbf{s}|_0 \approx 2$-$3$（更稀疏！）

场景C：复杂纹理

原始块（对角纹理）：
随机纹理模式...

• DCT表示：需要许多分量，$|\mathbf{s}|_0 \approx 30$
• 过完备字典（如果学习了该纹理模式）：$|\mathbf{s}|_0 \approx 5$-$10$

过完备度的选择：

定义过完备因子 $r = m/n$：

| $r$ | 特性 | 适用场景 |

与率失真的联系：

过完备性提供了一个额外的自由度来优化率失真权衡：

• $m = n$（正交基）：率失真曲线由变换本身决定（如DCT的率失真曲线）
• $m > n$（过完备）：可以通过选择不同的原子组合，在率失真曲线上移动到更优的点

用水注入（water-filling）类比：

• 正交基：水的分配由固定的"容器形状"（方差）决定
• 过完备字典：你可以选择不同的"容器"（原子组合），找到最优的水分配

Rule of thumb：字典大小$m$通常是信号维度$n$的2-8倍。太小则不够灵活，太大则计算复杂且易过拟合。对于8×8图像块（$n=64$），推荐$m=256$（$r=4$）作为起点。如果计算资源充足且训练数据丰富，可以尝试$m=512$（$r=8$）。

7.2 稀疏编码的率失真解释

7.2.1 稀疏性 ↔ 率

核心观察：稀疏系数需要的码率很低。

假设$|\mathbf{s}|_0 = k$（$k$个非零系数），编码需要：

1. 位置信息：哪$k$个系数非零 → $\log \binom{m}{k} \approx k \log \frac{m}{k}$比特
2. 数值信息：$k$个系数的值 → $k \cdot b$比特（每个$b$比特量化）

总码率： $$R \approx k \left(\log \frac{m}{k} + b\right)$$ 关键：$R$随稀疏度$k$线性增长。$k$越小，码率越低。因此：

稀疏度 $|\mathbf{s}|_0$ 对应 码率 $R$

深入理解码率计算：

上述公式的两个组成部分有不同的信息论含义：

1. 位置信息的编码： - 从$m$个可能位置中选择$k$个，共有$\binom{m}{k} = \frac{m!}{k!(m-k)!}$种可能 - 需要$\log_2 \binom{m}{k}$比特来编码这个选择 - 使用Stirling近似：$\log n! \approx n\log n - n$，可得 $$\log \binom{m}{k} \approx k\log\frac{m}{k} + (m-k)\log\frac{m}{m-k}$$

• 当$k \ll m$时，简化为$\log \binom{m}{k} \approx k\log\frac{m}{k}$

2. 数值信息的编码： - 每个非零系数需要量化和编码 - 如果使用均匀量化（$b$比特），直接是$kb$比特 - 如果使用熵编码（利用系数分布），实际码率可能更低

具体数值例子：

考虑8×8图像块的稀疏表示（$n=64$, $m=256$, $k=5$, $b=8$）：

位置信息： $$\log_2 \binom{256}{5} = \log_2 \frac{256 \times 255 \times 254 \times 253 \times 252}{5!} \approx \log_2(8.77 \times 10^{11}) \approx 39.7 \text{ 比特}$$ 或使用近似公式： $$k\log\frac{m}{k} = 5\log_2\frac{256}{5} \approx 5 \times 5.68 = 28.4 \text{ 比特}$$ 数值信息： $$k \cdot b = 5 \times 8 = 40 \text{ 比特}$$ 总码率： $$R \approx 28.4 + 40 = 68.4 \text{ 比特}$$ 每像素码率：$68.4 / 64 \approx 1.07$ 比特/像素

与DCT的对比：

如果用DCT，保留前5个系数（固定位置，无需位置信息）： $$R_{\text{DCT}} = 5 \times 8 = 40 \text{ 比特} \approx 0.625 \text{ 比特/像素}$$ 稀疏编码的位置信息带来了额外开销！但如果字典学习得当，失真可能更低。

码率的参数依赖性：

让我们分析不同参数下的码率：

| $k$ | $m$ | 位置信息 (bits) | 数值信息 (bits, $b=8$) | 总码率 (bits) | bpp |

观察：

• 码率随$k$近似线性增长（位置信息是$O(k\log m)$，数值信息是$O(k)$）
• 字典越大（$m$越大），位置信息开销越大
• 非常稀疏（$k=1$）时，稀疏编码优于DCT
• 中等稀疏（$k=5$-$10$）时，码率高于DCT，但失真可能更低

熵编码的改进：

上述计算假设均匀分布。实际中，可以利用统计特性：

1. 位置的先验分布： - 某些原子组合更常见（如"平滑背景" + "边缘"） - 可以用可变长编码（如Huffman）减少位置信息

2. 系数值的分布： - 非零系数通常服从Laplace或广义高斯分布 - 熵编码可以将$kb$比特降低到$k \cdot H(\mathbf{S})$比特（$H(\mathbf{S})$是系数熵）

实际系统的码率：

在实际的稀疏编码压缩系统中，码率通常还包括：

• 字典本身的存储/传输（如果字典需要发送给解码器）
• 元数据（图像大小、块边界等）
• 误差校正码

对于字典共享（编码器和解码器使用相同的预训练字典），字典传输可以忽略。

Rule of thumb：对于实际应用，稀疏编码的有效码率约为$R \approx k(\log_2 m + b - 2)$比特/块（考虑熵编码的2比特左右增益）。要达到比DCT更好的率失真性能，学习的字典需要在相同稀疏度$k$下提供至少2-3 dB的PSNR增益，以补偿位置信息的码率开销。

7.2.2 重建误差 ↔ 失真

重建信号$\hat{\mathbf{x}} = \mathbf{D}\mathbf{s}$与原信号$\mathbf{x}$的差异： $$D = |\mathbf{x} - \mathbf{D}\mathbf{s}|^2$$ 这正是失真（平方误差）。

深入理解重建误差：

稀疏编码中的失真来自两个来源：

1. 稀疏近似误差： - 即使字典是完美的，限制稀疏度$|\mathbf{s}|_0 \leq k$也会引入误差 - 如果允许无限稀疏度（$k \to n$或更大），且字典跨越整个空间，则可以无损重建 - 但实际中，$k$很小（如$k=5$），只能近似重建

2. 字典次优性： - 学习的字典不一定是最优的（局部最优、训练数据有限等） - 字典可能无法完美表示测试数据

失真的分解：

可以将总失真分解为： $$D_{\text{total}} = \underbrace{\min_{\mathbf{s}} |\mathbf{x} - \mathbf{D}\mathbf{s}|^2}_{\text{字典表示能力}} + \underbrace{|\mathbf{x} - \mathbf{D}\mathbf{s}^*|^2 - \min_{\mathbf{s}} |\mathbf{x} - \mathbf{D}\mathbf{s}|^2}_{\text{稀疏约束损失}}$$ 其中$\mathbf{s}^*$是在稀疏约束下的最优解（$|\mathbf{s}^*|_0 \leq k$）。

数值例子：

考虑一个64维信号$\mathbf{x}$（8×8图像块），使用256原子的字典，稀疏度$k=5$：

场景1：平滑块

原始块（均匀灰度）：
150 150 150 ... 150
150 150 150 ... 150
...

• 只需1个"平滑"原子即可完美重建
• 失真：$D \approx 0$（或量化误差）
• 实际上$k=1$就足够，$k=5$是浪费

场景2：简单边缘

原始块（水平边缘）：
100 100 100 ... 100
100 100 100 ... 100
200 200 200 ... 200
200 200 200 ... 200

• 需要2-3个原子（"平滑背景" + "边缘方向" + "边缘位置"）
• 使用$k=5$，失真：$D \approx 50$（MSE）
• 相当于PSNR $\approx 10\log_{10}(255^2/50) \approx 37$ dB

场景3：复杂纹理

原始块（高频纹理）：
50 200 60 180 ...
190 70 210 55 ...
...

• 需要许多原子才能好好重建
• 使用$k=5$，失真：$D \approx 300$（MSE）
• PSNR $\approx 10\log_{10}(255^2/300) \approx 35$ dB
• 如果允许$k=20$，失真可能降到$D \approx 50$（PSNR 37 dB）

失真与稀疏度的权衡曲线：

对于给定信号和字典，可以绘制$D$-$k$曲线：

失真 D
  500 |*
      |
  300 | *
      |
  100 |    *
      |      *
   10 |         *___
    0 |________________→ 稀疏度 k
      0   5  10  15  20

观察：

• $k$很小时，失真下降很快（"肘部"效应）
• $k$继续增加，失真下降变缓
• 存在一个"最佳"$k$：继续增加$k$带来的失真减少不足以弥补码率增加

与率失真理论的比较：

| 特性 | 率失真理论 | 稀疏编码 |

稀疏编码的率失真性能受限于字典。最好的字典学习算法试图逼近理论$R(D)$函数，但通常会有差距。

Rule of thumb：对于自然图像块，稀疏度与失真的关系大致为：$D \propto k^{-\alpha}$，其中$\alpha \approx 1.5$-$2$（幂律衰减）。这意味着失真随稀疏度快速下降，但边际收益递减。实际选择$k$时，应在率失真曲线的"肘部"附近，通常对应于信号能量的90%-95%被捕获。

7.2.3 稀疏编码的率失真优化

稀疏编码可以重新表述为率失真问题： $$\min_{\mathbf{s}} \left[ \underbrace{|\mathbf{x} - \mathbf{D}\mathbf{s}|^2}_{\text{失真 } D} + \underbrace{\lambda |\mathbf{s}|_0}_{\text{率 } R} \right]$$ 其中$\lambda$是拉格朗日乘子，权衡失真和码率（稀疏度）。

深层理解：从信息论到稀疏表示

这个优化问题的形式与第二章的率失真拉格朗日形式完全一致： $$\min_{p(\hat{x}|x)} [I(X; \hat{X}) + \beta \mathbb{E}[d(X, \hat{X})]]$$ 两者的对应关系：

| 率失真理论 | 稀疏编码 |

关键区别：

1. 确定性 vs 概率性：稀疏编码是确定性映射（给定$\mathbf{x}$，找到唯一的$\mathbf{s}$），而率失真理论允许随机编码（$p(\hat{x}|x)$是分布）。这对应于$\beta \to \infty$的极限情况。

2. 字典约束：稀疏编码受限于固定字典$\mathbf{D}$（或学习的字典），而率失真理论在所有可能的编码方案上优化。

与率失真函数的联系：

对于给定字典$\mathbf{D}$，可以定义"字典约束的率失真函数"： $$R_{\mathbf{D}}(D) = \min_{\mathbf{s}: |\mathbf{x}-\mathbf{D}\mathbf{s}|^2 \leq D} |\mathbf{s}|_0$$ 这个函数刻画了在字典$\mathbf{D}$的限制下，失真$D$所需的最小稀疏度（码率）。

性质：

• $R_{\mathbf{D}}(D)$关于$D$单调递减（允许更大失真 → 更稀疏的表示）
• $R_{\mathbf{D}}(0)$：无损重建所需的稀疏度（如果字典跨越整个空间，$R_{\mathbf{D}}(0) = n$）
• $R_{\mathbf{D}}(D)$不一定凸（因为$\ell_0$范数不凸）

字典学习的目标：

字典学习不仅优化表示$\mathbf{s}$，还优化字典$\mathbf{D}$，目标是最小化整体失真在给定稀疏度约束下： $$\min_{\mathbf{D}, \{\mathbf{s}_i\}} \sum_i |\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2 \quad \text{subject to } |\mathbf{s}_i|_0 \leq k, \, \forall i$$ 或等价的拉格朗日形式： $$\min_{\mathbf{D}, \{\mathbf{s}_i\}} \sum_i \left[|\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2 + \lambda |\mathbf{s}_i|_0\right]$$ 这相当于在所有可能的字典中寻找率失真性能最优的那个。

实际意义：

学习的字典$\mathbf{D}$适应数据的统计特性，类似于KLT（主成分分析）适应数据的协方差矩阵。但字典学习更灵活：

• KLT只能学习线性子空间
• 字典学习可以学习多个子空间的并集（union of subspaces），适应分段线性或多模态数据

与变换编码的比较：

| 特性 | 变换编码（如DCT） | 稀疏编码 |

数值例子：

假设8×8图像块（$n=64$），字典大小$m=256$，稀疏度$k=5$。

• 码率估计：
• 位置信息：$\log_2 \binom{256}{5} \approx 5 \log_2(256/5) \approx 27$ 比特
• 数值信息（每个系数8比特）：$5 \times 8 = 40$ 比特

• 总计：约67比特/块 ≈ 1.05 比特/像素

• 对比DCT：8×8 DCT，保留前5个系数，每个8比特 = 40比特/块 ≈ 0.625比特/像素

DCT更紧凑（固定字典，不需要位置信息），但稀疏编码可能通过学习的字典达到更低失真。

Rule of thumb：稀疏编码就是在固定字典下的率失真编码。字典学习则是同时优化字典$\mathbf{D}$和表示$\mathbf{s}$，达到更好的率失真性能。对于特定类型的信号（如纹理、边缘），学习的字典可以比固定变换（如DCT）提供5-15%的率失真增益。

7.2.4 $\ell_0$ vs $\ell_1$正则化

$\ell_0$范数：$|\mathbf{s}|_0 = |\{i: s_i \neq 0\}|$，真正的稀疏度

问题：$\ell_0$优化是NP难问题（组合优化）

$\ell_1$松弛：用$|\mathbf{s}|_1 = \sum_i |s_i|$替代$|\mathbf{s}|_0$ $$\min_{\mathbf{s}} |\mathbf{x} - \mathbf{D}\mathbf{s}|^2 + \lambda |\mathbf{s}|_1$$ 优势：$\ell_1$优化是凸问题，有高效算法（LASSO、ISTA、FISTA）

与率失真的联系：$\ell_1$正则化仍对应率约束，但度量方式不同（系数幅度和 vs 非零个数）。可以证明在某些条件下，$\ell_1$和$\ell_0$给出相似的稀疏解。

率的新解释：

• $\ell_0$：位置 + 值的编码
• $\ell_1$：类似于熵编码（小系数用短码字，大系数用长码字）

深入理解 $\ell_0$ 与 $\ell_1$ 的差异：

$\ell_0$和$\ell_1$范数在几何和优化上有本质不同：

几何直觉（2维例子）：

考虑$\mathbf{s} \in \mathbb{R}^2$，约束$|\mathbf{s}|_p \leq 1$的形状：

$\ell\_0$ "范数"（$k \leq 1$）:    $\ell\_1$ 范数:          $\ell\_2$ 范数:
    s₂                             s₂                      s₂
    |                              |                       |
  1 +---*                        1 +                     1 +
    |   |                          |\                      / \
----+---+---- s₁              -----+-\------- s₁      ----+---+---- s₁
  -1|   |  1                    -1 |  \  1              -1 |   |  1
    *---+                          +   \                   \   /
    |                              |    \                   \ /
                                                            +

• $\ell_0$：允许坐标轴上的任意点（稀疏性）
• $\ell_1$：菱形，在坐标轴上有"尖角"（促进稀疏）
• $\ell_2$：圆形，光滑，不促进稀疏

当等值线（误差项$|\mathbf{x} - \mathbf{D}\mathbf{s}|^2$的等高线）与约束区域相切时：

• $\ell_1$约束的尖角使得切点容易落在坐标轴上 → 稀疏解
• $\ell_2$约束的圆形使得切点通常不在坐标轴上 → 非稀疏解

等价性条件：

在什么情况下$\ell_1$和$\ell_0$给出相同的解？

定理（RIP - Restricted Isometry Property）：如果字典$\mathbf{D}$满足$k$-RIP，即对所有$k$-稀疏向量$\mathbf{s}$，有 $$(1-\delta_k)|\mathbf{s}|^2 \leq |\mathbf{D}\mathbf{s}|^2 \leq (1+\delta_k)|\mathbf{s}|^2$$ 其中$\delta_k < 1$，则$\ell_1$优化的解与$\ell_0$的解相同（或非常接近）。

直觉：RIP要求字典的任意$k$列近似正交。这样，$\ell_1$松弛不会引入太多误差。

数值对比：

考虑一个简单的例子：$\mathbf{x} = [3, 1]^T$，字典$\mathbf{D} = \mathbf{I}_2$（单位矩阵），$\lambda = 1$。

$\ell_0$优化： $$\min_{\mathbf{s}} |[3,1]^T - \mathbf{s}|^2 + \lambda |\mathbf{s}|_0$$ 尝试不同的稀疏度：

• $k=0$：$\mathbf{s} = [0, 0]^T$，目标函数 = $10 + 0 = 10$
• $k=1$：$\mathbf{s} = [3, 0]^T$或$[0, 1]^T$，目标函数 = $1 + 1 = 2$或$9 + 1 = 10$
• $k=2$：$\mathbf{s} = [3, 1]^T$，目标函数 = $0 + 2 = 2$

最优解：$\mathbf{s}^*_{\ell_0} = [3, 0]^T$（稀疏度1）

$\ell_1$优化： $$\min_{\mathbf{s}} |[3,1]^T - \mathbf{s}|^2 + \lambda |\mathbf{s}|_1$$ 这是LASSO问题，解为： $$s_i = \text{sign}(x_i) \max(|x_i| - \lambda/2, 0)$$ 对于$\lambda = 1$： $$\mathbf{s}^*_{\ell_1} = [2.5, 0.5]^T$$ 这个解不稀疏！如果增大$\lambda$到$\lambda = 2$： $$\mathbf{s}^*_{\ell_1} = [2, 0]^T$$ 仍然不完全一致。只有当$\lambda$非常大时，第二个分量才会被压缩到0。

实际应用中的选择：

| 特性 | $\ell_0$ 正则化 | $\ell_1$ 正则化 |

从率失真角度的解释：

$\ell_1$正则化对应于一种特殊的码率度量： $$R_{\ell_1}(\mathbf{s}) \propto |\mathbf{s}|_1 = \sum_i |s_i|$$ 这可以理解为：

• 系数越大，需要越多的比特来编码（更高的精度）
• 类似于"加权"的稀疏度：大系数"贡献"更多的码率

实际中，真实的码率更接近于： $$R(\mathbf{s}) \approx |\mathbf{s}|_0 \cdot \log m + \sum_i H(s_i)$$ 其中$H(s_i)$是系数的熵（与$|s_i|$相关，但不完全成比例）。

$\ell_1$范数是这个真实码率的一个凸近似，便于优化。

Rule of thumb：

• 计算资源受限：使用$\ell_1$正则化（LASSO），更快更稳定
• 码率精确控制：使用$\ell_0$正则化（OMP），直接指定$k$
• RIP条件满足（随机字典、测量矩阵）：$\ell_1$和$\ell_0$效果相近，优先选$\ell_1$
• 实际压缩系统：混合策略——用$\ell_1$初始化，再用$\ell_0$精修

7.3 字典学习算法

7.3.1 问题表述

字典学习同时优化字典和稀疏表示： $$\min_{\mathbf{D}, \\{\mathbf{s}_i\\}} \sum_{i=1}^N \left[ |\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2 + \lambda |\mathbf{s}_i|_0 \right]$$ 约束：$|\mathbf{d}_j|_2 = 1$（字典原子归一化，避免尺度模糊）

这是双非凸优化：对$\mathbf{D}$非凸，对$\mathbf{s}_i$非凸（$\ell_0$）。

7.3.2 K-SVD算法

K-SVD（Aharon et al., 2006）是经典的字典学习算法，交替优化：

迭代（$t = 0, 1, 2, ...$）：

1. 稀疏编码步：固定$\mathbf{D}^{(t)}$，对每个$\mathbf{x}_i$求稀疏系数 $$\mathbf{s}_i^{(t+1)} = \arg\min_{\mathbf{s}} |\mathbf{x}_i - \mathbf{D}^{(t)}\mathbf{s}|^2 \quad \text{s.t.} \quad |\mathbf{s}|_0 \leq k$$ 使用OMP（Orthogonal Matching Pursuit）等贪心算法求解

2. 字典更新步：固定$\\{\mathbf{s}_i^{(t+1)}\\}$，逐个更新字典原子

对第$j$个原子$\mathbf{d}_j$：

• 找使用$\mathbf{d}_j$的所有信号：$\Omega_j = \\{i: s_{i,j} \neq 0\\}$
• 计算误差矩阵：$\mathbf{E}_j = [\mathbf{x}_i - \sum_{k \neq j} s_{i,k}\mathbf{d}_k]_{i \in \Omega_j}$
• SVD更新：$\mathbf{d}_j \leftarrow$ 第一左奇异向量，$\\{s_{i,j}\\}_{i \in \Omega_j} \leftarrow$ 第一奇异值 × 右奇异向量

3. 收敛检查：重复直到目标函数变化小于阈值

与率失真的联系：

• 稀疏编码步：固定"测试信道"（字典），优化表示 → 类似固定码本的量化
• 字典更新步：固定表示，优化"码本" → 类似Lloyd算法的质心更新

深入理解 K-SVD 的工作机制：

K-SVD的核心思想是坐标下降（coordinate descent）：轮流优化稀疏系数和字典原子，每次保持其他变量固定。

稀疏编码步的详细过程（OMP算法）：

对于给定的信号$\mathbf{x}_i$和字典$\mathbf{D}$，OMP贪心地选择原子：

初始化: 残差 r = x_i, 稀疏系数 s = 0, 已选索引集 Λ = ∅

For t = 1 to k:

  1. 选择与残差最相关的原子: j* = argmax_j |⟨r, d_j⟩|
  2. 更新索引集: Λ ← Λ ∪ {j*}
  3. 最小二乘更新系数: s_Λ = (D_Λ^T D_Λ)^(-1) D_Λ^T x_i
  4. 更新残差: r ← x_i - D_Λ s_Λ

输出: s（只有Λ中的索引非零）

数值例子：

假设$\mathbf{x} = [5, 5, 0]^T$，字典$\mathbf{D} \in \mathbb{R}^{3 \times 4}$： $$\mathbf{D} = \begin{bmatrix} 1 & 0 & 0.7 & 0.6 \\ 0 & 1 & 0.7 & 0 \\ 0 & 0 & 0 & 0.8 \end{bmatrix}$$ （原子已归一化）

OMP过程（$k=2$）：

迭代1：

• 残差：$\mathbf{r} = [5, 5, 0]^T$
• 内积：$\langle \mathbf{r}, \mathbf{d}_1 \rangle = 5$, $\langle \mathbf{r}, \mathbf{d}_2 \rangle = 5$, $\langle \mathbf{r}, \mathbf{d}_3 \rangle = 7$, $\langle \mathbf{r}, \mathbf{d}_4 \rangle = 3$
• 选择：$j^* = 3$（最大内积）
• 更新：$s_3 = 7/(|\mathbf{d}_3|^2) = 7$，$\mathbf{r} \leftarrow \mathbf{x} - 7\mathbf{d}_3 = [0.1, 0.1, 0]^T$

迭代2：

• 残差：$\mathbf{r} = [0.1, 0.1, 0]^T$
• 内积：$\langle \mathbf{r}, \mathbf{d}_1 \rangle = 0.1$, $\langle \mathbf{r}, \mathbf{d}_2 \rangle = 0.1$, ...
• 选择：$j^* = 1$或$2$（假设选1）
• 最小二乘更新（使用$\mathbf{d}_1, \mathbf{d}_3$）：...

最终：$\mathbf{s} \approx [0.2, 0, 7, 0]^T$，$|\mathbf{s}|_0 = 2$

字典更新步的 SVD 机制：

K-SVD的巧妙之处在于如何更新字典原子$\mathbf{d}_j$：

对于第$j$个原子，我们希望最小化： $$\sum_{i \in \Omega_j} |\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2$$ 其中$\Omega_j = \{i: s_{i,j} \neq 0\}$是使用第$j$个原子的信号集合。

将重建误差改写： $$\sum_{i \in \Omega_j} \left|\mathbf{x}_i - \sum_{l=1}^m s_{i,l}\mathbf{d}_l\right|^2 = \sum_{i \in \Omega_j} \left|\underbrace{\left(\mathbf{x}_i - \sum_{l \neq j} s_{i,l}\mathbf{d}_l\right)}_{\mathbf{e}_i} - s_{i,j}\mathbf{d}_j\right|^2$$ 定义误差矩阵$\mathbf{E}_j = [\mathbf{e}_{i_1}, \mathbf{e}_{i_2}, ...]$（列是误差向量），以及系数行向量$\mathbf{s}_j^{\text{row}} = [s_{i_1,j}, s_{i_2,j}, ...]$。

目标变为： $$\min_{\mathbf{d}_j, \mathbf{s}_j^{\text{row}}} |\mathbf{E}_j - \mathbf{d}_j (\mathbf{s}_j^{\text{row}})^T|_F^2 \quad \text{s.t.} \quad |\mathbf{d}_j| = 1$$ 这是秩1近似问题！SVD给出最优解： $$\mathbf{E}_j = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T$$ 最优的$\mathbf{d}_j$和$\mathbf{s}_j^{\text{row}}$分别是：

• $\mathbf{d}_j = \mathbf{u}_1$（第一左奇异向量）
• $\mathbf{s}_j^{\text{row}} = \sigma_1 \mathbf{v}_1^T$（第一奇异值 × 第一右奇异向量）

与 Lloyd 算法（K-means）的类比：

| 特性 | Lloyd (K-means) | K-SVD |

K-SVD可以看作是K-means的线性组合泛化。

收敛性分析：

K-SVD的收敛性质：

1. 目标函数单调递减：每一步（稀疏编码 + 字典更新）都减少目标函数
2. 收敛到局部最优：由于非凸性，不保证全局最优
3. 收敛速度：通常10-50次迭代，取决于初始化质量

数值收敛例子：

假设训练1000个8×8图像块，字典大小256，稀疏度$k=5$：

| 迭代次数 | 平均重建误差（MSE） | 平均稀疏度 |

观察：误差快速下降，然后趋于平稳。通常20-50次迭代已经足够。

计算复杂度：

对于$N$个信号，每次迭代：

• 稀疏编码：$N$个OMP，每个$O(mnk)$ → 总计$O(Nmnk)$
• 字典更新：$m$个SVD，每个$O(n |\Omega_j|^2)$ → 总计$O(mn^2 N)$（假设$|\Omega_j| \approx N/m$）

总复杂度：$O(T \cdot N \cdot m \cdot \max(nk, n^2))$，其中$T$是迭代次数。

对于$N=10000$, $n=64$, $m=256$, $k=5$, $T=20$： 约$20 \times 10000 \times 256 \times (64 \times 5) \approx 1.6 \times 10^{10}$次操作（数分钟到数小时，取决于硬件）。

Rule of thumb：K-SVD通常10-50次迭代收敛。字典大小$m$和稀疏度$k$是关键超参数：$m$越大、$k$越小，码率越低但计算越复杂。初始化很重要：用DCT或从训练数据随机采样作为初始字典，比随机高斯初始化收敛更快且质量更好。每5-10次迭代检查一次目标函数，如果连续3次变化小于0.1%，可以提前停止。

7.3.3 MOD（Method of Optimal Directions）

MOD（Engan et al., 1999）是另一种字典学习算法：

1. 稀疏编码步：同K-SVD
2. 字典更新步：联合更新所有原子（而非逐个） $$\mathbf{D}^{(t+1)} = \arg\min_{\mathbf{D}} \sum_i |\mathbf{x}_i - \mathbf{D}\mathbf{s}_i^{(t+1)}|^2$$ 闭式解（伪逆）： $$\mathbf{D}^{(t+1)} = \mathbf{X}\mathbf{S}^T(\mathbf{S}\mathbf{S}^T)^{-1}$$ 其中$\mathbf{X} = [\mathbf{x}_1, ..., \mathbf{x}_N]$，$\mathbf{S} = [\mathbf{s}_1, ..., \mathbf{s}_N]$

对比：

• K-SVD：逐原子更新，保持稀疏模式
• MOD：联合更新，更简单但可能破坏稀疏性

深入理解 MOD：

MOD采用了一个更直接的字典更新策略：既然稀疏系数已经固定，为什么不一次性求解所有字典原子的最优值？

字典更新的推导：

给定固定的稀疏系数矩阵$\mathbf{S} \in \mathbb{R}^{m \times N}$（每列是一个$\mathbf{s}_i$），目标是： $$\min_{\mathbf{D}} |\mathbf{X} - \mathbf{D}\mathbf{S}|_F^2$$ 这是标准的最小二乘问题！对$\mathbf{D}$求梯度并令其为0： $$\frac{\partial}{\partial \mathbf{D}} |\mathbf{X} - \mathbf{D}\mathbf{S}|_F^2 = -2(\mathbf{X} - \mathbf{D}\mathbf{S})\mathbf{S}^T = 0$$ 解得： $$\mathbf{D}\mathbf{S}\mathbf{S}^T = \mathbf{X}\mathbf{S}^T$$ $$\mathbf{D} = \mathbf{X}\mathbf{S}^T(\mathbf{S}\mathbf{S}^T)^{-1}$$ 这是闭式解！非常简洁。

数值例子：

假设$N=3$个信号，$n=2$维，$m=3$个原子： $$\mathbf{X} = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{bmatrix}, \quad \mathbf{S} = \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}$$ 计算$\mathbf{S}\mathbf{S}^T$： $$\mathbf{S}\mathbf{S}^T = \begin{bmatrix} 5 & 0 & 1 \\ 0 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}$$ 计算$\mathbf{X}\mathbf{S}^T$： $$\mathbf{X}\mathbf{S}^T = \begin{bmatrix} 10 & 5 & 4 \\ 8 & 4 & 6 \end{bmatrix}$$ 然后求解$\mathbf{D} = \mathbf{X}\mathbf{S}^T(\mathbf{S}\mathbf{S}^T)^{-1}$（需要矩阵求逆）。

MOD vs K-SVD 的深度对比：

| 特性 | MOD | K-SVD |

稀疏性保持的问题：

MOD的一个潜在问题是：联合更新可能会破坏稀疏模式。例如：

• K-SVD更新第$j$个原子时，只影响使用该原子的信号（$\Omega_j$）
• MOD更新所有原子时，可能会使原本不使用某个原子的信号突然需要该原子

实际中，MOD通常需要在更新后重新归一化原子，并可能需要更多迭代才能收敛。

实践中的选择：

MOD更简单，适合作为教学工具或快速原型。K-SVD更成熟，在实际应用中更常用。

7.3.4 在线字典学习

问题：批量方法（K-SVD、MOD）需要所有数据在内存中，不适合大规模或流数据。

在线字典学习（Mairal et al., 2010）：

每次迭代只使用一个（或小批量）样本$\mathbf{x}_t$：

1. 稀疏编码：$\mathbf{s}_t = \arg\min_{\mathbf{s}} |\mathbf{x}_t - \mathbf{D}\mathbf{s}|^2 + \lambda|\mathbf{s}|_1$
2. 字典更新：随机梯度下降 $$\mathbf{D} \leftarrow \mathbf{D} - \eta_t \nabla_{\mathbf{D}} |\mathbf{x}_t - \mathbf{D}\mathbf{s}_t|^2$$ 并归一化原子

优势：内存高效、可扩展、适合流数据

深入理解在线学习：

在线字典学习的核心思想是随机逼近（stochastic approximation）：用单个样本的梯度估计整体梯度。

完整算法：

初始化: 字典 D（随机或DCT）, A = 0, B = 0

For t = 1, 2, 3, ...:

  1. 接收新样本 x_t
  2. 稀疏编码: s_t = argmin_s ||x_t - Ds||² + λ||s||₁
  3. 更新累积统计量:
     A ← ρA + s_t s_t^T     (m×m矩阵)
     B ← ρB + x_t s_t^T     (n×m矩阵)

  4. 字典更新: 对每个原子 j:
     d_j ← B[:, j] / √(A[j,j])  (归一化)

  5. 衰减因子: ρ = (t-1)/t 或固定值（如0.99）

其中$\mathbf{A}$和$\mathbf{B}$是累积统计量，对应批量版本的$\mathbf{S}\mathbf{S}^T$和$\mathbf{X}\mathbf{S}^T$。

与 MOD 的联系：

在线版本本质上是MOD的随机梯度版本：

• MOD（批量）：$\mathbf{D} = \mathbf{X}\mathbf{S}^T(\mathbf{S}\mathbf{S}^T)^{-1} = \mathbf{B}\mathbf{A}^{-1}$
• 在线：每次用一个样本更新$\mathbf{A}$和$\mathbf{B}$，然后更新$\mathbf{D}$

数值例子：

假设学习一个简单的2D字典（$n=2$, $m=3$），在线处理数据流：

迭代1：$\mathbf{x}_1 = [1, 2]^T$

• 稀疏编码：$\mathbf{s}_1 = [0.8, 0, 0.5]^T$（假设）
• 更新：$\mathbf{A} \leftarrow \mathbf{s}_1\mathbf{s}_1^T$, $\mathbf{B} \leftarrow \mathbf{x}_1\mathbf{s}_1^T$
• 字典更新：...

迭代2：$\mathbf{x}_2 = [2, 1]^T$

• 稀疏编码：$\mathbf{s}_2 = [0, 1.2, 0]^T$（假设）
• 更新：$\mathbf{A} \leftarrow 0.5\mathbf{A} + \mathbf{s}_2\mathbf{s}_2^T$, $\mathbf{B} \leftarrow 0.5\mathbf{B} + \mathbf{x}_2\mathbf{s}_2^T$
• 字典更新：...

随着时间推移，$\mathbf{D}$逐渐收敛。

在线学习的优势：

1. 内存效率： - 批量K-SVD：需要存储所有$N$个样本，内存$O(nN)$ - 在线学习：只需存储$\mathbf{A}, \mathbf{B}, \mathbf{D}$，内存$O(m^2 + nm)$ - 对于大规模数据（如$N=10^6$），差异巨大

2. 适应性： - 可以处理非平稳数据（分布随时间变化） - 通过调整$\rho$控制对新数据的权重

3. 可扩展性： - 可并行化（mini-batch版本） - 适合分布式训练

挑战与解决方案：

| 挑战 | 解决方案 |

Rule of thumb：在线字典学习适合处理百万级以上的样本。对于中小规模数据（$N < 100k$），批量K-SVD通常更快且质量更好。Mini-batch大小选择在10-1000之间，平衡收敛速度和内存使用。衰减因子$\rho$通常设为$(t-1)/t$（标准在线学习）或固定值0.95-0.99（更快适应新数据）。每处理1000-10000个样本检查一次字典质量（重建误差），决定是否继续训练。

7.4 稀疏编码的率失真权衡

7.4.1 稀疏度 vs 重建质量

实验观察（图像块$8 \times 8 = 64$维，字典$256$原子）：

| 稀疏度 $k$ | 重建PSNR (dB) | 码率 (bits/block) |

观察：

• $k$增加，重建质量提升，但码率也增加
• 典型工作点：$k = 3$-$5$，在质量和码率间良好权衡

深入分析率失真权衡：

上述表格揭示了稀疏编码的基本率失真特性。让我们更详细地分析：

PSNR增益的边际递减：

从表中可以看出，每增加稀疏度，PSNR增益逐渐减少：

• $k: 1 \to 3$：PSNR提升 $32 - 25 = 7$ dB，每个额外原子贡献 $3.5$ dB
• $k: 3 \to 5$：PSNR提升 $36 - 32 = 4$ dB，每个额外原子贡献 $2$ dB
• $k: 5 \to 10$：PSNR提升 $40 - 36 = 4$ dB，每个额外原子贡献 $0.8$ dB
• $k: 10 \to 20$：PSNR提升 $45 - 40 = 5$ dB，每个额外原子贡献 $0.5$ dB

这是典型的收益递减（diminishing returns）现象。

率失真效率（Rate-Distortion Efficiency）：

定义效率为单位码率带来的PSNR增益： $$\text{Efficiency} = \frac{\Delta \text{PSNR}}{\Delta \text{Rate}}$$ | 稀疏度区间 | $\Delta$PSNR (dB) | $\Delta$Rate (bits) | 效率 (dB/bit) |

效率持续下降！在$k=3$-$5$时效率仍然较高，之后效率大幅降低。

不同信号类型的率失真曲线：

不同类型的图像块表现出不同的率失真特性：

类型1：平滑区域

PSNR (dB)
  50 |    *****
     |  **
  40 | *
     |*
  30 |
     +---------------→ k
     0  2  4  6  8 10

• 只需很少的原子就能达到高质量（$k=2$-$3$即可达到45 dB）
• 继续增加$k$无明显改善

类型2：边缘/纹理

PSNR (dB)
  50 |          ****
     |       ***
  40 |    **
     |  **
  30 | *
     +---------------→ k
     0  2  4  6  8 10

• 需要更多原子才能达到相同质量（$k=5$-$7$达到45 dB）
• 改善更渐进，无明显饱和点

类型3：复杂纹理

PSNR (dB)
  50 |
     |         *****
  40 |     ****
     |  ***
  30 | **
     +---------------→ k
     0  5  10 15 20

• 需要许多原子（$k=15$-$20$才能达到45 dB）
• 即使$k$很大，质量仍在缓慢提升

自适应稀疏度分配：

受到水注入原理的启发，理想的编码器应该根据块的复杂度自适应选择$k$：

• 简单块（平滑）：$k=1$-$2$
• 中等复杂度（边缘）：$k=3$-$5$
• 复杂块（纹理）：$k=8$-$15$

这样可以在给定总码率预算下最小化整体失真。

数值例子：

假设一幅图像包含1000个8×8块，预算总码率50,000 bits。

固定稀疏度策略（$k=5$）：

• 每块：50 bits
• 总码率：50,000 bits
• 平均PSNR：36 dB（从表中）

自适应稀疏度策略： 假设图像组成为：

• 600个简单块：每个$k=2$ → 20 bits，PSNR 40 dB
• 300个中等块：每个$k=5$ → 50 bits，PSNR 36 dB
• 100个复杂块：每个$k=10$ → 100 bits，PSNR 35 dB

总码率：$600 \times 20 + 300 \times 50 + 100 \times 100 = 37,000$ bits < 50,000 bits！

平均PSNR：$\frac{600 \times 40 + 300 \times 36 + 100 \times 35}{1000} = 38.1$ dB

通过自适应分配，节省了13,000 bits，且PSNR还提升了2.1 dB！

与理论率失真界的比较：

对于高斯信源，理论率失真函数为：$R(D) = \frac{1}{2}\log_2\frac{\sigma^2}{D}$

转换为PSNR：$\text{PSNR} = 10\log_{10}\frac{255^2}{D}$

高斯理论界（$\sigma^2 = 1000$，典型自然图像块方差）：

| 码率 (bits/block) | 理论PSNR (dB) | 稀疏编码PSNR (dB) | 差距 (dB) |

稀疏编码落后理论界约4-6 dB。这是因为：

1. 字典表示能力有限（非最优编码）
2. 位置信息的码率开销
3. $\ell_0$优化的次优性（OMP是贪心算法）

Rule of thumb：选择稀疏度$k$时，应在率失真曲线的"肘部"（elbow point）附近，通常对应于效率下降50%的点。对于自然图像，$k=3$-$5$是常见的甜点（sweet spot）。如果码率预算充足且质量要求高，可以使用$k=10$-$15$。超过$k=20$后，增益通常不值得额外的计算和码率成本。对于自适应系统，根据块方差$\sigma^2$选择$k$：$k \approx \max(1, \min(20, \lceil 0.01 \sigma^2 \rceil))$可以作为启发式规则。

7.4.2 与DCT、小波的对比

率失真性能（自然图像）：

PSNR (dB)
  40 |           * 学习字典
     |       *
  35 |   *       * 小波
     | *     *
  30 |   *       * DCT
     | *
  25 | *
     +--------------------→ 码率 (bpp)
     0  0.2  0.4  0.6  0.8

结论：

• 学习字典 > 小波 > DCT（相同码率下）
• 优势：学习字典适应数据，非正交基更灵活
• 代价：计算复杂度高（编码时需优化）

深入对比分析：

让我们更系统地比较这三种方法在各个维度上的差异：

1. 表示能力对比：

| 方法 | 基函数 | 自适应性 | 稀疏性 |

2. 数值性能对比：

在标准测试集（Lena、Barbara等自然图像）上的实验结果：

| 码率 (bpp) | DCT PSNR (dB) | 小波 PSNR (dB) | 学习字典 PSNR (dB) |

观察：

• 学习字典相比DCT有2-3.5 dB增益
• 学习字典相比小波有1-2 dB增益
• 低码率时（0.1-0.25 bpp），学习字典优势更明显

3. 计算复杂度对比：

以处理一个8×8图像块为例：

| 方法 | 编码复杂度 | 解码复杂度 | 训练复杂度 |

学习字典的编码复杂度是DCT的400倍！但解码只慢1.5倍。

4. 不同图像内容的适应性：

场景A：平滑渐变（如天空）

性能排名: 小波 ≈ 学习字典 > DCT
理由: 小波的多分辨率特性天然适合平滑渐变
     学习字典学到类似小波的原子
     DCT的块边界效应明显

场景B：锐利边缘（如建筑）

性能排名: 学习字典 > 小波 > DCT
理由: 学习字典可以学到多方向边缘原子
     小波有方向选择性但受限于固定方向
     DCT会在边缘产生振铃效应

场景C：纹理（如织物、草地）

性能排名: 学习字典 >> 小波 > DCT
理由: 纹理模式可以被字典学习捕获
     小波和DCT无法适应特定纹理模式
     学习字典优势最大（3-4 dB增益）

5. 实际系统考虑：

JPEG（基于DCT）：

优势：

- 编解码速度极快
- 硬件加速广泛支持
- 标准化、兼容性好
- 无需训练

劣势：

- 固定变换，不适应数据
- 块效应明显
- 率失真性能一般

JPEG2000（基于小波）：

优势：

- 多分辨率
- 渐进传输
- 无块效应
- 率失真性能优于JPEG

劣势：

- 计算复杂度高于JPEG
- 标准化采用较慢
- 仍然是固定变换

稀疏编码压缩系统：

优势：

- 最佳率失真性能
- 可针对特定应用优化
- 数据自适应

劣势：

- 编码极慢（不适合实时）
- 需要预训练字典
- 字典传输/存储开销
- 缺乏标准化

6. 混合策略：

实际中，可以结合各方法的优势：

策略1：分层编码

1. 用小波获得多分辨率分解
2. 在每个子带用学习字典稀疏编码
3. 结合小波的全局结构和字典的局部适应性

策略2：预测+稀疏残差

1. 用DCT/小波获得粗略重建
2. 用学习字典编码残差（通常更稀疏）
3. 降低字典学习的复杂度（只处理残差）

数值例子：

假设编码Lena图像（512×512），目标码率0.5 bpp（总计128 Kbits）：

纯DCT：

• 编码时间：10 ms
• 解码时间：8 ms
• PSNR：32.0 dB
• 文件大小：128 Kbits

纯学习字典（$m=512$, $k=5$）：

• 训练时间：2 hours（离线，使用10k块）
• 编码时间：4000 ms
• 解码时间：15 ms
• PSNR：35.5 dB
• 文件大小：128 Kbits + 字典（50 Kbits，如果需要传输）

混合策略（DCT + 稀疏残差，$m=256$, $k=3$）：

• 训练时间：30 min（只训练残差字典）
• 编码时间：50 ms
• 解码时间：10 ms
• PSNR：34.0 dB
• 文件大小：128 Kbits

混合策略在性能、速度、复杂度之间取得平衡。

7. 应用场景推荐：

| 应用 | 推荐方法 | 理由 |

Rule of thumb：对于特定领域（如人脸、纹理），学习字典可以比通用变换获得2-3 dB的PSNR增益。但计算成本高，主要用于对质量要求极高或带宽受限的场景。如果编码时间不是瓶颈（如离线编码、云端处理），且数据类型相对固定，学习字典是值得的。对于通用、实时场景，DCT仍是首选。小波适合需要多分辨率或渐进传输的应用。

7.5 应用实例

7.5.1 图像去噪

模型：$\mathbf{y} = \mathbf{x} + \mathbf{n}$，其中$\mathbf{n}$是高斯噪声

稀疏去噪： $$\min_{\mathbf{s}} |\mathbf{y} - \mathbf{D}\mathbf{s}|^2 + \lambda |\mathbf{s}|_1$$ 直觉：自然图像块是稀疏的（在学习字典下），噪声不是。稀疏约束抑制噪声。

率失真视角：

• 允许小失真（去噪后与原噪声图像的差异）
• 换取低"码率"（稀疏表示）
• 稀疏表示对应干净信号，非稀疏分量对应噪声

深入理解稀疏去噪的原理：

稀疏去噪的核心假设是：信号和噪声在字典下有不同的稀疏性。

数学分析：

假设干净信号$\mathbf{x}$在字典$\mathbf{D}$下有稀疏表示$\mathbf{s}_{\text{clean}}$（$|\mathbf{s}_{\text{clean}}|_0 = k$），噪声$\mathbf{n} \sim \mathcal{N}(0, \sigma^2\mathbf{I})$。

观测：$\mathbf{y} = \mathbf{x} + \mathbf{n} = \mathbf{D}\mathbf{s}_{\text{clean}} + \mathbf{n}$

如果直接在$\mathbf{D}$下表示$\mathbf{y}$： $$\mathbf{y} = \mathbf{D}\mathbf{s}_{\text{noisy}}$$ 其中$\mathbf{s}_{\text{noisy}}$将包含：

• 信号成分：$\mathbf{s}_{\text{clean}}$（稀疏）
• 噪声成分：$\mathbf{D}^T\mathbf{n}$（不稀疏，如果$\mathbf{D}$是过完备的）

稀疏正则化倾向于保留稀疏的信号成分，抑制非稀疏的噪声成分。

数值例子：

考虑一个64维信号，字典256原子，噪声标准差$\sigma = 20$。

干净信号： $$\mathbf{x} = 5\mathbf{d}_3 + 8\mathbf{d}_{17} + 3\mathbf{d}_{42}$$ （3个原子，高度稀疏）

噪声： $$\mathbf{n} = [2.1, -1.5, 0.8, ..., -0.3]^T$$ （64个分量，均值0，标准差20，不稀疏）

观测信号： $$\mathbf{y} = \mathbf{x} + \mathbf{n}$$ 不同去噪方法的效果：

| 方法 | 稀疏度 | 重建MSE | PSNR (dB) |

最佳$\lambda$值平衡了拟合噪声数据（小$\lambda$）和强制稀疏性（大$\lambda$）。

参数选择的率失真解释：

稀疏去噪的$\lambda$对应于率失真权衡中的拉格朗日乘子：

• 大$\lambda$：强制高稀疏度（低"码率"），但可能欠拟合（高失真）
• 小$\lambda$：允许更多原子（高"码率"），拟合噪声（高失真）
• 最优$\lambda$：在率失真曲线的最佳点

与Wiener滤波的对比：

| 特性 | Wiener滤波 | 稀疏去噪 |

实际性能对比：

在标准测试图像（Barbara, 512×512, $\sigma=25$）上：

| 方法 | PSNR (dB) | 视觉质量 |

稀疏去噪在纹理保持上优于传统方法，接近最先进的BM3D。

$\lambda$的选择方法：

方法1：基于噪声水平 $$\lambda \approx C \cdot \sigma$$ 其中$C$是经验常数（通常$C=2$-$5$）。噪声越大，需要越强的稀疏约束。

方法2：交叉验证

• 将图像分为多个块
• 用部分块的去噪结果调整$\lambda$
• 选择最小化验证误差的$\lambda$

方法3：Sure（Stein's Unbiased Risk Estimate） 在无需干净图像的情况下，估计MSE： $$\text{SURE}(\lambda) = \frac{1}{n}|\mathbf{y} - \hat{\mathbf{x}}(\lambda)|^2 - \sigma^2 + \frac{2\sigma^2}{n}\text{div}(\hat{\mathbf{x}})$$ 其中$\text{div}(\hat{\mathbf{x}})$是去噪算子的散度（自由度）。

分块去噪策略：

实际图像去噪时，通常分块处理：

1. 滑动窗口：提取重叠的8×8或16×16块
2. 逐块去噪：对每块应用稀疏去噪
3. 聚合：重叠区域取平均（减少块边界伪影）

数值例子：

512×512图像，使用8×8块，步长4（50%重叠）：

• 总块数：约16,000个
• 每个像素被覆盖：4次（平均）
• 聚合后PSNR比单块提升约1 dB

Rule of thumb：对于高斯噪声去噪，$\lambda$设为$2\sigma$到$4\sigma$是一个好的起点。字典应在干净图像上训练（或使用通用自然图像字典）。稀疏度$k$通常选择5-10，取决于块大小和噪声水平。使用重叠分块（50%重叠）可以显著减少块效应。对于彩色图像，在YCbCr空间分别处理Y/Cb/Cr通道，Y通道用更多原子（$k=10$），色度通道用更少（$k=3$）。

7.5.2 压缩感知（Compressive Sensing）

问题：信号$\mathbf{x} \in \mathbb{R}^n$，但只观测到$\mathbf{y} = \mathbf{\Phi}\mathbf{x} \in \mathbb{R}^m$（$m < n$），能否恢复$\mathbf{x}$？

稀疏先验：如果$\mathbf{x} = \mathbf{D}\mathbf{s}$且$\mathbf{s}$稀疏，则可以： $$\min_{\mathbf{s}} |\mathbf{y} - \mathbf{\Phi}\mathbf{D}\mathbf{s}|^2 + \lambda |\mathbf{s}|_1$$ 定理（CS理论）：如果$\mathbf{\Phi}$满足RIP（受限等距性质），$|\mathbf{s}|_0 = k$，则$m = O(k \log \frac{n}{k})$个测量足以完美恢复。

率失真联系：

• 测量数$m$对应"码率"
• 重建误差对应"失真"
• 稀疏性使得低"码率"（少测量）下仍能低失真重建

深入理解压缩感知：

压缩感知（CS）颠覆了传统的采样-压缩范式：

• 传统：先全采样（$n$个样本），再压缩（保留$m < n$个系数）
• CS：直接采样压缩表示（$m$个测量），跳过中间步骤

数学直觉：

欠定系统$\mathbf{y} = \mathbf{\Phi}\mathbf{x}$（$m < n$）通常有无穷多解。但如果我们知道$\mathbf{x}$是稀疏的（在某个字典下），则解可能是唯一的！

几何理解（2D例子）：

假设$n=2$, $m=1$：测量$y = \phi_1 x_1 + \phi_2 x_2$

    x₂
     |
     |     / 测量线（所有满足y的点）
     |   /
     |  /
     | /  * 稀疏解（在坐标轴上）
     |/_____________________ x₁
     O

如果额外约束$x_1 = 0$或$x_2 = 0$（稀疏性），则解唯一！

RIP条件的直觉：

受限等距性质（RIP）要求：对于$k$-稀疏信号，测量矩阵$\mathbf{\Phi}$近似保持距离： $$(1-\delta_k)|\mathbf{x}|^2 \leq |\mathbf{\Phi}\mathbf{x}|^2 \leq (1+\delta_k)|\mathbf{x}|^2$$ 直觉：RIP保证$\mathbf{\Phi}$不会"压扁"稀疏信号，从而信息不会丢失。

随机测量矩阵（如高斯随机矩阵）以高概率满足RIP，只要$m \geq C k \log(n/k)$。

数值例子：

场景：恢复一个512维信号，已知在DCT下10-稀疏。

传统方法：

• 采样：512个样本
• DCT变换：512个系数
• 量化+编码：保留10个最大系数
• 压缩比：512/10 ≈ 50

压缩感知：

• 测量数：$m = O(10 \log(512/10)) \approx 10 \times 5.6 \approx 60$个（理论界） 实际中，通常需要$m \approx 4k = 40$个测量（经验规则）

• 恢复：求解$\ell_1$最小化

• 压缩比：512/40 ≈ 13

CS需要更少的测量（40 vs 512），但恢复需要优化（计算成本高）。

实际恢复性能：

| 测量数 $m$ | $m/k$ | 恢复成功率 | 平均MSE |

经验法则：$m \geq 3k$到$5k$足以高概率恢复。

CS在图像中的应用：

单像素相机：

• 传统相机：用$n$个像素传感器直接测量图像
• 单像素相机：用随机掩码（DMD）调制光线，单个传感器做$m$次测量
• 优势：在某些波段（如红外、太赫兹），单像素传感器便宜得多

MRI加速：

• 传统MRI：采集完整k空间数据（耗时）
• CS-MRI：随机采样k空间（$m < n$测量），利用图像稀疏性恢复
• 加速比：3-10倍（$m/n = 0.1$-$0.3$）

数值例子（CS-MRI）：

128×128 MRI图像（$n = 16384$）：

• 完整采样：16384个k空间样本，扫描时间10分钟
• CS采样（30%）：4915个样本，扫描时间3分钟
• 字典：小波 + TV（总变差）
• 恢复算法：ISTA
• 恢复PSNR：38 dB（临床可接受）

与率失真的深层联系：

CS可以看作是一种测量域的率失真编码：

| 概念 | 传统率失真 | 压缩感知 |

率失真函数的类比：

对于$k$-稀疏信号，CS的"率失真函数"为： $$m(D) = O\left(k \log \frac{n}{k}\right) + O\left(\frac{\sigma^2}{D}\right)$$ 其中第一项是稀疏恢复的测量数，第二项是噪声引起的额外测量需求。

CS的局限性：

1. 计算成本：$\ell_1$优化比FFT/DCT慢得多（秒 vs 毫秒）
2. 精确稀疏性假设：自然信号通常只是"近似稀疏"，恢复质量下降
3. 字典选择：性能严重依赖于字典选择（DCT, 小波, 学习字典？）
4. 噪声敏感：测量噪声显著影响恢复质量

Rule of thumb：对于$k$-稀疏信号，测量数选择$m = 4k$到$6k$可以实现高质量恢复（PSNR > 35 dB）。测量矩阵使用随机高斯（理论保证）或部分DCT/Hadamard（实际中更高效）。对于图像，使用小波或学习字典作为稀疏基，配合TV正则化可以进一步提升质量。CS最适合测量成本高（如MRI、天文学）或硬件受限（如无线传感器网络）的场景。

7.5.3 特征提取

字典学习的稀疏表示$\mathbf{s}_i$可以作为特征，用于分类、检索等任务。

优势：

• 稀疏性：高维特征但多数为0，易存储和处理
• 判别性：学习字典时加入分类损失，得到判别性字典
• 可解释性：每个原子有语义（如人脸字典中的"左眼"、"鼻子"）

应用：人脸识别、纹理分类、图像检索

深入理解稀疏特征表示：

稀疏编码作为特征提取方法，相比传统方法（如SIFT、HOG）和深度学习方法（如CNN）有独特优势。

1. 稀疏特征的优势：

维度与稀疏性的权衡：

假设图像块$\mathbf{x} \in \mathbb{R}^{64}$（8×8），使用字典$\mathbf{D} \in \mathbb{R}^{64 \times 512}$：

• 特征维度：$m = 512$（高维）
• 但稀疏度：$|\mathbf{s}|_0 \approx 5$（实际上只有5个非零元素）

对比传统特征：

• SIFT：128维，稠密
• HOG：通常36-108维，稠密
• 稀疏编码：512维，但只有5个非零（存储/计算时可忽略零）

2. 判别性字典学习：

标准字典学习只考虑重建： $$\min_{\mathbf{D}, \\{\mathbf{s}_i\\}} \sum_i |\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2 + \lambda |\mathbf{s}_i|_0$$ 判别性扩展（如D-KSVD）：同时优化分类性能： $$\min_{\mathbf{D}, \\{\mathbf{s}_i\\}, \mathbf{W}} \sum_i \left[|\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2 + \lambda |\mathbf{s}_i|_0 + \alpha |y_i - \mathbf{W}\mathbf{s}_i|^2\right]$$ 其中：

• $y_i$：类别标签
• $\mathbf{W}$：线性分类器
• $\alpha$：分类损失权重

直觉：字典不仅要能重建信号，还要使得稀疏系数$\mathbf{s}_i$具有判别性（同类相似，异类不同）。

3. 人脸识别应用：

数值例子：

数据集：ORL人脸数据库，40个人，每人10张图片（共400张），图像32×32。

方法1：像素特征 + 最近邻

• 特征：1024维（直接像素）
• 分类器：k-NN（k=1）
• 识别率：70%

方法2：PCA + 最近邻

• 特征：100维（主成分）
• 分类器：k-NN（k=1）
• 识别率：85%

方法3：稀疏编码 + 线性SVM

• 字典：512原子（从训练集学习）
• 稀疏度：$k=10$
• 特征：512维稀疏向量（10个非零）
• 分类器：线性SVM
• 识别率：92%

方法4：判别性字典 + 线性SVM

• 字典：512原子（判别性学习）
• 稀疏度：$k=10$
• 分类器：线性SVM
• 识别率：95%

判别性字典学习显著提升了分类性能！

4. 字典原子的可解释性：

对于人脸数据，学习的字典原子可以可视化：

原子1:    原子2:    原子3:    原子4:
 👁️       👁️       👃       👄
左眼      右眼      鼻子      嘴巴

原子5:    原子6:    ...      原子512:
 👂       💈
耳朵      头发轮廓   ...      背景

每个人脸可以表示为这些"部件"的组合： $$\mathbf{x}_{\text{face}} \approx s_1 \cdot\text{左眼} + s_2 \cdot\text{右眼} + s_3 \cdot\text{鼻子} + ...$$

5. 纹理分类应用：

任务：分类不同纹理（如木头、金属、布料、石头）

数据集：CUReT纹理数据库，61类纹理，每类92张图片。

实验设置：

• 提取32×32图像块（$n=1024$）
• 学习类特定字典：每类一个字典$\mathbf{D}_c$（$m=256$）
• 测试时：对新块$\mathbf{x}$，在每个类字典下稀疏编码，选择重建误差最小的类

结果：

| 方法 | 分类准确率 |

6. 与深度学习的比较：

| 特性 | 稀疏编码 | CNN（如ResNet） |

稀疏编码在小数据集上有优势，深度学习在大数据集上更强。

7. 率失真视角的特征提取：

稀疏特征可以看作是一种有损压缩：

• 率：特征维度$m$（但有效维度是稀疏度$k$）
• 失真：重建误差$|\mathbf{x} - \mathbf{D}\mathbf{s}|^2$

好的特征应该：

• 低率：$k$小（稀疏），便于存储和计算
• 低失真：重建好（保留重要信息）
• 判别性：不同类的特征要能区分

这正是率失真权衡在特征空间的体现！

8. 混合特征策略：

实际中，可以结合多种特征：

策略1：金字塔稀疏编码

• 不同尺度提取图像块（如4×4, 8×8, 16×16）
• 每个尺度学习一个字典
• 连接所有稀疏系数作为最终特征

策略2：空间金字塔匹配 + 稀疏编码

• 将图像分为多个空间区域（如2×2网格）
• 每个区域提取稀疏特征并池化（max pooling或sum）
• 连接所有区域的池化特征

数值例子（图像分类，Caltech-101数据集）：

| 方法 | 特征维度 | 分类准确率 |

Rule of thumb：对于小到中等数据集（< 10k样本），判别性字典学习是一个强大的特征提取方法，通常优于手工设计的特征。字典大小选择$m = 256$-$1024$，稀疏度$k = 5$-$20$。对于分类任务，使用判别性字典学习（D-KSVD）并配合线性SVM。对于检索任务，可以直接使用稀疏系数的$\ell_1$或$\ell_2$距离。对于大规模数据集（> 100k样本），深度学习方法通常更好，但稀疏编码可以作为预训练或辅助特征。

7.6 本章小结

核心概念：

1. 稀疏表示： - 信号$\mathbf{x} \approx \mathbf{D}\mathbf{s}$，$\mathbf{s}$稀疏 - 过完备字典$\mathbf{D}$（$m > n$）

2. 率失真解释： - 稀疏度$|\mathbf{s}|_0$ ↔ 码率$R$ - 重建误差$|\mathbf{x} - \mathbf{D}\mathbf{s}|^2$ ↔ 失真$D$ - 稀疏编码：$\min [D + \lambda R]$

3. 字典学习： - K-SVD：逐原子SVD更新 - MOD：联合伪逆更新 - 在线方法：随机梯度

4. 应用： - 图像去噪、压缩感知、特征提取

关键公式：

• 稀疏编码：$\min_{\mathbf{s}} |\mathbf{x} - \mathbf{D}\mathbf{s}|^2 + \lambda |\mathbf{s}|_1$
• 字典学习：$\min_{\mathbf{D}, \\{\mathbf{s}_i\\}} \sum_i [|\mathbf{x}_i - \mathbf{D}\mathbf{s}_i|^2 + \lambda |\mathbf{s}_i|_0]$
• 码率估计：$R \approx k(\log \frac{m}{k} + b)$

7.7 常见陷阱与错误

Gotcha #1: 字典原子的归一化

错误：忘记归一化字典原子$|\mathbf{d}_j|_2 = 1$。

正解：如果不归一化，优化会让$|\mathbf{d}_j|$任意大、$s_{i,j}$任意小，以降低$|\mathbf{s}_i|_0$但保持$\mathbf{D}\mathbf{s}_i$不变。归一化消除这个尺度自由度。

Gotcha #2: $\ell_0$ vs $\ell_1$的等价性

错误：认为$\ell_1$和$\ell_0$总是给出相同解。

正解：只有在满足某些条件（如RIP、字典的相干性小）时，$\ell_1$松弛才等价于$\ell_0$。一般情况下，$\ell_1$是近似，可能不如$\ell_0$稀疏（但更易计算）。

Gotcha #3: 过拟合

错误：用过大的字典（$m \gg n$）或过小的$\lambda$，导致过拟合。

正解：字典会"记忆"训练数据，在测试数据上泛化差。解决：

• 交叉验证选择$m$和$\lambda$
• 加入字典正则化（如Frobenius范数约束）
• 使用更多训练数据

Gotcha #4: 初始化的影响

错误：用随机初始化字典，收敛到差的局部最优。

正解：好的初始化很重要：

• 用DCT、小波基初始化
• 从训练数据随机采样块作为初始原子
• 多次随机初始化，选最好的

Gotcha #5: 码率的实际计算

错误：认为稀疏度$k$直接等于码率（比特）。

正解：$k$是非零系数个数，实际码率还需要：

• 编码位置：$\log \binom{m}{k}$比特
• 量化系数值：每个系数$b$比特
• 熵编码：如果系数分布已知，可进一步压缩

总码率是这些的和，通常远大于$k$。

Gotcha #6: 计算复杂度

错误：认为稀疏编码像DCT一样快。

正解：稀疏编码（OMP、ISTA等）需要迭代优化，比正交变换慢得多：

• DCT：$O(n \log n)$（FFT）
• OMP（稀疏度$k$）：$O(mnk)$
• 这限制了稀疏编码在实时应用中的使用

Gotcha #7: 字典的可解释性

错误：期望学习的字典原子总是有清晰的语义（如"边缘"、"纹理"）。

正解：字典原子的可解释性取决于数据和算法。某些情况下（如人脸），原子确实有语义。但一般情况下，原子可能是抽象的、难以解释的。字典学习是黑盒优化，不保证可解释性。

下一章预告：第八章将探索深度学习如何重新诠释率失真理论，从VAE到神经压缩、信息瓶颈理论。

← 第六章 | 返回目录 | 第八章：深度学习中的率失真 →