基于正则化模型的K—SVD算法及其应用

刘坚桥 唐加山

摘要：提出一种基于正则化方法的K均值奇异值分解（K-SVD）算法。新算法在更新字典阶段，建立一种正则化模型，针对经典K-SVD算法中每次原子更新，引入正则项参与字典更新过程，将每次更新原子所产生的误差限制在设定范围内完成原子更新。在K-SVD算法正则化模型基础上，对K-SVD的衍生算法近似K-SVD（Approximate K-SVD）进行了研究，提出了适用于AK-SVD的正则化模型。实验结果表明，新模型训练字典的误差相较于传统算法缩小了13.8%。将训练字典用于图像去噪时发现，新模型下字典重构出图像的峰值信噪比（PSNR）比传统算法提升0.5dB左右。

关键词：K-SVD；正则化方法；字典学习；稀疏表示；图像去噪

DOIDOI：10.11907/rjdk.173177

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）008-0114-04

英文摘要Abstract：A method of K Singular Value Decomposition （K-SVD） based on regularized model is proposed.The regularized term is introduced into the algorithm at the stage of updating atoms，which limits the training error to optimal level.Furthermore，some other algorithms improved from K-SVD can also be combined with the regularized model to promote their performance.The new model is implemented in signal reconstruction and image denoising in experiments.Simulation results show that compared with the traditional K-SVD，the RMSE of new method decrease by about 13.8% in signal set reconstruction，and the Peak Signal to Noise Ratio （PSNR） increase about 0.5dB in image denoising.

英文关键词Key Words：K-SVD； regularization method； dictionary learning； sparse representation；image denoising

收稿日期收稿日期：2017-12-11

基金项目基金项目：

作者简介作者简介：刘坚桥（1993-），男，南京邮电大学通信与信息工程學院硕士研究生，研究方向为信号处理、压缩感知；唐加山（1968-），男，博士，南京邮电大学理学院教授，研究方向为应用概率统计、现代通信中的智能信号处理技术、信道辨识与均衡、复杂网络。

0 引言

在稀疏表示领域，基于超完备冗余字典的信号稀疏分解[1]理论应用较多，而字典学习算法优化了冗余字典结构，使得构造出的字典能更好地适应模型，极大提高了冗余字典的灵活性与实用性。

K-SVD字典学习算法是字典学习的经典算法之一，由Aharon等[2]于2006年提出，在压缩感知[3]、稀疏分解等领域得到广泛应用。与其它字典学习算法如MOD[4]等不同，K-SVD算法在更新字典时，对字典原子逐列进行更新而非直接更新整个字典。在更新原子方式上，K-SVD采用了K-Means聚类算法[5]思想，结合SVD（奇异值分解）对原子进行更新。SVD分解时间复杂度和空间复杂度都很高，而K-SVD每次原子更新都要进行一次SVD分解，导致算法运行时费时费力。对此，Hartigan [6]等提出了一种近似K-SVD算法（AK-SVD）。AK-SVD算法以一定的精度损失换取算法在运行速度上的提升。

机器学习中经常用正则化方法对学习模型进行优化[7]，通过对模型引入不同范数的正则项达到目的，F范数能防止学习模型过拟合[8]。本文通过将K-SVD算法与F范数正则化相结合，提出一种基于F范数正则化的K-SVD算法。

1 研究背景

K-SVD算法求解分为稀疏表示阶段和字典学习阶段。

3 实验

本实验的硬件环境是（4.0GHz，16GB），所有算法均采用MATLAB2016a实现。实验分为信号集训练测试和算法的图像去噪两个部分。

实验1：信号集训练测试。给定大小为20×50的初始字典，分别用K-SVD 、AK-SVD以及相应的正则化模型进行字典训练。通过改变算法迭代次数计算截止到第k次更新时所积累的均方根误差RMSE：

其中，size表示字典大小，实验中值为100，训练集Y的稀疏度为3，正则化参数设为0.05。整个算法重复30次，取平均值得到RMSE随迭代次数的关系如图1所示。

实验2：将正则化K-SVD算法应用到图像去噪。实验中正则化参数设为0.1，实验先随机构造冗余DCT字典，再将字典进行基于待处理图片进行在线字典学习，并将得到的字典用于图像去噪。实验处理了3幅带噪声图片，采用峰值信噪比（PSNR）[15]衡量去噪水平，去噪效果如图2所示。

由图1可知，随着迭代次数增加，所有算法字典训练的RMSE不断缩小。当迭代次数达到128次左右时，所有算法的RMSE都减小到一个稳定值，表明所有算法都已收敛。在收敛状态时，R-KSVD （正则化K-SVD）的RMSE最小，而R-AKSVD （正则化AK-SVD）与K-SVD的RMSE比较接近且都大于正则化K-SVD，AK-SVD算法的RMSE远大于其它3种算法。实验结果表明，正则化模型使得原有算法在字典训练时误差更小，给K-SVD和AK-SVD带来了精度上的提升，从而提高了字典的表达能力。

由图2可知，正则化K-SVD在图像去噪中表现良好。3幅带噪声图去噪处理后信噪比提升明显，处理后的图片相较于原图亮度虽有所下降，但原图的细节都得到了恢复。实验2表明正则化模型下的K-SVD在图像去噪中保留了经典K-SVD优势，能够出色完成图像去噪处理。

4 结语

本文提出一种K-SVD字典学习算法以及它的衍生算法AK-SVD的正则化模型。对模型进行求解然后应用到仿真实验，实验结果表明，正则化K-SVD算法能够缩小训练誤差，提升原算法所得字典的表达能力。此外，正则化模型结合AK-SVD算法能够在一定程度上弥补AK-SVD算法在字典表达能力上的不足。在图像去噪中，正则化K-SVD性能稍优于传统K-SVD算法。正则化参数的选取一般在0.05～0.1之间效果较好，不同应用场景下正则化参数的选取还有待进一步研究。

参考文献：

[1] 余南南.基于稀疏表示的图像融合与去噪算法研究[D].大连：大连理工大学，2012.

[2] AHARON M，ELAD M，BRUCKSTEIN A.K-SVD：an algorithm for designing overcomplete dictio- naries for sparse representation [J].IEEE Transactions on Signal Process，2006，54（11）：4311-4322.

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

[4] 练秋生，石保顺，陈书贞.字典学习模型、算法及其应用研究进展[J].自动化学报，2015，41（2）：240-260.

[5] HARTIGAN J A，WONG M A.Algorithm AS 136：a K-means clustering algorithm[J].Journal of the Royal Statistical Society，Series C （Applied Statistics），1979，28（1）：100-108.

[6] RUBINSTEIN R， ZIBULEVSKY M，ELAD M.Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[C].Haifa：Cs Technion，2008.

[7] 朱军，胡文波.贝叶斯机器学习前沿进展综述[J].计算机研究与发展，2015，52（1）：16-26.

[8] 吴颉尔.正则化方法及其在模型修正中的应用[D].南京： 南京航空航天大学，2007 .

[9] 魏雅丽，温显斌，邹永廖，等.基于稀疏分解和聚类的自适应图像去噪新方法[J].计算机应用，2013，33（2）：476-479.

[10] 刘建伟，崔立鹏，刘泽宇，等.正则化稀疏模型[J].计算机学报，2015 （7）：1307-1325.

[11] 农秀丽.齐次等式约束线性回归模型回归系数的综合条件岭估计[J].湖南师范大学自然科学学报，2012，35（2）：7-13.

[12] 吕琪.不适定问题的迭代正则化方法研究[D].武汉：武汉理工大学，2012.

[13] GOLUB G H，VAN LOAN C F.Matrix computations[M].fourth edition，Baltimore：JHU Press，2012.

[14] 丰明坤，赵生妹，邢超.一种基于视觉特性的PSNR图像评价方法[J].南京邮电大学学报：自然科学版，2015，35（4）：33-38.

（责任编辑：杜能钢）