基于一种网络结构的块稀疏字典学习

倪一宁　彭宏京

(南京工业大学电子与信息工程学院　江苏 南京 211816)



基于一种网络结构的块稀疏字典学习

倪一宁彭宏京

(南京工业大学电子与信息工程学院江苏 南京 211816)

摘要以过完备字典为基础，信号可以被描述为原子的稀疏线性组合。在以往的字典学习方法中，大都是以单个原子为单位进行字典学习。利用稀疏子空间聚类的方法将字典中具有相同稀疏表达形式的原子归类为一组，形成具有块结构的字典，然后对训练信号稀疏编码，最后结合梯度下降的方法对字典进行更新。实验结果表明，该方法在相同迭代次数下的优化收敛速度较快，而且对信号的重构误差率优于传统方法。另外，所构造一种对称网络结构的字典学习流程框架，不同于一次性用全部训练数据进行训练的方法，该学习流程每处理一组信号，字典进行一次更新，实现了对字典的分步更新。

关键词对称网络结构块稀疏梯度下降字典学习与信号稀疏表示

0引言

信号的表示是信号处理中的核心部分，大多数信号处理过程中依赖于信号的表示，例如图像压缩、去噪，信号的稀疏表现形式是常用的技术手段之一。将非正交基构成的字典设计为过完备的，设字典的列数K，字典的原子的维数是n, k>>n,称为过完备字典[1-4]。稀疏编码形成的系数向量与字典原子相乘叠加形成重构信号，所以信号的稀疏表示与重构可以用下式表示：

(1)

可以看出信号是由原子线性组合而成的，{d(k)}k是组成字典的一个个原子。当大多数系数c(k)为0时，这种信号表示就是稀疏的表达形式，{d(k)}k组合而成的矩阵即为所谓的字典形式。

对于大多数字典而言，字典的设计多种多样，这样字典也能够来表示宽泛的各种类型的信号。对于特定的信号和字典，为了用字典来精确表示和重构信号，需要通过字典对大量该类型信号训练[9]。字典学习过程中要将原始训练信号转化为与字典原子具有相同维数的列信号组合，同时在字典的设计方面，字典尺寸和结构也是要考虑的要素[11,13]。

在字典设计中，选择合适的字典学习算法是重要的。随着利用字典学习的方法处理信号的优越性日趋明显，各种各样的字典学习算法不断被提出以适应多种输入信号类型。字典学习算法的实质是优化目标式使得误差在一定原则下最小。求解目标误差式的最小二乘解其中一种方法是以直观闭解的形式直接求得全局最优解，其中典型的就是MOD[4]。另外通常以迭代的方法求局部最优解来获得最小误差，梯度下降是常用的一种迭代方法。除此以外，K均值聚类奇异值分解算法(K-SVD), 迭代最小二乘字典学习算法(ILS-DLA)等都是字典学习算法的发展[1,4]。

对信号的稀疏编码是字典学习过程中重要部分。稀疏编码用于在信号的分解与重构过程中产生稀疏的系数矩阵，通常有匹配追踪法(MP)、正交匹配追踪法(OMP)和FOCUSS等方法。MP算法是一种贪婪算法，每次都选择与信号最匹配的字典原子，获得的余量再选择匹配原子，直接达到预先设定的稀疏度或者余量误差阈值[7]。而OMP方法选择匹配字典原子之前对字典原子做正交处理，所以在稀疏编码过程中产生的余量不再选择已匹配过的原子，从而使得编码过程收敛速度更快[3,6,8,10]。

本文预先介绍MOD方法的字典学习，用MOD进行字典的更新优化时，字典更新的表达式是对欠定逆问题直观的最小二乘解。ILS-DLA是以MOD为主的字典学习方法[4]，由此发展而来的递归最小二乘法(RLS-DLA)与本文所用的梯度下降法相似能够实现分步的稀疏编码[2，5]。

字典的优化和信号的稀疏编码通常是在单个字典原子的基础上进行的，针对块稀疏信号(指信号不为0的地方成块出现的信号)，提出了块稀疏的压缩感知模型。所谓块稀疏指两方面，一方面指字典的块结构，能够表达相同信号的字典原子，将以聚类的形式结合形成最小的字典原子单位，从而在字典中形成块结构。当最小的字典原子单位为1时就降化为普通的字典结构；另一方面是块稀疏的编码，为了适应块结构字典的稀疏编码，将OMP的编码方法改善为BOMP(Block OMP)即块正交匹配追踪，BOMP在字典中选择与信号最匹配的块原子从而能够实现信号的块稀疏编码。信号按照潜在的子空间对字典进行块结构的分类。以往字典的块结构是固定的[3]，不会随着信号的输入重新调整字典的块结构。本文的字典块结构除了最大块尺寸(指字典中最大的聚类原子个数)是设定的，其余由输入信号决定，这样设计的字典块结构能够更好地适应信号的表示。梯度下降的方法和块稀疏结合，可以在实现分步稀疏编码的同时提高字典更新的收敛速度[12]。

1字典学习算法概述

(2)

ILS-DLA使用最小二乘法解这个误差表达式[1-4]，s为重构需要的原子数，固定系数矩阵C,可以得出：

D=(XCT)(CCT)-1

利用上式对字典D更新，然后保持D固定，利用OMP重新计算C，反复这两个步骤直到字典D收敛[4]。

ILS-DLA发展出的RLS-DLA可以归纳为一种连续的字典优化方法,更适合大规模训练信号，因为RLS-DLA可以实现在信号分步输入的情况下对字典连续优化更新[2]。在本文中使用的梯度下降法同样具有这个特性。

无论是ILS-DLA还是RLS-DLA字典更新方法大致四步骤：

(1) 输入信号的分解。

(2) 固定字典D对输入信号稀疏编码，形成系数矩阵C。

(3) 固定系数矩阵C优化字典D。

(4) 重复步骤(2)-步骤(3)直到字典D优化收敛。

2块稀疏的描述与实现

2.1块稀疏的概念

块稀疏的压缩感知模型包括字典的块结构与块稀疏编码两部分。字典的块结构是指能够表示相同信号的原子聚类成为字典的一个原子单位，该原子单位里的原子个数将不再是一个。与块结构相对应的块稀疏编码法BOMP是对正交匹配追踪法OMP的改善[3,6,8]，其本质是选择与训练信号最匹配的字典原子块。

2.2字典块结构和系数矩阵的初始化

对于给定的字典根据输入信号设计字典的块结构，首先初始化字典结构p和稀疏系数矩阵C，设字典D为N×K规模的矩阵，按照常规，字典D是由K个N维的向量组成的，每个向量是重构稀疏信号的原子，为满足冗余字典的要求，其中K>>N。初始化字典结构p为p=[1,2,…,K],每个原子为一个最小单位块等同于普通的字典结构，所以对系数矩阵C初始化利用OMP计算就可以满足。设稀疏度为k,表示每个重构信号由k个非零原子构成，字典的块结构尺寸设置为s，由于信号可视为k个块原子组合而成的，所以在用OMP初始化系数C时，初始的稀疏度应该是k×s[3,6](系数矩阵中的每个列向量都有至多有k×s个非零元素)。

2.3更新块结构p与实例描述

更新块结构的时候应不再对系数矩阵C更新，为了在块结构p下得到最少的非零系数，可以描述为以下公式：

(3)

3基于网络结构的块稀疏字典优化方法

3.1字典优化流程框架

图1　字典流程框架

字典优化流程可以概括为：首先对字典的块结构与系数矩阵初始化，然后基于字典D，对训练信号X块稀疏编码产生系数矩阵C；最后利用C对W优化更新。需要指出的是每次利用梯度下降对字典更新完成后，随着新的训练信号输入会产生新的系数矩阵C，W的块结构也应及时优化更新。

基于本文的字典学习框架的字典学习方法是轮换迭代的，即每学习完一轮，就会将W的转置作为下一轮字典学习的初始字典D，学习一轮视为迭代1次，实验一共迭代100次，分别记录迭代第25次、50次、75次和100次的字典为D25、D50、D75和D100。分别用这四个字典对同一幅噪声图片去噪，记录去噪后图片的PSNR和MSE放入下面表1中对比。PSNR为峰值信噪比，MSE为均方根误差。

表1　迭代不同阶段字典去噪效果评估

从表1可以看出随着迭代次数的增加，PSNR增加，MSE减小，对信号的重构效果越来越好。同时也说明将W的转置作为下一轮字典学习的初始字典D的方法是可行的。

另外需要注意的是由于此时字典的最小原子单位为块，利用BOMP方法编码产生C的最小单位也是块的形式，例如，设块结构字典块大小为s,字典中有k个块原子，块原子信号维度为n,那么字典大小为n×(K×s)，设输入的一组训练信号大小为n×s，可得C的大小为(K×s)×s,由于字典块尺寸s不等于1，所以C的最小单位为块，不是单行或单列的。

3.2梯度下降字典优化方法的推导

(4)

其中，XTX中不含Wij，所以：

所以对称字典W的更新有以下关系式：

Wn=Wn-1-a×[-CX+CTCWn-1]ij

(5)

本文字典优化方法具体步骤如下：

(1) 设置初始化字典结构p=[1,2,…,K],字典块最大尺寸为s,利用OMP将系数矩阵C求出，稀疏度为k×s。

(2) 根据第2节的描述的原则，寻找C中具有相同稀疏形式的列,将D中的对应列合并同时将W中对应行合并，合并块尺寸不能超过s直至所有字典原子合并。

(3) 根据合并后的D，利用BOMP计算新的系数矩阵C。

(4) 根据训练信号X和系数矩阵C，利用式(5)对W更新。

(5) 有信号输入完成更新字典后，将W的转置作为下一轮的初始字典D，重复步骤(1)-步骤(4)，直至字典收敛。需要指出首次输入信号之后，由于字典形成了块结构，第(1)步改为根据上一次更新后的字典及其块结构，利用BOMP计算新的系数矩阵C。

4实验结果及分析

在实验部分，要测试和对比两部分，分别是字典块结构算法中的系数稀疏度选择、本文算法与ILS-DLA、K-SVD的对比实验。

4.1块结构算法实验

图2　块覆盖成功率随稀疏度的变化　图3　误差率随稀疏度的变化

从图2可以看出当k>5时，字典块恢复率r明显降低，而当k<5时字典块恢复率r都较高。图3可以看出随着k的增长误差率e也逐渐增长。所以在本文块的稀疏度的选择不能超过5。

4.2本文字典优化方法与K-SVD、ILS-DLA重构去噪对比实验

设定D为64×1024的随机矩阵并进行归一化，字典块结构最大尺寸s=2,系数矩阵C时的稀疏度最大值设置为8(s×k=4)，梯度下降学习速率设置为0.05，调节速率为0.001。输入训练信号为图像库中随机的选取的100幅图片，测试图片不在训练图片范围之内。对测试图片加方差σ为20和30，均值为0的高斯白噪声。如图4-图6所示。

图4　图像去噪结果比对

图5　图像去噪结果比对

图6　图像去噪结果比对

图7　迭代过程中字典优化误差‖的变化

随机选取100幅图片作为输入信号，观测本文方法、ILS-DLA、K-SVD在迭代过程中的误差变化如图7所示。

由图7可知在迭代过程中，本文方法中字典收敛速度比K-SVD、ILS-DLA更快。

5结语

本文方法能够更加直观地展现字典的训练与重构，以Frobenius范数衡量字典与初始字典的误差，实验证明本文的字典优化收敛速度优于K-SVD和ILS-DLA。

利用优化后的字典处理噪声图片，实验验证了本文方法处理的图片的PSNR均高于K-SVD和ILS-DLA。这也说明本文的字典优化方法对信号的重构效果优于K-SVD和ILS-DLA。

对比用特定字典训练特定类型信号的方法，本文方法更适合处理大量各种类型的训练信号，优化后的字典可以更精确的重构表示各种类型的信号。

本文方法执行速度优于ILS-DLA,但是比K-SVD慢，所以在执行速度方面需要改善。另外最大块尺寸s和学习速率η的设置对字典优化速率和信号重构的影响都是需要进一步探索的课题。

参考文献

[1] Michal Aharon,Michael Elad,Alfred Bruckstein.K-SVD:An algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Trans on Signal Processing,2006,54(11):4311-4322.

[2] Karl Skretting,Kjersti Engan.Recursive least squares dictionary learning algorithm[J].IEEE Trans on Signal Processing,2010,58(4):2121-2130.

[3] Kevin Rosenblum,Lihi Zelnik-Manor.Dictionary optimization for block-sparse representations signal Processing[J].IEEE Trans on Signal Processing,2012,60(5):2386-2395.

[5] Julien Mairal,Francis Bach,Jean Ponce,et al.Online dictionary learning for sparse coding,2009[C]//Proceedings of the 26th Annual International Conference on MachineLearning,ICML.2009:14-18.

[6] Yuli Fu,Haifeng Li,Qiheng Zhang,et al.Block-sparse recovery via redundant block OMP[J].IEEE Trans on Signal Processing,2014,97:162-171.

[7] 杨真真,杨震,孙林慧.信号压缩重构的正交匹配追踪类算法综述[J].信号处理,2013,29(4):486-496.

[8] Pati Y C,Rezzaiifar R,SKrishnaprsad P.Orthogonal matching pursuit:recursive function approximation with application to wavelet decomposition[C]//1993 ConferenceRecord of The 27thAsilomar Conference on Signal Process,1997,45(3):600-616.

[9] Elad M,Aharon M.Image denoising via sparse and redundant representations over learned dictionaries[J].IEEE Trans Image Process,2006,15(12):3736-3745.

[10] Julien Mairal,Francis Bach,Jean Ponce,et al.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research,2010,11(1):19-60.

[11] Ron Rubinstein,Michael Zibulevsky,Michael Elad.Double sparsity learning sparse dictionaries[J].IEEE Trans on Signal Processing,2010,58(3):1553-1564.

[12] Ron Rubinstein,Michael Zibulevsky,Michael Elad.Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[EB/OL].http://www.technion.ac.il/～ronrubin/software.html.

[13] Ron Rubinstein,Michael Zibulevsky,Michael Elad.Dictionaries for sparse representation modeling[J].IEEE Proceedings-Special Issue on Applications of Sparse Representation&Compressive Sensing,2010,98(6):972-982.

BLOCK SPARSE DICTIONARY LEARNING BASED ON A NETWORK STRUCTURE

Ni YiningPeng Hongjing

(SchoolofElectronicandInformationEngineering,NanjingUniversityofTechnology,Nanjing211816,Jiangsu,China)

AbstractBased on over-complete dictionary, the signal can be described as sparse linear combination of atoms. In previous dictionary learning methods, most of them are based on single atom unit. We made use of sparse subspace clustering method to range the atoms with same sparse expression form into one group and formed a dictionary with block structure, and then conducted the sparse coding on training signals, finally updated the dictionary in combination with gradient descent method. Experimental result showed that this method had faster optimised convergence rate in same iteration times, and was superior to traditional methods in signal reconstruction error rate. Besides, we constructed a dictionary learning process framework with symmetrical network structure, differing from the method which uses all training data one-off in training, in it the dictionary will update once along with each processing of a set of signals in this learning process, and it realises the stepwise update of the dictionary.

KeywordsSymmetrical network structureBlock sparseGradient descentDictionary learning and signal sparse representation

收稿日期：2015-01-12。江苏省自然科学基金项目(BK2011794)。倪一宁，硕士生，主研领域：数字图像处理中的信号处理。彭宏京，副教授。

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.065