📚 稀疏表示、字典学习、K-SVD 与压缩感知
本笔记系统讲解稀疏学习中的高阶概念：稀疏表示（用少量基表示信号）、字典学习（从数据中学基）、K-SVD（更新字典的算法）、压缩感知（从少量测量重建稀疏信号）。所有算法步骤用表格呈现，公式清晰，适合深入复习。
🎯 一、稀疏表示（Sparse Representation）
✅ 1. 核心思想
任何信号 $\mathbf{x} \in \mathbb{R}^d$ 可近似表示为字典 $\mathbf{D}$ 中少数原子的线性组合：
- $\mathbf{D} \in \mathbb{R}^{d \times K}$：字典（包含 K 个原子/基向量）
- $\boldsymbol{\alpha} \in \mathbb{R}^K$：稀疏编码（大部分元素为 0）
目标：找到一个稀疏的 $\boldsymbol{\alpha}$，使得重构误差最小：
📌 通俗比喻：
一张人脸 = “大眼睛原子”×0.8 + “高鼻梁原子”×0.6 + “微笑原子”×0.9 + 其他原子×0
→ 只用 3 个原子就能描述 → 稀疏表示！
✅ 2. 为什么稀疏表示有用？
| 应用 | 原理说明 |
|---|---|
| 压缩 | 只需存储非零系数的位置和值 + 字典 → 大幅减少存储 |
| 去噪 | 噪声通常无法被字典稀疏表示 → 重建时被滤除 |
| 分类 | 稀疏编码$\boldsymbol{\alpha}$ 可作为新特征输入分类器 |
| 恢复 | 在压缩感知中，从少量观测$\mathbf{y}$ 恢复原始信号 $\mathbf{x}$ |
✅ 3. 如何求解稀疏编码 $\boldsymbol{\alpha}$？
由于 L0 优化是 NP 难问题，常用以下近似方法：
（1）OMP（Orthogonal Matching Pursuit）—— 贪心算法
输入：信号 x, 字典 D, 稀疏度 T
初始化：残差 r = x, α = 0, Λ = 空集（选中的原子索引）
for t in 1 to T:
# 找与当前残差最相关的原子
k = argmax_j |D[:, j]^T r|
Λ = Λ ∪ {k}
# 用选中的原子最小化重构误差（正交投影）
α_Λ = (D[:, Λ]^T D[:, Λ])^{-1} D[:, Λ]^T x
r = x - D[:, Λ] α_Λ
输出：稀疏编码 α（非零位置在 Λ）
（2）Lasso（L1 松弛）—— 凸优化
| 方法对比 | OMP | Lasso |
|---|---|---|
| 速度 | 快 | 慢（需优化） |
| 精度 | 局部最优 | 全局最优（凸问题） |
| 稀疏控制 | 精确控制非零个数$T$ | 通过$\lambda$ 控制稀疏度 |
📚 二、字典学习（Dictionary Learning）
✅ 1. 核心思想
- 字典 $\mathbf{D}$ 不是预定义的，而是从数据中学习！
给定数据集 $\mathbf{X} = [\mathbf{x}_1, …, \mathbf{x}_n] \in \mathbb{R}^{d \times n}$，同时学习 $\mathbf{D}$ 和所有 $\boldsymbol{\alpha}_i$：
📌 交替优化框架：
| 阶段 | 操作描述 |
|---|---|
| 稀疏编码阶段 | 固定$\mathbf{D}$，对每个 $\mathbf{x}_i$ 求解 $\boldsymbol{\alpha}_i$ |
| 字典更新阶段 | 固定所有$\boldsymbol{\alpha}_i$，更新 $\mathbf{D}$（如用 K-SVD） |
| 循环 | 重复以上两步直到收敛 |
✅ 2. 字典学习 vs PCA
| 特性 | PCA | 字典学习 |
|---|---|---|
| 基向量 | 正交、按方差排序 | 非正交、过完备、自适应 |
| 系数 | 稠密（所有系数非零） | 稀疏（大部分系数为 0） |
| 表示能力 | 线性、全局最优 | 非线性、局部结构、更强 |
| 是否监督 | 无监督 | 无监督 |
| 应用 | 降维、去相关 | 去噪、超分、分类、压缩感知 |
📌 过完备字典：原子数 K > 信号维度 d → 提供更多表示自由度
🧩 三、K-SVD 算法（字典更新的经典方法）
✅ 1. 核心思想
- 在字典学习的“字典更新”阶段，逐列更新 $\mathbf{D}$ 的每个原子 $\mathbf{d}_k$
- 对每个原子 $\mathbf{d}_k$，只考虑使用它的样本，用 SVD 同时更新原子和对应系数
✅ 2. 算法步骤（更新第 k 个原子 $\mathbf{d}_k$）
| 步骤编号 | 步骤描述 |
|---|---|
| 1 | 输入：当前字典$\mathbf{D}$，编码矩阵 $\mathbf{A}$，数据 $\mathbf{X}$，原子索引 $k$ |
| 2 | 计算误差矩阵：$\mathbf{E}_k = \mathbf{X} - \sum_{j \neq k} \mathbf{d}_j \boldsymbol{\alpha}_j^T$ |
| 3 | 找到使用原子$k$ 的样本索引：$\omega_k = \{ i \mid \alpha_i(k) \neq 0 \}$ |
| 4 | 若$\omega_k$ 为空，跳过此原子 |
| 5 | 提取子矩阵：$\mathbf{E}_k^{\omega_k} = \mathbf{E}_k[:, \omega_k]$ |
| 6 | 对$\mathbf{E}_k^{\omega_k}$ 做 SVD：$\mathbf{E}_k^{\omega_k} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T$ |
| 7 | 更新原子：$\mathbf{d}_k^{\text{new}} = \mathbf{U}[:, 0]$ |
| 8 | 更新系数：$\boldsymbol{\alpha}_k^{\omega_k, \text{new}} = \Sigma_{11} \cdot \mathbf{V}[:, 0]^T$ |
| 9 | 更新$\mathbf{D}$ 和 $\mathbf{A}$ 的第 $k$ 列/行 |
✅ 3. 完整算法流程表
| 步骤编号 | 步骤描述 |
|---|---|
| 1 | 输入：数据$\mathbf{X}$ (d×n), 字典大小 $K$, 稀疏度 $T$, 最大迭代次数 |
| 2 | 初始化字典$\mathbf{D}$（随机或从 $\mathbf{X}$ 中选 $K$ 列） |
| 3 | for$\text{iter} = 1$ to $\text{max_iter}$： |
| 4 | 稀疏编码阶段：对每个样本 $i$，用 OMP 求 $\boldsymbol{\alpha}_i$ |
| 5 | 字典更新阶段：对每个原子 $k=1$ to $K$： |
| 6 | 按上表“更新第 k 个原子”步骤执行 |
| 7 | 输出：字典$\mathbf{D}$，稀疏编码矩阵 $\mathbf{A}$ |
✅ 4. 优缺点
| 类型 | 描述 |
|---|---|
| ✅ 优点 | 自适应字典，表示能力强；可处理非正交、过完备字典；理论保证 |
| ❌ 缺点 | 计算复杂（SVD 开销大）；对初始化敏感；不适合超大规模数据 |
🌀 四、压缩感知（Compressed Sensing, CS）
✅ 1. 核心思想
突破奈奎斯特采样定理：如果信号是稀疏的，那么可以用远少于传统方法的测量次数完美重建原始信号！
📌 数学框架：
- 原始信号 $\mathbf{x} \in \mathbb{R}^d$，在某个变换域稀疏：$\mathbf{x} = \mathbf{\Psi} \boldsymbol{\theta}$，$|\boldsymbol{\theta}|_0 \ll d$
- 观测：$\mathbf{y} = \mathbf{\Phi} \mathbf{x} = \mathbf{\Phi} \mathbf{\Psi} \boldsymbol{\theta} \in \mathbb{R}^m$，$m \ll d$
重建：
✅ 2. 三大关键条件
| 条件 | 数学描述 | ||||||
|---|---|---|---|---|---|---|---|
| 稀疏性 | $\ | \boldsymbol{\theta}\ | _0 = s \ll d$ | ||||
| 不相干性 | $\mathbf{\Phi}$ 与 $\mathbf{\Psi}$ 不相干（如 $\mathbf{\Phi}$ 为随机高斯矩阵） | ||||||
| RIP | $(1 - \delta_s) \ | \mathbf{v}\ | _2^2 \leq \ | \mathbf{\Phi} \mathbf{\Psi} \mathbf{v}\ | _2^2 \leq (1 + \delta_s) \ | \mathbf{v}\ | _2^2$ |
✅ 3. 应用场景
| 领域 | 应用实例 |
|---|---|
| 医学成像 | MRI：减少扫描时间（从 10 分钟 → 2 分钟） |
| 单像素相机 | 用一个传感器 + 随机掩模拍摄图像 |
| 无线通信 | 减少采样率，节省带宽和功耗 |
| 天文成像 | 从少量望远镜观测重建高分辨率图像 |
✅ 4. 重建算法（表格版）
（1）基追踪（Basis Pursuit）
| 步骤 | 描述 | ||
|---|---|---|---|
| 1 | $\min_{\boldsymbol{\theta}} \ | \boldsymbol{\theta}\ | _1$ |
| 2 | s.t.$\mathbf{y} = \mathbf{\Phi} \mathbf{\Psi} \boldsymbol{\theta}$ |
（2）LASSO 形式
| 步骤 | 描述 | ||||
|---|---|---|---|---|---|
| 1 | $\min_{\boldsymbol{\theta}} \ | \mathbf{y} - \mathbf{\Phi} \mathbf{\Psi} \boldsymbol{\theta}\ | _2^2 + \lambda \ | \boldsymbol{\theta}\ | _1$ |
（3）迭代硬阈值（IHT）
θ = 0
for t in range(T):
gradient = ΦΨ^T (y - ΦΨ θ)
θ = θ + step_size * gradient
θ = hard_threshold(θ, s) # 保留最大的 s 个元素，其余置零🆚 五、概念关系与对比
📌 概念关系图（文字版）
稀疏学习（Sparse Learning）
├── 稀疏表示（Sparse Representation）
│ ├── 固定字典 → 如 DCT、小波、PCA
│ └── 学习字典 → 字典学习（Dictionary Learning）
│ └── 字典更新算法 → K-SVD, Online DL
└── 压缩感知（Compressed Sensing）
└── 依赖稀疏表示 + L1 优化 + 随机测量📌 稀疏表示 vs Lasso 回归
| 稀疏表示 | Lasso 回归 | |
|---|---|---|
| 目标 | 信号重建$\mathbf{x} \approx \mathbf{D}\boldsymbol{\alpha}$ | 预测标签$y \approx \mathbf{X}\mathbf{w}$ |
| 字典 | 可学习或固定 | 固定为训练数据$\mathbf{X}$ |
| 系数 | $\boldsymbol{\alpha}$ 是信号的表示 | $\mathbf{w}$ 是特征权重 |
| 应用 | 去噪、压缩、分类、重建 | 特征选择、回归、分类 |
📌 Lasso 是稀疏表示的特例：当 $\mathbf{D} = \mathbf{X}$，稀疏表示退化为 Lasso！
⚠️ 六、关键注意事项
| 注意点 | 说明 |
|---|---|
| 稀疏性前提 | 压缩感知和稀疏表示都要求信号“本质稀疏”，否则重建失败 |
| 字典大小 | K 太小 → 表示能力不足；K 太大 → 过拟合、计算慢 |
| K-SVD 初始化 | 常用随机或从数据中选 K 个样本作为初始原子 |
| 测量矩阵 | 必须满足 RIP 或使用随机矩阵（高斯、伯努利） |
| 实际误差 | 受噪声、稀疏度估计误差、优化算法精度影响 |
✅ 七、一句话终极总结
稀疏表示 = “万物皆可少数基表示”
字典学习 = “基不是天生的，是学出来的”
K-SVD = “用 SVD 一列一列优化字典”
压缩感知 = “看几眼就能还原全貌 —— 前提是它够稀疏！”
