第十四讲 · 稀疏表示 | L.D.J 的私家工坊

稀疏表示相信一个朴素原则：复杂观测往往能由少量基本模式组合出来。人脸图像虽然有成千上万个像素，但一张测试脸可能只需要同一个人的少数训练照片就能近似重构。

把训练样本或可学习的基本模式排成矩阵 $D$ ，稀疏表示写成

y\approx D\alpha,

其中 $D$ 是字典， $\alpha$ 是编码。关键要求是 $\alpha$ 中绝大多数元素为零。

一、字典、原子与过完备表示

字典

D=[d_1,d_2,\ldots,d_n]\in\mathbb R^{m\times n}

的每一列 $d_j$ 称为一个原子。若 $n>m$ ，原子数多于信号维数，字典是过完备的：同一个 $y$ 往往有无穷多组系数能满足 $D\alpha=y$ 。

过完备看似制造歧义，实际却提供灵活性。稀疏约束从无穷多解中选出只使用少数原子的简单解释。

课件在人脸识别中直接用全部训练图像作为字典

A=[A_1,A_2,\ldots,A_K],

其中 $A_i$ 收集第 $i$ 个人的训练脸。若测试脸 $y$ 属于第 $i$ 类，并且该类样本近似位于一个线性子空间，则 $y$ 应主要由 $A_i$ 中的列重构，完整系数向量自然只在第 $i$ 类对应位置非零。

二、为什么最小二乘通常不稀疏

欠定方程 $D\alpha=y$ 的最小 $L_2$ 范数解为

\hat\alpha_2 =\arg\min_\alpha\lVert\alpha\rVert_2 \quad\text{s.t.}\quad D\alpha=y.

它可由伪逆求得，但 $L_2$ 倾向于把能量平摊给很多原子，结果通常是稠密的。要直接要求非零元素最少，可以写

\hat\alpha_0 =\arg\min_\alpha\lVert\alpha\rVert_0 \quad\text{s.t.}\quad D\alpha=y,

其中 $\lVert\alpha\rVert_0$ 表示非零元素个数。这个组合优化一般是 NP-hard，穷举所有原子子集代价极高。

课件用“非零元素少于 $m/2$ ”帮助建立唯一解直觉。更严格地说，唯一恢复界依赖字典的 spark、互相干性或受限等距性质，不能只凭信号维数 $m$ 判断；字典列越相似，区分真正使用了哪个原子就越困难。

三、用 $L_1$ 近似稀疏计数

常用凸替代是基追踪（Basis Pursuit）：

\hat\alpha_1 =\arg\min_\alpha\lVert\alpha\rVert_1 \quad\text{s.t.}\quad D\alpha=y.

$L_1$ 单位球有尖角，线性约束更容易在坐标轴附近与其相切，所以解更容易出现零元素。满足一定稀疏度与字典条件时， $L_1$ 解可以恢复 $L_0$ 的最稀疏解。

现实中有噪声，可改为基追踪去噪：

\min_\alpha\lVert\alpha\rVert_1 \quad\text{s.t.}\quad \lVert D\alpha-y\rVert_2\le\varepsilon,

对适当匹配的误差上限 $\varepsilon$ 与惩罚系数 $\lambda$ ，约束形式与下面的 Lasso 形式可以得到对应的解；这不是说任意同取一组参数都会无条件等价：

\min_\alpha \frac12\lVert D\alpha-y\rVert_2^2 +\lambda\lVert\alpha\rVert_1.

$\lambda$ 越大，编码通常越稀疏，但重构误差也可能增加。

四、匹配追踪：贪心地挑原子

$L_1$ 优化是全局凸优化，另一条路线是贪心选择。

匹配追踪（Matching Pursuit，MP）从残差 $r_0=y$ 开始，每轮选与当前残差最相关的原子：

j_t=\arg\max_j |d_j^{\mathsf T}r_{t-1}|,

随后沿该原子更新系数和残差。正交匹配追踪（Orthogonal Matching Pursuit，OMP）会在已选原子集合上重新做一次最小二乘，让新残差与所有已选原子正交。

OMP 的流程是：选原子 → 加入支持集 → 在支持集上重估全部系数 → 更新残差，直到达到目标稀疏度或残差阈值。它速度快，但贪心早期选错原子后不一定能恢复。

五、字典学习：原子也可以从数据中学

若没有合适的固定字典，可以同时学习字典和编码：

\min_{D,A} \lVert X-DA\rVert_F^2 \quad\text{s.t.}\quad \lVert\alpha_i\rVert_0\le s,

其中 $X$ 的每一列是训练样本， $A$ 的每一列是对应稀疏编码。通常交替优化：

固定 $D$ ，用 OMP 或 $L_1$ 方法求每个样本的稀疏编码；
固定编码，更新字典原子；
重复直到重构误差稳定。

K-SVD 是典型算法：逐个选取字典原子，对只使用该原子的样本残差做低秩 SVD，同时更新原子和相应系数。需要给字典列做单位范数约束，否则可以把 $D$ 任意放大、把 $A$ 任意缩小，表示会失去尺度唯一性。

本讲课件主体聚焦后面的稀疏表示分类；MP、OMP 与字典学习用于补全这一方法谱系。

六、稀疏表示分类 SRC

稀疏表示分类（Sparse Representation-based Classification，SRC）的标准流程如下。

1. 组成训练字典

A=[A_1,A_2,\ldots,A_K].

训练列和测试向量通常先归一化，避免亮度或整体幅值直接支配系数。

2. 求全局稀疏编码

\hat\alpha =\arg\min_\alpha\lVert\alpha\rVert_1 \quad\text{s.t.}\quad \lVert A\alpha-y\rVert_2\le\varepsilon.

3. 按类别重构

令 $\delta_i(\hat\alpha)$ 只保留第 $i$ 类系数，其余置零，计算

r_i(y)=\lVert y-A\delta_i(\hat\alpha)\rVert_2.

预测重构残差最小的类别：

\hat y=\arg\min_i r_i(y).

课件用“最大重构系数对应类别”解释直觉；实际 SRC 用逐类重构残差更稳健，因为同一类可能由多个中等系数共同表示。

一个二维例子

设第一类字典为

A_1= \begin{bmatrix} 1&0.8\\ 0&0.2 \end{bmatrix},

第二类字典为

A_2= \begin{bmatrix} 0&0.2\\ 1&0.8 \end{bmatrix},

测试样本 $y=(0.9,0.1)^{\mathsf T}$ 。有

y=0.5(1,0)^{\mathsf T}+0.5(0.8,0.2)^{\mathsf T},

所以一个稀疏解是 $\hat\alpha=(0.5,0.5,0,0)^{\mathsf T}$ 。第一类重构残差 $r_1=0$ ；只保留第二类系数后重构为零， $r_2=\lVert y\rVert_2\approx0.906$ ，因此判为第一类。

七、遮挡为什么也能写成稀疏项

若人脸被墨镜、围巾或随机像素污染，可写成

y=A\alpha+e,

其中 $\alpha$ 在身份字典上稀疏，误差 $e$ 在像素位置上也可能稀疏。把单位矩阵加入字典：

y=[A\ I] \begin{bmatrix} \alpha\\e \end{bmatrix},

再对联合系数做 $L_1$ 优化，便可同时估计身份表示和被污染位置。课件展示了 $30\%$ 、 $50\%$ 、 $70\%$ 随机污染以及块遮挡实验，并对比 $L_1$ 与 $L_2$ ： $L_2$ 会把局部大误差扩散到许多系数， $L_1$ 更能把它隔离成稀疏异常。

但鲁棒性不是无限的。遮挡过大、训练姿态覆盖不足或不同人的子空间高度重叠时，稀疏恢复条件会失效。

课件还比较了 Eigen、Laplacian、随机投影、下采样与 Fisher 等特征。在 Yale B 与 AR 数据的历史实验中，理论估计可恢复稀疏系数的最低特征维数分别约为 128 和 88，实验趋势与之接近；另一个实验使用 1207 张训练脸，展示 SRC 在特征维度高于样本数时仍可工作。这些数字说明“维度够用后不同特征差距可能缩小”，而不是保证所有数据上都存在固定的 128 或 88 维阈值。

八、SRC、最近邻与最近子空间

最近邻（NN）只找一个最相似训练样本；当训练数据密到一个样本就能表示测试脸时，SRC 近似退化为 NN。
最近子空间（NS）允许用某一类全部样本线性组合；当正确类子空间足够准确时，SRC 与 NS 接近。
SRC 在全字典上先做稀疏选择，可以避免某一类用所有样本过度拟合，并利用不同类别之间的竞争提高判别性。

若最小残差仍很大，或系数分散到许多类别，可拒绝识别，而不是强行输出训练集中某个人。课件的开放集实验中只有一半测试身份在训练集出现，正是在检验这一点。

九、常见误区与 sanity check

$\lVert\alpha\rVert_0$ 不是数学意义上的范数，它只是非零元素计数。
稀疏不等于系数绝对值都很小，而是大多数系数恰为零或接近零。
求出稀疏系数后，SRC 应比较逐类重构残差，不能只看单个最大系数。
字典列应做尺度归一化；否则范数大的原子可能用很小系数占便宜。
噪声容忍阈值 $\varepsilon$ 或正则强度 $\lambda$ 必须与噪声尺度匹配。
课件“特征选择不重要”的结论有条件：只有稀疏可恢复、维数足够且类别子空间可分时才成立，不能理解成任意糟糕特征都一样好。

第十四讲 · 稀疏表示