一种改进的K-SVD字典学习算法

刘雅莉，马 杰，王晓云，苑焕朝

（1.河北工业大学 电子信息工程学院，天津300401；2.天津市电子材料与器件重点实验室，天津市300401）

一种改进的K-SVD字典学习算法

刘雅莉1,2，马 杰1,2，王晓云1,2，苑焕朝1,2

（1.河北工业大学 电子信息工程学院，天津300401；2.天津市电子材料与器件重点实验室，天津市300401）

提出了一种ALM-KSVD字典学习算法，通过稀疏编码和字典更新两步迭代学习得到训练样本的字典．为了提高字典训练速度与性能，在稀疏编码引入增广拉格朗日乘子法（ALM，Augmented LagrangeMultipliers）求解，更新字典则使用经典K-SVD的字典更新算法．为考察算法的字典训练速度和平均表示误差（RMSE），选取了不同样本数和噪声标准进行数据合成实验，结果表明本文算法比经典的K-SVD算法字典训练速度快、RMSE低．进一步考察算法的图像去噪能力，选取不同的输入图像噪声标准和字典原子数进行仿真，实验结果表明本文算法比经典的K-SVD算法获得更高的峰值信噪比（PSNR），具有良好的去噪性能．

字典学习；K-SVD；稀疏编码；增广拉格朗日乘子法；ALM

0 引言

近年来信号的稀疏表示研究引起了越来越多的关注[1-2]．为了实现信号的稀疏表示，给定一组训练信号，使用一个包含信号信息的字典，信号由少量的字典原子线性组合表示．字典可以通过预先定义的一组基函数（DCT基、Gabor基等）产生，也可以通过某种算法学习得到．学习型字典能够自适应的根据训练样本构造基函数，而且稀疏重构误差小于固定基字典．1996年Olshausen等[3]在《Nature》上发表了著名的Sparsenet字典学习算法，该算法奠定了字典学习的基础．Engan等[4]对Olshausen的字典学习算法进行了改进，提出了MOD（Method ofoptimaldirections）字典学习算法，并将其应用在语音数据和心电图数据重构上，取得了良好效果．为减小MOD算法的复杂度，Elad等5在2006年提出了K-SVD（K-singular value decomposition）算法，实现了基于K-SVD字典学习的填写缺失像素、压缩及图像去噪、修复等．K-SVD字典学习是1种迭代算法，固定当前字典进行稀疏编码求解稀疏系数，根据稀疏系数对字典的列进行迭代更新，字典列的更新结合稀疏表示一个更新，从而加速收敛．在稀疏编码求解稀疏系数时，在当前固定字典下是1个NP难问题6．一种简单的方法是使用贪婪追踪算法，如匹配追踪（MP，Matching Pursuit）或正交匹配追踪（OMP，Orthogonal Matching Pursuit）[7-8]等，直接求解l0范数问题．另一种方法是使用l1范数近似代替l0范数,如基追踪（BP，Basis Pursuit）[9]及其变形FOCUSS[10]，LARS-Lasso[11]等．经典K-SVD字典学习在实际中应用最广，许多学者对其进行了改进．Rubinsteind等[12]在稀疏编码步骤中采用Batch-OMP（Batch-OrthogonalMatching Pursuit）替代OMP（Orthogonal Matching Pursuit)，比经典K-SVD字典训练效率更高，但图像去噪效果却有所下降．Smith等[13]在字典更新中加入支撑完整的先验信息，提出了多重字典更新（DUC，Dictionary UpdateCycles）算法，有效地减小了字典学习的目标函数，提升了字典训练速度与性能．

前面提到的稀疏表示问题涉及到了最小化l1范数问题，最小化l1范数往往涉及软阈值截取运算（Softthresholding）[14]．具体的算法包括加速近似梯度算法（APG，Accelerated ProximalGradient）[15]、交替方向乘子法（ADMM，Alternating Direction Method of Multipliers）[16]、Bregman迭代法[17]和增广拉格朗日乘子法（ALM，Augmented LagrangeMultiplier）[18]等．Honglak等[19]在求解字典更新时采用拉格朗日对偶算法，加快了收敛速度．Adler[20]等在稀疏编码异常检测时引入交替方向乘子法（ADMM）求解，充分利用ADMM使目标函数可分离的结构特点，对其中两项交替求最小化，该算法与增广拉格朗日乘子法类似．增广拉格朗日乘子法（ALM，Augmented Lagrange Multipliers）[17-18]经研究证明，该算法比其他算法收敛速度快，而且可以达到更高的精度，同时需要较低的存储空间．当前字典学习特别是K-SVD方法存在的主要问题是字典训练时间长，计算量大．针对这一问题，为提高字典学习的收敛速度与性能，本文提出一种ALM-KSVD字典学习算法．在稀疏编码引入速度快的增广拉格朗日乘子法（ALM）求解，更新字典则使用经典K-SVD的字典更新，通过稀疏编码和字典更新两步迭代学习得到字典．

1 稀疏表示模型

稀疏表示模型[21]是假设1个信号可以描述为y Dx，其中是1个字典，是稀疏

的．因此，y被D的一些原子的线性组合表示．稀疏表示的重构称为稀疏编码，其模型为

式中：‖x‖0是l0范数为x中非零的个数；T0是非零数目的最大值．问题 (1)可以被扩展到一个集合的信号

求解问题 (1)或 (2)的精确解是一个NP难问题，典型的做法是应用追踪算法寻找近似解．最简单的方法是使用贪婪追踪算法（如MP或OMP）直接求解l0范数，但是需要将原始信号内的元素逐一稀疏表示，而且重构时每次恢复都有微小的误差，信号重构质量差．Donoho等[22]提出利用l1范数代替l0范数，变成线性规划的凸优化问题，找出最稀疏的系数矩阵，这种方法称为松弛法．其模型为

式中：l1范数为x中非零元素的绝对值之和；T0是非零数目的最大值．问题 (3)也可以扩展到一个集合的信号

式中l1范数为X中非零元素的绝对值之和．解决问题 (3)和问题 (4)可以通过无约束凸优化问题近似求解，模型为转化为无约束凸优化求解l1范数问题．式中是一个很小的正数，表示权重的大小．

2 基于ALM-KSVD的字典学习

首先介绍增广拉格朗日乘子法（ALM），对于一个约束优化问题：

其中：f:RnR；h:RnRm．其增广拉格朗日函数为

2.1 稀疏编码

在该阶段，字典D固定，寻找训练样本Y在字典D上的稀疏系数X．贪婪算法的计算复杂度低，但是信号重构质量差．松弛法虽然比贪婪算法信号重构的质量好，缺点是计算复杂度较高，收敛速度慢．为了缩短稀疏编码时间，提高字典训练速度和性能，引入速度较快的增广拉格朗日乘子法（ALM）解决问题 (5)．加入辅助变量Z，无约束优化问题转化为有约束优化问题．问题 (5)转化为

其拉格朗日函数为

式 (10)是强凸函数，可以通过求解其偏微分函数来求解其最小值，解得

Zk+1的更新方式是固定最小化以下方程

式 (12)可以化简为

解得

其中Suf表示软阈值算子，定义如下

表1 基于ALM的稀疏编码的算法流程Tab.1 Flow chartof sparse coding based on ALM

2.2 字典更新

在该阶段应用经典K-SVD的字典更新[6]，根据稀疏系数X，对字典D中的原子进行迭代更新，字典列的更新结合稀疏表示的一个更新，使字典和稀疏系数同步更新．K-SVD字典学习的本质是范数的稀疏约束和奇异值分解（SVD）交替进行，字典学习过程可用优化问题表示

式中：‖xi‖0是l0范数计算xi中非零元素的个数，T0是非零元素个数的最大值．

综上，基于ALM-KSVD的字典学习算法的步骤如

表2 基于ALM-KSVD的字典学习Tab.2 Dictionary learning based on ALM-KSVD

3 实验结果及分析

实验中，利用CPU为2GHz，内存为2GB的计算机，通过MATLABR2010a仿真实现，取参数．对本文算法ALM-KSVD与经典K-SVD算法进行对比分析，采用字典训练时间、平均表示误差（RMSE）、峰值信噪比（PSNR）作为性能评价标准．

3.1 数据合成实验

为了检测本文算法的性能，首先使用仿真合成数据测试字典训练时间和平均表示误差（RMSE），并将其与经典K-SVD进行比较．应用文献 [6]中的实验，首先生成一组基，由M=50个维数为N=20的基向量组成，每一列都标准化．然后取L个数据信号组成样本集，每个信号由3个不同生成字典原子的线性组合表示，其稀疏系数的位置和值都是随机独立同分布的．对生成的信号加入等级SNR=30dB的高斯噪声，选取不同数目的样本集L，迭代50次．实验结果如表3和图1所示．

表3 不同样本集字典训练速度与RMSETab.3 The valuesof dictionary training speed and RMSE with differentsample sets

实验分析：本文算法比经典K-SVD算法字典训练速度快，当加入SNR=30dB的高斯噪声时本文算法RMSE比经典K-SVDS算法减0.01．图1表明样本集数目越大本文算法比经典K-SVD速度快体现的越明显，当选取L=62 001，本文算法比经典K-SVD算法快3倍．

接下来选取L=1500个数据信号，对生成的信号加入不同等级SNR=10 dB，20dB，30dB，40dB，50 dB的高斯噪声，迭代50次，测试结果如表4和图2所示．实验结果表明噪声在SNR=10dB，20dB，30 dB问题时本文算法和经典K-SVD算法的RMSE都减小了，而且本文算法RMSE比经典K-SVD算法小．从图2可以看到经典K-SVD算法在SNR=40dB，50 dB时RMSE又增大，而本文算法RMSE值变化不大，说明本文算法比经典K-SVD算法稳定性好，尤其是在小信噪比体现更明显．

表4 不同SNR值字典训练速度与RMSETab.4 The valuesof dictionary training speed and RMSE with different SNR SNR/dB

图1 字典训练速度的比较Fig.1 Comparison of dictionary training speed

3.2 图像去噪实例

为解决图像去噪问题，文献 [23]所采取的方法是使用稀疏和冗余表示训练字典，应用K-SVD算法获得一个字典有效地描述图像内容．为考察本文算法的去噪能力，进行了实验验证并与经典K-SVD算法比较．图3显示了5幅标准测试图像分别为“barbara”，“boat”，“lena”，“house”，“peppers”．对测试图像g （256×256）加入均值为0标准差为的噪声得到含噪图像I，从含噪图像中提取大小为8×8，L=62001的样本集．为保证公平初始字典都为 DCT，迭代5次，得到近似去噪值，并将其在恰当的位置进行加权平均取值得到输出图像 f．性能评级指标峰值信噪比（PSNR）定义为．

表5 5幅测试图像去噪结果Tab.5 The resultof five imagesaftervarious denoising tests

实验分析：比较本文算法和经典K-SVD算法在加入不同等级噪声时的去噪效果．表5显示了本文算法和K-SVD算法在噪声范围[5～100]之间得到的去噪结果，可以发现在大部分噪声等级下本文算法要比K-SVD好，获得较高的PSNR．算法在噪声=15时5幅测试图像输出PSNR平均值比经典K-SVD算法高0.26 dB．图4显示了在噪声=15时2种算法对“barbara”的去噪效果，只截取了图像一部分，算法明显比经典K-SVD算法效果好，去噪后得到的图像清晰．

图2 RMSE的比较Fig.2 Comparison of RMSE between ALM-KSVD and OMP-KSVD

图3 5幅用于测试的图片Fig.3 Five imagesused for variousdenoising tests

图4 去噪效果Fig.4 The image denoised

以上的实验结果是在字典原子个数M=256的情形下得到的，为进一步验证本文算法的有效性，对字典学习中的主要参数如字典大小进行实验验证．考察一下在噪声=15时不同字典原子数如64，128，256，512对去噪结果的影响．表6是不同字典大小的去噪结果比较，实验图像是“barbara”和“lena”，图5展示了其PSNR值．

表6 不同字典大小去噪结果Tab.6 The denoising resultof the dictionary w ith differentsizes

图5 不同字典大小去噪结果的PSNR值Fig.5 PSNR of the dictionaryw ith differentsizesafter denoising test

4 结论

本文提出了一种ALM-KSVD字典学习算法，在稀疏编码引入增广拉格朗日乘子法（ALM）求解，更新字典则使用经典K-SVD的字典更新，稀疏编码和更新字典两步迭代学习得到字典．本文算法提升了字典训练速度与性能，图像去噪实例结果表明与经典K-SVD算法相比，本文算法去噪效果更好．由于超完备字典的训练受诸多因素影响，且训练时间长，因此如何训练更快速、更有效地字典是下一步工作的内容．

[1]Dong Wei-sheng，Zhang Lei，ShiGuang-m ing，etal．Nonlocally centralized sparse representation for image restoration[J]．Image Processing，IEEE Transactionson，2013，22（4）：1620-1630．

[2]YANG Meng，ZhANG Lei，FENG Xiang-chu，et al．Fisher discrim ination dictionary learning for sparse representation[C]//Computer Vision （ICCV），2011 IEEE InternationalConferenceon．IEEE，2011：543-550．

[3]Olshausen BA，Field D J．Emergency ofsimple-cell receptive field propertiesby learning asparse code fornatural images[J]．Nature，1996，381 （6583）：607-609．

[4]Engan K，Aase SO，Hakon Husoy J．Method of optimal directions for frame design[C]//Acoustics，Speech and Signal Processing，1999．Proceedings．1999 IEEE InternationalConferenceon．IEEE，1999，5：2443-2446．

[5]Aharon M，Elad M，Bruckstein A M．The K-SVD：an algorithm for designing of over complete dictionaries for sparse representation[J]．IEEE Transactionson SignalProcessing，2006，54（11）：4311-4322．

[6]Donoho D L，Elad M，Tem lyakov V N．Stable recovery of sparseover complete representations in the presenceof noise[J]．Information Theory，IEEE Transactionson，2006，52（1）：6-18．

[7]MallatSG，Zhang Z．Matchingpursuitsw ith time-frequency dictionaries[J]．SignalProcessing，IEEETransactionson，1993，41（12）：3397-3415．

[8]Tropp J．Greed isgood：A lgorithmic results forsparseapproximation[J]．Information Theory，IEEETransactionson，2004，50（10）：2231-2242．

[9]Chen SS，DonohoD L，SaundersM A．Atomic decompositionbybasispursuit[J]．SIAM Journalon Scientific Computing，1998，20（1）：33-61．

[10]Gorodnitsky IF，Rao B D．Sparse signal reconstruction from limited data using FOCUSS：A re-weightedm inimum norm algorithm[J]．Signal Processing，IEEETransactionson，1997，45（3）：600-616．

[11]Efron B，Hastie T，Johnstone I，etal．Leastangle regression[J]．The Annalsof Statistics，2004，32（2）：407-499．

[12]RubinsteinR，Zibulevsky M，EladM．Efficientimplementationof theK-SVD algorithm usingbatchorthogonalmatchingpursuit[J]．CSTechnion，2008，40（8）：1-15．

[13]Sm ith LN，Elad M．Improving dictionary learning：Multipledictionary updatesand coefficientreuse[J]．SignalProcessing Letters，IEEE，2013，20（1）：79-82．

[14]戴琼海，付长军，季向阳．压缩感知研究 [J]．计算机学报，2011，34（3）：425-434．

[15]Beck A，TeboulleM．A fastiterativeshrinkage-thresholding algorithm for linear inverseproblems[J]．SIAM journalon imaging sciences，2009，2（1）：183-202．

[16]Yuan X，Yang J．Sparseand low-rankmatrix decomposition viaalternating directionmethods[J]．Pacific JournalofOptim ization，2009，9（1）．

[17]YinW，Osher S，Goldfarb D，etal．Bregman iterativealgorithms for1-m inim izationw ith applications to compressed sensing[J]．SIAM Journal on Imaging Sciences，2008，1（1）：143-168．

[18]Lin Z，ChenM，MaY．Theaugmented lagrangemultipliermethod forexactrecoveryofcorrupted low-rankmatrices[J]．EprintArxiv，2010，9．

[19]LeeH，BattleA，RainaR，etal．Efficientsparse codingalgorithms[C]//Advances in Neural Information Processing Systems．2006：801-808．

[20]Adler A，Elad M，Hel-Or Y，etal．Sparse codingw ith anomaly detection[C]//Machine Learning for Signal Processing（MLSP），2013 IEEE InternationalWorkshop on．IEEE，2013：1-6．

[21]Bruckstein AM，Donoho D L，Elad M．From sparsesolutionsofsystemsofequations to sparsemodelingofsignalsand images[J]．SIAM Review，2009，51（1）：34-81．

[22]Donoho D L．Formost largeunderdetermined systemsof linearequations them inimal1-norm solution isalso thesparsestsolution[J]．Communications on Pureand Applied Mathematics，2006，59（6）：797-829．

[23]Elad M，AharonM．Imagedenoising viasparseand redundantrepresentationsover learned dictionaries[J]．ImageProcessing，IEEETransactions on，2006，15（12）：3736-3745．

[责任编辑 代俊秋]

An improved K-SVD dictionary learning algorithm

LIU Yali1,2，MA Jie1,2，WANG Xiaoyun1,2，YUAN Huanchao1,2

(1.Schoolof Electronic and Information Engineering,HebeiUniversity of Technology,Tianjin300401,China;2.Key Laboratory of Tianjin Electronic Materialsand Devices,Tianjin 300401,China)

Animprovementof K-SVD dictionary learning algorithm has been proposed,through the two-stage iteration of sparse coding and dictionary update.In order to improve the dictionary training speed and performance,Augmented Lagrangianmultipliermethod(ALM)is introduced in the sparse coding stage,while the standard K-SVD dictionary updating algorithm isused in thedictionary updating stage.In thiswork,the dictionary training speed and root-mean-square error(RMSE)of the algorithm are investigated in the synthesis date experimentby selecting different sample sets and noisestandards.The resultsshow thatthealgorithm isbetter than thestandard K-SVD dictionary learning,which receives faster training speed and lowerRMSE.In order to investigate the image denoising ability of thealgorithm,simulation experiment is carried outby selecting different input image noise standards and the atomic numbers of the dictionary.The algorithm showshigherpeak signal-to-noise ratio(PSNR)and betterdenoising performance than thestandard K-SVD algorithm.

dictionary learning;K-SVD;sparse coding;Augmented Lagrangianmultipliermethod;ALM

TP391.9

A

1007-2373(2016)02-0001-08

10.14081/j.cnki.hgdxb.2016.02.001

2015-09-11

国家自然科学基金（61203245）；河北省自然科学基金（F2012202027）；河北省高等学校科学技术研究项目（Z2011142）

刘雅莉（1989-），女（汉族），硕士生．通讯作者：马杰（1978-），男（回族），副教授，博士．

数字出版日期：2016-04-19 数字出版网址：http://www.cnki.net/kcms/detail/13.1208.T.20160419.1019.002.htm l