2.3.2 字典学习
由于冗余字典中原子个数可远高于信号长度，因此可从字典中寻找原子的最佳线性组合来逼近信号，获得稀疏的表示系数。但是在冗余字典表示中，表示并不是唯一的。例如，图2-5中，x=［3 2 0 0］T也是一个可行的稀疏解。因此，要获得基于冗余字典的稀疏表示，需要解决两个方面的问题：一是给定一组目标信号，如何获得最佳的原子，并构造得到字典，即字典设计问题；二是对于任意一个信号，如何从这个字典中挑选出最优的一种原子组合来表示信号，即原子选择问题。
1. 字典设计
字典设计需要解决的问题是如何设计字典D，使得对于给定的一系列信号{yi，i=1，2，…，N}，利用y=Dx得到的表示x是稀疏的。当前，主流字典设计方法可以大致归结为以下两类[8]：
·第一类方法：分析法。根据信号的先验知识来构建字典，如傅里叶、DCT、小波、曲波、带波、仿型波、复小波、方向波、组波等。用分析法构建字典相对简单，且结构特征明显，计算量小。然而，使用该类方法需要有一定的信号先验知识[9]。
·第二类方法：学习法。这种方法无须信号先验信息，直接对信号样本进行训练得到字典。相比分析法，学习法得到的字典可带来更好的信号匹配度，得到更优的稀疏化效果。
由于分析法需要先验知识，对于成分复杂的信号或时变信号，无法保证较好的稀疏化效果。因此，目前更多地采用学习法进行字典构造。
对于一系列待训练信号{yi，i=1，2，…，N}，字典学习的目标是通过训练寻找字典D，使得字典原子与训练信号相适应，从而使得信号在其上的分解系数xi尽量稀疏。若将待训练信号和分解系数分别组成矩阵Y，X，上述问题可表示为
式中，ε表示逼近误差。如果采用稀疏效果作为约束条件，则字典学习问题还可表述为
若将约束条件抽象化，更一般地可将式（2-4）记为
式中，G（X）表示训练过程中对分解系数X的约束条件。
2. 原子选择
原子选择需要解决在给定冗余字典D的条件下，从满足y=Dx的多种可能表示x中找到最优的表示，这里的最优通常指的是最稀疏的，也就是在表示y时，用到的原子数最少。
由于D的行数N远小于列数M，y=Dx的求解属于欠定方程组求解问题，一般情况下无法得到确定解。然而基于信号稀疏的前提，该问题可以转化为稀疏约束条件下的优化问题：
即满足约束条件的lp范数（p≥0）最稀疏矢量为最优解。
在lp范数稀疏的约束下寻找方程组的解，可看作求解矢量所在的超平面与lp范数张成的曲面的交点，且交点应位于坐标轴上以保证解最为稀疏。此处超平面不与任意坐标平面平行。如图2-3所示，当p=0时，超平面与退化后的曲面形成的切点易落在坐标轴上，因此加入l0范数稀疏的约束可以实现信号重构；类似地，对于0<p≤1的情况，超平面和曲面都容易寻找到落在坐标轴上的切点，因此在这些稀疏约束下都能找到式（2-6）的解；当p>1时（例如p=2），曲面是“凸”的，超平面与曲面的切点以绝对的大概率不落在坐标轴上，因此无法保证估计到稀疏信号。综合起来，当0≤p≤1时，在lp范数稀疏的约束下都可以对欠定方程组进行求解，进而得到稀疏解。
由于采用信号的非零元素个数（即l0范数）判断其稀疏性最为直观，研究者最初选择l0范数约束对欠定方程进行求解。然而，这需要列出x中所有非零项位置的
种可能的线性组合，才能得到最优解。因此采用l0范数求解式（2-4）属于NP难问题[10]。若选择0<p<1，由lp范数的定义，计算较为复杂，因此更多地考虑采用l1范数约束进行求解。
许多算法都利用了l1范数最小来求解最稀疏解的思想，它们属于凸松弛算法类别，基追踪（Basis Pursuit，BP）算法是其代表，有效性已得到了充分的理论证明[11]，但其全局搜索策略的计算复杂度较大，人们进而考虑采用贪婪算法来求解局部最优。这种思想促生了匹配追踪（Matching Pursuit，MP）算法[1]及其一系列改进算法，如正交匹配追踪（Orthogonal Matching Pursuit，OMP）[12]等。另一种贪婪算法的求解思路是对信号进行结构化采样，由分组测试快速获得信号的表示，如子空间追踪（Subspace Pursuit，SP）、迭代硬阈值法（Iterative Hard Thresholding，IHT）[13]等就是其中的代表。这类算法在计算复杂度上较凸优化算法低，然而在理论完备性上还有所欠缺[14]。图2-6给出了已有原子选择算法比较详细的分类。
图2-6 原子选择算法分类
作为一种典型的自然信号，声音信号中也包含着大量冗余。如何通过字典学习找到语音、音频信号的稀疏表示，也引起了很多研究人员的关注。例如，文献［15］结合稀疏多尺度改进型DCT（MDCT）对音频进行建模，降低了编码比特率；文献［16］用特定源字典对音乐进行稀疏分解，实现了乐-噪分离；文献［17］结合语音信号设计了贪婪自适应字典训练方法，实现了语音增强。随着研究的推进，利用冗余字典对语音进行稀疏表示将在更多的应用中发挥作用。