基本定义

1 稀疏

一个含有大多数零元素的向量(矩阵)称为稀疏向量(稀疏矩阵)，这种结构在数据压缩和特征提取中具有极高的价值。

2 信号分解的局限性

对于信号向量

$y \in \mathbb{R}^n$

若将其分解为一组完备正交基

$G$

的线性组合：

$y = Gc = \sum_{i=1}^n c_i g_i$

在这种情况下，系数向量$c$通常是非稀疏的，即大多数系数都不为零。为了获得稀疏性，需要引入过完备的概念。

完备正交基下的系数是被迫由内积决定的，没有自由度去选择”哪些基向量不用”，因此一般信号只会给出稠密的系数；而过完备字典通过冗余给了我们选择稀疏表示的自由。

3 过完备分解

若将信号向量 $y$ 分解为 $m$ 个 $n$ 维基向量 $d_i$ 的线性组合（其中 $m>n$）：

$y = Dx = \sum_{i=1}^{m} x_i d_i$

由于 $m>n$，这 $m$ 个向量不可能构成正交基，我们称这种原子的集合为过完备的。

为了与正交基区别，称 $d_i$ 为原子、码字、基函数或基向量。由于原子的个数 $m$ 大于向量空间 $\mathbb{R}^n$ 的维数 $n$，称这些原子的集合是过完备的。

为了获得稀疏表示，必须放弃表示唯一性。过完备基（冗余字典）包含 $m (m>n)$ 个原子。此时系数不唯一，可以在众多表示中主动选择一个最稀疏的（即用最少的原子逼近信号）。这恰好对应了稀疏编码的核心思想：通过引入冗余，让信号与少数几个原子匹配，从而获得稀疏系数。

信号过完备分解存在无穷多组解向量 $x$。

4 字典

过完备原子组成的矩阵

$D = [d_1, \dots, d_m] \in \mathbb{R}^{n \times m}$

被称为字典或码本。对字典$D$通常有以下假设：

• 行数小于列数：

  $n < m$

• 满行秩：即

  $\text{rank}(D) = n$

• 单位范数：每一列原子具有单位欧氏范数，即

  $\|d_j\|_2 = 1, \quad j = 1, 2, \dots, m$

---

稀疏编码问题

1 问题定义

当系数向量 $x$ 是稀疏向量时，信号分解 $y = Dx$ 称为稀疏分解。其中，字典矩阵 $D$ 的列常称为解释变量或预测变量；向量 $y$ 称为响应变量或目标信号；而 $x$ 则可视为目标信号 $y$ 相对于字典 $D$ 的一种表示。

稀疏编码问题：给定一个 $n$ 维实值输入向量 $y \in \mathbb{R}^n$，确定 $m$ 个 $n$ 维基向量 $d_1, \dots, d_m \in \mathbb{R}^n$ 以及一个稀疏的 $m$ 维权向量（系数向量）$s \in \mathbb{R}^m$，使得部分基向量的加权线性组合可以充分逼近输入向量，即：

$y \approx Ds$

其中 $D = [d_1, \dots, d_m] \in \mathbb{R}^{n \times m}$。

如果给定的是 $n$ 维实值输入向量的一组集合 $\{y_1, y_2, \dots, y_k\}$，则稀疏编码的目的就是确定基矩阵 $D$ 和系数矩阵 $S$，使得：

$Y \approx DS$

其中系数矩阵 $S$ 的每一个列向量都是稀疏向量。

稀疏编码的主要特点是系数向量只有少数元素不等于零，大多数元素为零。

稀疏编码可能是临界完备的或过完备的。临界完备是指基向量的个数 $m$ 等于输入向量的维数 $n$。

---

稀疏编码问题中的两种求解方法

稀疏编码的目标是在给定输入向量 $y$ 和字典 $D$ 的情况下，寻找一个稀疏的系数向量 $x$ 来逼近或表示原信号。在过完备字典 $D \in \mathbb{R}^{n \times m} (m > n)$ 下，信号 $y \in \mathbb{R}^n$ 的表示 $y = Dx$ 通常有无数个解。为了从中选出最好的一个，不同的优化准则导致不同的解。

1 经典方法：最小 $\ell_2$ 范数解

1.1 问题形式

$\min \|x\|_2 \quad \text{subject to} \quad Dx = y$

1.2 数学含义

• $\|x\|_2 = \sqrt{\sum_{i=1}^m x_i^2}$，即向量的欧几里得长度（能量）。
• 在所有满足精确重构 $Dx = y$ 的解中，选择总能量最小的那个。

1.3 解的特性

• 唯一性：解存在且唯一，表达式为
  $x^* = D^+ y$ 其中 $D^+$ 是 Moore-Penrose 伪逆。
• 稀疏性：非稀疏。一般情况下 $x^*$ 的所有分量都不为零（稠密向量）。因为最小化 $\ell_2$ 范数会”均匀”地分散能量到所有原子，而不是集中在少数几个上。
• 计算难度：低。可以直接通过矩阵运算（如 SVD）计算伪逆，或求解线性方程组 $D^T D x = D^T y$，属于凸二次规划，解析解可用。

1.4 适用场景

• 早期信号处理中的最小能量解（如最小平方估计）。
• 当不关心稀疏性，只要求解稳定且计算简单时。

2. 现代方法：最小 $\ell_0$ 范数解（稀疏表示）

2.1 问题形式

$\min \|x\|_0 \quad \text{subject to} \quad Dx = y$ 其中 $\|x\|_0$ 定义为 $x$ 中非零元素的个数（不是真正的范数，而是计数函数）。

2.2 数学含义

• 在所有精确表示中，寻找非零分量最少的解，即最稀疏的解。
• 稀疏表示的目标：用尽可能少的原子（字典列）线性组合出信号 $y$。

2.3 解的特性

• 唯一性：不一定唯一。当字典满足某些条件（如有限等距性质 RIP）且稀疏度足够低时，稀疏解可能唯一；但一般情况可能存在多个不同位置、但同样稀疏的解。
• 稀疏性：高度稀疏。这正是所求的目标。
• 计算难度：非常高。$\ell_0$ 最小化是组合优化问题，通常 NP-hard。实际中无法穷举所有原子组合，必须用近似算法：
  • 贪婪算法（如正交匹配追踪 OMP）
  • 松弛为 $\ell_1$ 范数（基追踪，LASSO）

2.4 适用场景

• 压缩感知、图像稀疏编码、字典学习、特征选择、可解释性建模。

3. 两种方法的优缺点对比

维度	最小 $\ell_2$ 范数	最小 $\ell_0$ 范数
解的唯一性	唯一	可能不唯一（需附加条件）
稀疏性	稠密（不稀疏）	稀疏
计算难度	低（解析解，多项式时间）	高（NP-hard，需近似）
表示效率	低（需要很多原子）	高（仅用少数原子）
可解释性	差（几乎所有原子都参与）	好（只有关键原子被选中）
对噪声鲁棒性	对微小扰动敏感？	适当松弛后鲁棒性好

“经典”与”现代”的命名反映了信号处理领域的范式转变：从追求能量最小（物理合理）转向追求原子数最少（稀疏、压缩、语义）。

4. 存在噪声时的稀疏逼近（$\ell_0$ 松弛形式）

在实际应用中，观测信号往往含有噪声或模型误差，精确的 $Dx = y$ 约束过强。此时采用 近似表示 更为合理。

4.1 问题形式

$\min \|x\|_0 \quad \text{subject to} \quad \|Dx - y\| \leq \varepsilon$

其中 $\varepsilon > 0$ 是允许的重建误差上界（与噪声水平相关）。

4.2 解释

• 不要求精确重构，只要求误差足够小（在 $\varepsilon$ 球内）。
• 同时在所有近似解中选择最稀疏的那个。

4.3 名称

这个问题称为 稀疏逼近（Sparse Approximation），区别于精确重构的”稀疏表示”。

4.4 常见变体

• $\ell_0$ 带不等式约束 $\to$ 等价于拉格朗日形式：

  $\min_x \|Dx - y\|_2^2 + \lambda \|x\|_0$

  其中 $\lambda$ 控制稀疏性与拟合误差的权衡。

• 实际计算仍然需要松弛为 $\ell_1$ 范数（如 LASSO）或使用贪婪算法（如 OMP 的噪声版本）。

4.5 应用意义

稀疏逼近是现实世界中压缩感知、图像去噪、磁共振重建等领域的核心模型，因为传感器数据总是含有噪声，且信号本身不一定能用字典精确表示（可能存在模型失配）。

---

稀疏矩阵方程的求解

在稀疏编码中，$Y$ 是需要进行编码的样本集，$D$ 是超完备字典，$X$ 是系数矩阵。稀疏矩阵方程的求解就是为了求解出系数矩阵 $X$。

直接求解该优化问题：

$\min_x \|x\|_0 \quad \text{subject to} \quad \|Dx - y\| \leq \varepsilon$

必须筛选出系数向量 $x$ 中所有可能的非零元素。此方法是 NP 困难 的，因为搜索空间过于庞大。

1 为什么是 NP-hard？

从 $m$ 个原子中选尽量少的原子去拟合信号，本质上是一个 子集选择（Subset Selection）问题。

决策版本：给定字典 $D$、信号 $y$、误差阈值 $\varepsilon$ 和稀疏度上限 $k$，问是否存在一个大小不超过 $k$ 的原子子集，使得用这些原子线性组合后的拟合误差 $\|Dx - y\| \leq \varepsilon$？

该决策版本可以通过暴力枚举所有可能的子集来检验：依次尝试选 1 个原子、2 个原子、……、直到 $k$ 个原子，对每个子集求解最小二乘看误差是否满足条件。但这种方法无法在多项式时间内完成，因此该优化问题是NP-hard

2 时间复杂度分析

假设字典有 $m$ 列，要求最多选 $k$ 个原子：

• 从 $m$ 个原子中恰好选 $i$ 个的组合数为 $\binom{m}{i}$
• 需要检查的所有候选子集总数为：

$\sum_{i=0}^{k} \binom{m}{i}$

• 当 $k$ 固定且很小时，该和为 $O(m^k)$，仍在多项式级别；
• 但当 $k$ 与 $m$ 同阶（例如 $k = \Theta(m)$），总和趋近于 $2^m$，即指数级复杂度： $2^m = 1,048,576 \quad (\text{当 } m=20) \qquad 2^m \approx 10^{30} \quad (\text{当 } m=100)$

即使对中等规模（如 $m=100$ 列），穷举所有子集也是不现实的。因此直接求解 $\ell_0$ 最小化问题在计算上是不可行的，必须依赖贪婪算法（如 MP、OMP）或凸松弛（如 $\ell_1$ 近似）来在合理时间内获得近似解。

3 影响稀疏编码精度的因素

给定 $D = [d_1, \dots, d_m] \in \mathbb{R}^{n \times m}$，$y \in \mathbb{R}^n$，$x \in \mathbb{R}^m$，求解方程：

$\min_x \|x\|_0 \quad \text{subject to} \quad \|Dx - y\| \leq \varepsilon$

稀疏编码中的常见问题：

1. 基向量的训练（字典学习）
2. 稀疏编码的求解（稀疏恢复算法）

---

贪婪求解算法

1 匹配追踪算法（MP 算法）

1.1 核心思想

MP（Matching Pursuit）算法迭代地构造一个稀疏解。从字典矩阵 $D$（也称为过完备原子库）中，选择一个与信号 $y$ 最匹配的原子（也就是某列），构建一个稀疏逼近，并求出信号残差，然后继续选择与信号残差最匹配的原子，反复迭代。

关键步骤（每轮迭代）：

1. 匹配：计算当前残差 $r$ 与字典中所有原子的内积，选择绝对值最大的那个 $j^* = \arg\max_{j} |r^T d_j|$

   因为 $\|d_j\|=1$，内积的大小就是残差在该原子方向上的投影长度（可正可负），选出的原子$d_{j^*}$是这一轮认为与残差最相关的。

2. 投影：将残差投影到选中的原子方向上，得到该原子对信号的近似贡献（作为系数） $\alpha = r^T d_{j^*}$

   $\alpha$是标量

3. 更新残差：从当前残差中减去该投影分量，得到新残差 $r_{\text{new}} = r - \alpha \cdot d_{j^*}$

信号表示： 经过 $k$ 轮迭代后，信号 $y$ 可以表示为： $y = \sum_{i=1}^{k} \alpha_i d_{j_i} + r_k$ 其中 $\{d_{j_1}, \dots, d_{j_k}\}$ 是选中的 $k$ 个原子，$r_k$ 是最终残差。

1.2 预处理与匹配准则

一般地，预先将信号 $y$ 零均值化，将字典中的原子（即 $D$ 中的列向量）也零均值化，再将原子归一化后再进行求解。此时，与信号 $y$ 最匹配的原子就是与 $y$ 的内积的绝对值最大的原子。

$d_j^T d_j = 1, \quad \forall j$

1.3 MP 算法示例

假设有信号 $y = [4, 3]^T$，字典 $D = [d_1, d_2, d_3]$，其中：

• $d_1 = [1, 0]^T$（水平方向）
• $d_2 = [0, 1]^T$（垂直方向）
• $d_3 = [0.6, 0.8]^T$（斜向）

第 1 轮：

• 计算内积：$y^T d_1 = 4$，$y^T d_2 = 3$，$y^T d_3 = 4 \times 0.6 + 3 \times 0.8 = 4.8$
• 选中 $d_3$（内积最大），$\alpha_1 = 4.8$
• 近似：$y \approx 4.8 \times d_3 = [2.88, 3.84]^T$
• 残差：$r_1 = y - 4.8 d_3 = [1.12, -0.84]^T$

第 2 轮：

• 计算 $r_1^T d_1 = 1.12$，$r_1^T d_2 = -0.84$，$r_1^T d_3 = 0$（残差已与 $d_3$ 正交！）
• 选中 $d_1$（绝对值最大），$\alpha_2 = 1.12$
• 残差：$r_2 = r_1 - 1.12 d_1 = [0, -0.84]^T$

第 3 轮：

• 选中 $d_2$，$\alpha_3 = -0.84$
• 残差：$r_3 = [0, 0]^T$，精确重构！

最终 $y = 4.8 d_3 + 1.12 d_1 - 0.84 d_2$，用了 3 个原子。但这说明 MP 的一个问题：如果一开始选了”不好”的原子，可能需要用更多原子才能精确表示。

1.4 MP 的优缺点

特性	说明
优点	计算速度快，每步只需一次内积计算
缺点	收敛性差——同一原子可能被重复选择，因为残差只与刚选的原子正交，不一定与之前选的原子正交

MP 的收敛性：虽然 MP 在理论上可以收敛到精确表示（当残差与所有原子正交时），但收敛速度可能很慢。更严重的是，由于每次只保证与最新选中的原子正交，之前选的原子可能又变得”相关”，导致同一原子被反复选中，系数震荡。

2 正交匹配追踪算法（OMP 算法）

2.1 核心改进

OMP（Orthogonal Matching Pursuit）是 MP 的改进版。关键区别在于：在每一步，对残差与已选中的全部原子集合进行正交化处理。

这意味着：

• 残差始终与所有已选原子张成的子空间正交
• 一个原子不会被重复选择
• 在相同精度下，OMP 的迭代步数更少，收敛更快

2.2 正交化如何实现？

假设已选中原子集合为 $S = \{d_{j_1}, \dots, d_{j_k}\}$，令 $D_S$ 为以这些原子为列构成的子矩阵。

OMP 的残差更新：

$\hat{y}_S = D_S (D_S^T D_S)^{-1} D_S^T y = P_S y$

其中 $P_S = D_S (D_S^T D_S)^{-1} D_S^T$ 是到 $\text{span}(S)$ 的正交投影矩阵。

投影到 $\text{span}(S)$：对任意向量 $v$，$P_S v = D_S \cdot \underbrace{(D_S^T D_S)^{-1} D_S^T v}_{\text{系数向量}}$，即 $D_S$ 列的线性组合，因此 $P_S v \in \text{span}(S)$。同时，若 $v \in \text{span}(S)$（即 $v = D_S x$），则： $P_S v = D_S (D_S^T D_S)^{-1} D_S^T D_S x = D_S x = v$ 这说明 $P_S$ 在 $\text{span}(S)$ 上是恒等映射，确实是到该子空间的投影。

残差为： $r = y - \hat{y}_S = (I - P_S) y$

对任意已选原子 $d_{j_i}$：

$r^T d_{j_i} = y^T (I - P_S)^T d_{j_i}$

由于 $P_S$ 是到 $\text{span}(S)$ 的投影，且 $d_{j_i} \in \text{span}(S)$，故 $P_S d_{j_i} = d_{j_i}$，即 $(I - P_S) d_{j_i} = 0$。

又因为 $P_S$ 对称（$P_S^T = P_S$），所以：

$r^T d_{j_i} = y^T (I - P_S) d_{j_i} = y^T \cdot 0 = 0$

因此残差 $r$ 与所有已选原子正交，下一步不会重复选择同一原子。

下一步选择：在新的残差空间中，选择最匹配的原子 $j_{k+1} = \arg\max_{j \notin S} |r^T d_j|$

为什么不会重复选择？ 因为新残差 $r$ 已经与所有已选原子正交，所以它们的内积为 0，不可能是最大值（除非残差为 0，此时已收敛）。

2.3 OMP 算法示例

继续使用 MP 示例中的信号 $y = [4, 3]^T$ 和字典 $D = [d_1, d_2, d_3]$。

第 1 轮：

• 与 MP 相同：内积分别为 4, 3, 4.8
• 选中 $d_3$，$\alpha_1 = 4.8$
• 当前近似：$\hat{y} = 4.8 d_3 = [2.88, 3.84]^T$
• 残差：$r_1 = [1.12, -0.84]^T$

第 2 轮（关键区别）：

• OMP 要求残差与已选集合 $\{d_3\}$ 正交。验证：$r_1^T d_3 = 1.12 \times 0.6 + (-0.84) \times 0.8 = 0.672 - 0.672 = 0$ ✓
• 计算 $r_1$ 与剩余原子内积：$r_1^T d_1 = 1.12$，$r_1^T d_2 = -0.84$
• 选中 $d_1$（绝对值大）

正交投影更新（而非简单相减）：

• 已选集合 $S = \{d_3, d_1\}$，构造 $D_S = [d_3, d_1]$
• 求最优系数 $\hat{x}$ 使得 $\|y - D_S \hat{x}\|_2$ 最小：

能让重构误差最小的系数就是最小二乘解。定义目标函数为误差平方和： $f(x) = \|y - D_S x\|_2^2 = (y - D_S x)^T (y - D_S x)$对 $x$ 求梯度（向量导数）：$\nabla f(x) = -2 D_S^T y + 2 D_S^T D_S x = 0$整理得到正规方程：$D_S^T D_S \, x = D_S^T y$如果 $D_S$ 列满秩（即各原子线性无关），则 $D_S^T D_S$ 可逆，解得：$\hat{x} = (D_S^T D_S)^{-1} D_S^T y$这个 $\hat{x}$ 使得误差平方和最小，因此称为最小二乘解

$\hat{x} = (D_S^T D_S)^{-1} D_S^T y$

• 这样得到的残差自动与 $d_3$ 和 $d_1$ 都正交

计算结果：

• $D_S^T D_S = \begin{bmatrix} 1 & 0.6 \\ 0.6 & 1 \end{bmatrix}$，$D_S^T y = \begin{bmatrix} 4.8 \\ 4 \end{bmatrix}$
• $(D_S^T D_S)^{-1} = \frac{1}{0.64} \begin{bmatrix} 1 & -0.6 \\ -0.6 & 1 \end{bmatrix}$
• $\hat{x} = \begin{bmatrix} 5 \\ 1 \end{bmatrix}$，即 $\hat{y} = 5 d_3 + 1 d_1 = [4, 3]^T = y$

OMP 仅用 2 步就精确重构 而 MP 需要 3 步。因为 OMP 的正交投影保证了每步都在”最优地”利用已选原子。

2.4 OMP 的优缺点

特性	说明
优点	收敛速度快，原子不重复选择，结果在有限步内收敛（最多 $n$ 步，$n$ 为信号维度）
缺点	每步需要解一个最小二乘问题（涉及矩阵求逆），计算量比 MP 大

2.5 MP vs OMP 对比

维度	MP	OMP
正交性	只与最新原子正交	与所有已选原子正交
原子重复	可能重复	绝不重复
收敛步数	可能很多	最多 $n$ 步（有限）
每步计算	一次内积	内积 + 最小二乘
精度/步数比	较差	更优
适用场景	快速近似	需要精确或有限步收敛

---

字典训练算法：K-SVD

K-SVD 算法是 2006 年由以色列理工学院的 Michal Aharon、Michael Elad 等人提出，是一种非常经典的字典训练算法，并且达到了很好的训练效果。

1 基本思想

在稀疏编码中，除了稀疏表示外，另外一个重要工作就是过完备字典的训练。过完备字典质量的好坏对稀疏编码的结果有很大的影响。

K-SVD 算法主要分为两个步骤：稀疏表示与字典更新：

稀疏表示：对于目标信号集 $Y \in \mathbb{R}^{n \times N}$，初始化字典 $D \in \mathbb{R}^{n \times m}$，采用各类稀疏编码的求解算法来求解出系数矩阵 $X \in \mathbb{R}^{m \times N}$。

2 字典设计目标

$\min_{D, X} \|Y - DX\|_F^2 \quad \text{subject to} \quad \forall i, \|x_i\|_0 \leq T_0$

其中 $x_i$ 表示系数矩阵 $X$ 的第 $i$ 列，$T_0$ 是稀疏度约束。

3 字典更新

K-SVD 更新字典的方法为逐列更新字典，并且更新系数矩阵中相应行的非零项的值。当更新第 $k$ 列原子的时候，其它的原子固定不变。

假设当前更新的是字典 $D$ 中第 $k$ 列原子，将其表示为 $d_k$，其对应系数矩阵 $X$ 相应的第 $k$ 行，令其为 $X_k^T$。那么样本矩阵与字典表示之间的误差可以表示为：

$\|Y - DX\|_F^2 = \left\|Y - \sum_{j=1}^m d_j X_j^T\right\|_F^2 = \left\|\left(Y - \sum_{j \neq k} d_j X_j^T\right) - d_k X_k^T\right\|_F^2 = \|E_k - d_k X_k^T\|_F^2$

其中 $E_k = Y - \sum_{j \neq k} d_j X_j^T$ 是去掉第 $k$ 个原子贡献后的残差。

依据误差最小原则，对误差项 $E_k$ 进行 SVD 分解：

$E_k = U \Sigma V^T$

选择使误差最小的分解项作为更新的字典原子和系数矩阵 $X$ 中对应的原子系数。具体地，取 $U$ 的第一列作为新的 $d_k$，取 $\Sigma_{11} V_1^T$ 作为新的 $X_k^T$，经过不断的迭代从而得到最优化的解。

---

总结

• 最小 $\ell_2$ $\to$ 快速、唯一，但稠密 $\to$ 适合无稀疏需求、计算优先的场景。
• 最小 $\ell_0$ $\to$ 稀疏、可解释，但难算 $\to$ 适合压缩、特征提取。
• 带噪声的 $\ell_0$ $\to$ 真实世界的稀疏逼近模型，平衡误差与稀疏性。
• MP/OMP $\to$ 贪婪算法，快速求解稀疏编码的近似解。
• K-SVD $\to$ 经典字典训练算法，通过交替优化获得高质量过完备字典。

在实际工程中，几乎不会直接求解 $\ell_0$ 问题，而是用 $\ell_1$ 松弛（如基追踪去噪 BPDN）或贪婪近似（如 OMP），在稀疏性与计算效率之间取得折中。同时，字典的质量至关重要，K-SVD 及其变种是获取数据驱动字典的主流方法。