基于PCA的快速字典学习算法研究

王莲子 庄晓东 李钟晓 陈倩倩

摘要：  针对传统K奇异值分解（K-singular value decomposition，K-SVD）算法在训练中存在运行时间过长的问题，本文将主成分分析（principal component analysis，PCA）与K-SVD算法相结合，提出一种基于PCA的快速字典学习算法。该方法对原信号进行PCA降维，获取其主要成分，并对主成分信息进行字典学习，同时利用主成分字典作正交变换获取原信号字典。为验证本方法的有效性，采用快速字典学习算法对语音信号进行处理。研究结果表明，与传统K-SVD算法相比，基于PCA的快速字典学习算法在运行上时间减少了近1/2。新算法通过消除训练样本的冗余信息，使样本结构更加紧凑，极大程度降低了学习复杂度，在保证稀疏表示可靠性的同时，提升了字典学习效率，具有较好的应用前景。

关键词：  PCA; 快速字典学习; 稀疏表示; K-SVD

中图分类号： TN912.3  文献标识码： A

2006年，D.L.Donoho等人[1] 提出的压缩感知为信号处理技术带来了革命性突破。以远低于奈奎斯特频率对信号进行采样，不仅简洁而有效的表示信号，还降低实际应用中庞大数据量所带来的压力，在理论数学、信号处理、图像与视频处理等方面得到广泛应用[2 4] 。压缩感知的前提及基础是信号必须具有稀疏性，因此，构造合适的字典，从而实现信号的最优稀疏表示是压缩感知中较为关键的一个阶段。根据构造方式，字典可分为固定字典和训练字典。固定字典实现简单，但原子形态单一，应用范围较为局限。K.Engan等人[5] 提出最优方向（method of optimal directions，MOD）算法，是一种经典字典学习算法，因在训练字典中大量使用最小二乘，使字典学习消耗较长时间;M.Aharon等人[6] 提出了K奇异值分解（K-singular value decomposition，K-SVD）算法，与MOD算法相比，其计算复杂度有所降低，因此K-SVD算法逐渐成为研究热点，但训练时间过长仍是K-SVD算法存在的主要问题。虽然许多学者对K-SVD算法进行了改进[7 9] ，但大多数改进仅对K-SVD中的稀疏表示以及字典更新阶段的改进，却忽略了由训练目标本身所带来计算量过大的问题，随着待处理数据增多，训练复杂度逐渐增加，通过减少字典学习的训练量，可有效提升训练速度。字典学习的本质是信号特征的针对性训练，要在保留信号主要特性的同时减少训练目标量，往往涉及一些数据降维技术。余付平等人[10 12] 的研究结果表明，PCA与字典学习及稀疏表示有效结合，在误差重构方面具有明显效果，但上述研究并没有解决字典学习中计算复杂度较高的问题。基于此，本研究将PCA与K-SVD字典学习算法相结合，提出了一种基于PCA的快速字典学习算法，从根本上解决了字典学习中训练量过大的问题。实验结果表明，与传统字典学习算法相比，该方法在字典学习中具有较高运算效率。该研究具有广阔的应用前景。

1 字典学习与PCA

1.1 稀疏表示与字典学习

大多数信号本身不具备稀疏特性，只有在字典下才能稀疏表示，信号 y ∈ R （n×m） 的稀疏表示模型[13 15] 为

y = DC  （1）

其中， D =[ d1 d2 … ds ]， D ∈ R （n×s） 是一组具有S个原子的字典，每个原子的矢量长度为n; C ∈ R （s×m） 是信号 y 在字典 D 上展开的系数。常用的稀疏求解方法有正交匹配追踪（orthogonal matching pursuit，OMP）算法和匹配追踪（matching pursuit，MP）算法等，为获取较快的收敛速度，本研究选择OMP算法作为稀疏求解方法[16] 。

K-SVD是一种经典的字典学习算法，K-SVD将数据矩阵 y 分解为具有符合数据特性的字典 D 以及稀疏系数矩阵 C ，其分解过程[17 19] 为

argmin  D ， C ‖ y - DC ‖2F （2）

K-SVD是一种迭代算法，字典学习过程主要分为两部分，一是固定当前字典，利用稀疏求解算法获取稀疏系数;二是利用稀疏系数来更新下一次迭代字典。当达到误差要求，或者一定迭代次数时，输出字典即所需学习字典。

1.2 PCA技术

PCA是一种重要的数据降维方法，利用正交变换将原始向量组转变成一组线性不相关向量，变换后向量组保留了原始数据的主要成分，有效消除原始信号冗余信息，在更小维度下展示数据特性。PCA算法的主要步骤[20 22] 如下：

1） 首先对信号 y （n×m） ={y1，y2…ym}进行中心化，得到中心化矩陣  。

2） 对  的协方差矩阵进行特征值分解。

3） 取前t个最大特征值对应的特征向量，并将其标准化后组成特征矩阵 W ={W1，W2…Wt}。

4） 得到后数据 y′ = W T  ，其中 y′ ∈ R （t×m） 。

2 基于PCA的快速字典学习算法

在字典学习中，信号常以一组线性相关向量组形式处理，待处理信号一般具有冗余性。在利用K-SVD算法构造字典中，稀疏表示阶段的最优解问题以及字典更新阶段的奇异值分解，都具有较高计算量，随着训练样本不断增加，计算复杂度也逐渐增大。对训练样本中冗余成分进行学习，不仅降低训练效率，也增加一定资源浪费。因此，消除冗余信息的字典学习，可以有效提升字典学习效率。字典学习是针对原始信号特征进行训练，而通过PCA提取到原始信号的特征能较好满足字典学习的特征需要，对具有冗余性的信号进行降维，在保证不丢失原始信号重要特性情况下，消除了冗余信息。针对上述问题，本文将PCA与K-SVD字典学习算法相结合，提出了一种基于PCA的快速字典学习算法，通过消除训练样本冗余信息，解决字典学习过程中训练集计算量大的问题，极大提高了字典学习效率。基于PCA的快速字典学习算法首先对原信号进行主成分分析，获得矢量长度较小，代表重要信息的主成分矩阵，将主成分矩阵作为训练样本，得到主成分字典，利用正交变换求得原始信号学习字典。

原始信号矩阵为 y （n×m） ，利用PCA技术，设置最佳主成分阈值λ，获得主成分矩阵 y′ ∈ R （t×m） ，通过对主成分矩阵进行字典学习，得到主成分字典 Dt 以及稀疏系数 Ct ，由文献[22]得

y′ = W T   （3）

经过对式（1）进行分析，主成分矩阵 y′ 可进行稀疏表示，现将式（4）与式（1）结合，得

y′ = W T  = DtCt  （4）

式中， W T∈ R （t×n） 是  协方差矩阵的特征矩阵。为获取能表征原始信号特性的字典，现处理为

（ W T）T（ W T）  =（ W T）T DtCt  （5）

由于 W T为单位正交矩阵，（ W T）T（ W T）为近似单位矩阵，则式（6）近似表示为

=（ W T）T DtCt = DC t （6）

因为 y′ 代表 y  主要特征; Dt 为 y′ 的学习字典，一定程度上也具有原信号结构特性。因此，将 Ct 作为原始信号临时稀疏系数，则（ W T）T Dt 表示为原始矩阵 y （n×m） 经过快速字典学习算法得到的训练字典 D ，并将 D 进一步与OMP算法相结合，取代临时稀疏系数 Ct ，得到原信号在字典 D 上的稀疏系数 C 。

研究结果表明，稀疏系数 C 有着较强的稀疏性，字典 D 有着较小的RMSE以及极快的运行速度。基于PCA的快速字典学习算法主要步骤如下：

输入：原始信号 y （n×m） 。

1） 对原信号 y （n×m） 进行PCA处理，获取主成分矩阵 y′ ∈ R （t×m） 。

2） 对主成分矩阵利用K-SVD进行字典学习，获取主成分字 Dt ，主成分稀疏系数 Ct 。

3） 固定主成分稀疏系数 Ct ，对 Dt 作正交变换，得原始信号字典 D =（ W T）T Dt 。

4） 利用OMP算法，得原始信号稀疏系数 C 。

输出：字典 D ，稀疏系数 C 。

3 语音信号快速字典学习仿真实验

基于PCA的快速字典学习算法首先对原始信号进行降维，选取合适主成分阈值，保留信号主要信息，减少计算维度，得到主成分矩阵。再利用K-SVD字典学习算法以及OMP稀疏表示算法对主成分信息进行字典学习，获主成分字典，对主成分字典正交变换，得到符合原始信号特性的训练字典。为验证本方法的有效性，现利用快速字典学习算法对语音信号进行稀疏处理。字典稀疏表示能力的强弱以及表示误差的大小反应了字典学习能力，为了更加客观分析字典的性能，本研究将稀疏性、均方根误差（root mean square error，RMSE）和运行时间作为客观评价标准，现将稀疏性进行定量处理，稀疏性度量K的计算模型为

K= 1 m ∑ m i=1 ‖ Ci ‖1F （7）

式中， C ∈ R （s×m） 代表稀疏系数矩阵; Ci 表示第i列系数;‖ Ci ‖1F表示对第i列系数求解1范数。

3.1 获取主成分矩阵

本研究运行环境为windows7，运行软件为matalba2014b，采用的样本数据及测试数据是在安静环境下录制，语音信号采样频率为16 kHz，因语音具有短时平穩性，现对语音进行分帧处理，帧长128 ms，帧移32 ms。将语音数据 y ∈ R （n×m） 进行PCA降维，选择主成分阈值λ，得到主成分矩阵 y′ （t×m） （t

由表1可以看出，随着主成分阈值λ增大，主成分矩阵矢量长度也逐渐增大。降维后，矩阵的矢量长度最少可为原始信号矢量长度的1/7，且至少包含原始信号97%以上的信息。由此可见，主成分矩阵以较小矢量长度占据了原始信号的主要信息。快速字典学习算法再以主成分矩阵为训练目标，学习主成分字典，而在字典训练过程中，主成分矩阵的矢量长度越大，字典训练效率越低。因此，选择合适主成分阈值，可以使主成分矩阵在能保证信号主要结构特征的同时，极大提升字典学习效率。

3.2 最佳主成分阈值选取

将主成分矩阵 y′ 作为字典学习训练样本，获其主成分字典，对主成分字典按式（6）正交变换，一定程度上保证了字典稀疏表示能力，得到与原始信号特性相符的学习字典。实验对多个音素进行测试，比较λ在（97，99.5）范围内，快速字典学习算法的运行时间、RMSE及稀疏性度量K。语音信号在不同λ下，运行时间随主成分阈值的变化曲线如图1所示，均方根误差随主成分阈值的变化曲线如图2所示，稀疏性度量随主成分阈值的变化曲线如图3所示。由图1～图3可以看出，主成分阈值λ越大，主成分矩阵包含的主要信息 越多，即越接近原始信号;同时，主成分矩阵的矢量长度也随之增大，参与训练样本维数增加，导致主成分矩阵在字典学习中的存储空间与计算量增加，运行时间也随之增加;当提取到的主成分矩阵逐渐接近原始信号时， 由快速字典学习算法训练得到字典的RMSE逐渐减小;在稀疏性方面，主成分阈值λ的增大，展开系数的稀疏性度量K保持在一个相对稳定的数值，受阈值变化影响较小，稀疏展开效果较为稳定。因此选择合适的主成分阈值，可以使主成分矩阵在既包含主要信息的同时，又具有较小的矢量长度，在保证一定的RMSE及稀疏性的同时，又具有较快运行速度，使新方法具有更加明显的效果。

为使快速字典学习算法在多方面具有较好处理效果，现对语音音素[a]，[h]，[i]在主成分阈值λ为97%，97.5%，98%，98.5%，99%和99.5%条件下的RMSE、运行时间和稀疏性三个性能进行综合分析。针对不同信号，采用主成分分析法作为多个性能综合评价的分析方法，获取在不同主成分阈值下快速字典学习方法性能的综合得分，选择具有最高综合得分的阈值，并以此阈值λ作为此信号在快速字典学习算法中的最佳主成分阈值。

3.3 仿真结果分析

根据3.2选出最佳主成分阈值，采用基于PCA的快速字典学习算法对语音信号进行稀疏处理， 从RMSE、运行时间和稀疏性K多个方面与K-SVD算法进行分析比较，将发音信号[a]，[h]，[i]在基于PCA的快速字典学习算法与K-SVD算法下的性能进行对比，语音音素在两种算法下的学习性能对比如表2所示。

由表2可以看出，与K-SVD算法相比，基于PCA的快速字典学习算法在运行时间上减少了近1/2，这是因为利用快速字典学习算法处理信号时，参与字典学习的主成分矩阵以更小矢量长度代表原始信号主要信息，则训练样本结构特性更加紧凑，一定程度上减少了冗余信息的字典训练，使字典学习的稀疏表示阶段及原子更新阶段的计算复杂度得到大幅度减少，避免了训练样本在字典学习中由维数过多而引发运行时间过长的问题，使字典学习计算速度得到极大提升。利用PCA获取的主成分矩阵，在至少包含97%原始信息情况下，作为训练样本学习主成分字典，通过正交变换构造有稳定稀疏展开的原始信号字典，且其RMSE与K-SVD算法相比，均保持在同一数量等级，在保证字典稀疏表示可靠性的同时，极大提升了字典学习效率。

4 结束语

针对传统字典学习算法中运算时间过长的问题，提出了一种基于PCA的快速字典学习算法。选择最佳主要成分阈值，利用PCA对原信号进行处理，对主成分矩阵进行训练，对主成分字典进行字典变换处理，得到与原始信号结构相适应的学习字典。 与K-SVD算法的定性和定量实验表明，基于PCA的快速字典学习算法极大降低了计算复杂度，在保留原始信号重要特性情况下，消除冗余信息的字典学习，提高字典运行速度。

参考文献：

[1] Donoho D L. Compressed sensing [J]. IEEE Transactions on Information Theory， 2006， 52（4）： 1289 1306.

[2] 金卯亨嘉. 压缩感知中字典学习算法的研究及应用[D]. 天津： 天津大学， 2014.

[3] 尹宏鹏， 刘兆栋， 柴毅， 等. 压缩感知综述[J]. 控制与决策， 2013， 28（10）： 1441 1445， 1453.

[4] 石光明， 刘丹华， 高大化， 等. 压缩感知理论及其研究进展[J]. 电子学报， 2009， 37（5）： 1070 1081.

[5] Engan K， Aase S O， Husoy J H. Method of optimal directions for frame design[C]∥IEEE International Conference on Acoustics. IEEE， 1999， 5： 2443 2446.

[6] Aharon M， Elad M， Bruckstein A M.The K-SVD： an algorithm for designing of over complete dictionaries for sparse representation [J]. IEEE Transactions on Signal Processing， 2006， 54（11）： 4311 4322.

[7] Rubinstein R， Zibulevsky M， Elad M. Efficient implement-tation of the K-SVD algorithm using batch orthogonalmatching pursuit[J]. CS Technion， 2008， 40（8）： 1 15.

[8] Smith L N， Elad M. Improving dictionary learning： Multiple dictionary updates and coefficient reuse[J]. IEEE Signal Processing Letters， 2013， 20（1）： 79 82.

[9] 袁超， 李海洋. 基于TL1范數的改进 K-SVD 字典学习算法[J]. 计算机与数学工程， 2017， 45（12）： 2327 2331， 2363.

[10] 余付平， 冯有前， 范成礼， 等. 基于主成分分析的字典学习[J]. 控制与决策， 2013， 28（7）： 1109 1112.

[11] 首照宇， 吴广祥， 张彤. 基于PCA子字典学习的图像超分辨率重建[J]. 计算机工程与设计， 2015， 36（11）： 3025 3029.

[12] 霍雷刚， 冯象初. 基于主成分分析和字典学习的高光谱遥感图像去噪方法[J]. 电子与信息学报， 2014， 36（11）： 2723 2729.

[13] 刘振， 姜晖， 王粒宾. 基于稀疏表示的SAR图像目标识别方法[J]. 计算机工程与应用， 2014， 50（10）： 212 215， 232.

[14] 王凡， 王屹， 刘洋. 利用结构化和一致性约束的稀疏表示模型进行红外和可见光图像融合 [J]. 信号处理， 2020， 36（4）： 572 583.

[15] 鄭思龙， 李元祥， 魏宪， 等. 基于字典学习的非线性降维方法[J]. 自动化学报， 2016， 42（7）： 1065 1076.

[16] 莫长鑫， 毕宁. OMP算法对稀疏信号准确重构的一个充分条件[J]. 复旦学报： 自然科学版， 2019， 58（1）： 19 24.

[17] 鲍光照. 基于稀疏表示与联合字典学习的语音增强算法研究[D]. 合肥： 中国科学技术大学， 2015.

[18] 郭欣. 基于K-SVD稀疏表示的语音增强算法[D]. 太原： 太原理工大学， 2016.

[19] Zhou Y， Zhao H， Shang L， et al. Immune K-SVD algorithm for dictionary learning in speech denoising[J]. Neurocomputing， 2014， 137（15）： 223 233.

[20] 赵鑫， 汪维家， 曾雅云， 等. 改进的模块PCA人脸识别新算法[J]. 计算机工程与应用， 2015， 51（2）： 161 164， 175.

[21] 董恩增， 魏魁祥， 于晓， 等. 一种融入PCA 的LBP特征降维车型识别算法[J]. 计算机工程与科学， 2017， 39（2）： 359 363.

[22] 董航. 基于PCA字典和两阶段优化的非凸压缩感知重构[D]. 西安： 西安电子科技大学， 2013.

A Fast Dictionary Learning Algorithm Based on PCA

WANG Lianzi， ZHUANG Xiaodong， LI Zhongxiao， CHEN Qianqian

（College of Electronic Information， Qingdao University， Qingdao 266071， China）

Abstract：  A fast dictionary learning algorithm based on PCA is proposed to solve the problem that the K-SVD algorithm runs too long in dictionary training. In this method， PCA is used to reduce the dimension of speech signal to obtain its main components and the dictionary of original signal is acquired by taking orthogonal transformation in the components dictionary which is learned by main components. In order to verify the effectiveness of this method， a fast dictionary learning algorithm is used to process speech signals. The results show that， compared with K-SVD algorithm， the fast dictionary learning algorithm reduces the running time by nearly half. By eliminating redundant information of training samples， the sample structure is more compact and the learning complexity is greatly reduced. The new method not only guarantees the reliability of sparse representation but also improves the efficiency of dictionary learning， and has a strong application prospect.

Key words： PCA; fast dictionary learning; sparse representation; K-SVD