压缩感知框架下快速字典的学习算法

张得生, 张莉华

(黄淮学院 信息工程学院， 河南 驻马店 463000)



压缩感知框架下快速字典的学习算法

张得生, 张莉华

(黄淮学院 信息工程学院， 河南 驻马店 463000)

信号稀疏基的构造，关系信号稀疏表示的程度，进而影响应用压缩感知对信号进行恢复重构的效果。针对这一问题，多种字典学习算法如KSVD，OLM等予以提出；这些算法使用重叠的图像块来构建字典，产生了大量稀疏系数，从而导致过拟合及计算过缓，且不能确保收敛；基于此，设计一种基于近端梯度的快速字典学习算法。算法在分析近端梯度求解多重凸优化问题的基础上，将其应用于字典学习涉及的优化求解上，降低了每次迭代的复杂度，减少了迭代开销，同时能够确保收敛。在合成数据上的实验表明，该算法字典学习速度快，所耗时间短，且获得的字典更好。

字典学习； 稀疏表示； 近端梯度； 全局收敛; 压缩感知

0 引 言

压缩感知是一种利用信号的可压缩性或者稀疏性对信号进行重构的技术。压缩感知颠覆了传统的信号采样方法，它对信号进行稀疏表示来保证原始信号的主要结构，能够通过更少的数据采样来对信号进行恢复重构，已发展成为一种新型的数据采样技术；不言而喻，其优势在于降低了数据采样率，直接获得信号的稀疏表示，大大缩减了数据信息的获取时间和存储空间。图1给出了压缩感知的理论过程，压缩感知包括信号的稀疏表示、观测矩阵的设计、信号重构。

假定信号x在基D下能够进行稀疏表示，则只要获得在给定基D下信号x的线性测量值b=x+ξ(ξ为噪声)，就能够由其稀疏表示来恢复信号x。上述问题等价于优化求解[2]

(1)

其中：‖y‖0为l0范数，表示向量中非零元素的个数；ε为控制误差。式(1) 求解出y，则由x=Dy就可以获得原信号x。

Mallat于1993年提出使用超完备字典作为基对信号进行表示[3]，以求得信号的最稀疏表示，这开启了稀疏表示先河。经研究发现[4]，信号经稀疏表示后越稀疏则信号重建后的精度越高，而且稀疏表示可以根据信号的自身结构特点自适应的选择合适的过完备字典，从而对信号稀疏表示的目的在于寻找一个自适应字典使信号能够最稀疏表达。因此稀疏表示核心问题在于选择一个最优的字典和合适的稀疏分解算法。

字典可分为分析字典和学习字典两大类。常用的分析字典有小波字典[4]、过完备DCT字典和Curvelets等，使用分析字典进行稀疏表示，简单易实现，但信号表示形式单一且不具备自适应性；相比之下，学习字典能更好地适应不同的图像数据，自适应能力强[1,5-6]，常用的学习字典的方法有：Michael Elad提出的KSVD算法[7];Mairal提出的OLM算法[8]。

KSVD、OLM核心思想是交替迭代优化，主要有两步：信号稀疏表示——固定字典下稀疏表示；字典更新——固定稀疏系数下的字典更新。这类字典学习算法使用重叠图像块构建字典进行稀疏表示，同时应用交替迭代更新的优化方法，计算复杂度高，而且无法确保算法的收敛性。

针对以上问题，本文提出一种基于加速近端梯度的字典学习算法。该算法在每次迭代中，采用联合优化，同时进行字典原子更新和稀疏表示求解，即在稀疏表示优化求解过程中不限制字典更新。对比于其它算法，该算法大大降低了每一步迭代的复杂度，运算更快，同时能确保全局收敛。

1 字典学习

假定训练数据集X∈Rn×p，矩阵中每一列即为一个信号向量；字典D∈Rn×K。KSVD通过求解下述优化问题来实现字典学习[7,9]：

(2)

其中:‖di‖2表示l2范数;s为表示稀疏度的参数;di是字典的第i列。

KSVD算法交替更新Y和D来求解式(2)，其迭代过程主要包括：① 在当前字典下对X中的信号进行稀疏分解，实现这类稀疏表示的算法很多，如OMP、BP算法；② 更新字典中的原子，其核心为SVD算法。其中，优化求解涉及矩阵的SVD计算，计算量很大，很大程度上限制了计算速度；当图像尺寸、迭代次数较大时，所产生的计算总量及计算消耗巨大，所需时间过长，实用价值受到较大限制，同时该算法无法确保收敛。

另一个典型的字典学习方法是OLM (Online Dictionary Learning)[8,10],其通过求解下述优化问题来实现字典学习：

(3)

(1) 稀疏表示。固定字典D，随机选取矩阵X中的信号向量，组合成信号小块，然后求取在字典D上的稀疏表示系数YS(其中，S为选取样本块的索引)；

(2) 字典更新。求解下述优化问题，更新字典D：

其中:XS表示矩阵X的子矩阵，其元素为矩阵X中所有包含索引S指代的元素。该算法运行效率依赖于训练样本的分布，当样本为同分布时其比KSVD算法运行得更快，但是仍难以保证其收敛性；每步迭代涉及矩阵块运算，计算量很大[10]。

当然还有很多其他字典学习的算法[11]和更为复杂的稀疏表示模型[12-14]，在此不再赘述。

本文致力于式(3)的快速求解方法的研究,其基本思路是引入加速近端梯度，采用联合优化策略，在每一次迭代中，更新字典和系数矩阵，加速计算，同时确保收敛。

2 基于近端梯度快速字典学习

通过字典学习，获得的字典更适应于自然图像表示，能更好地表示信号。学习字典的方法有很多，如MOD[15]、KSVD、OLM等，本文采用一种新的方法来实现字典学习，即应用近端梯度算法来加速求解式(3)优化问题。

2.1 基于块的加速近端梯度方法

对于多重凸优化问题， Xu等提出了一种基于BPG(Block Proximal Gradient)的求解方法[16]； Ma提出了一种基于APG (Alternating Proximal Gradient) 的求解方法。本文我们将结合这两种方法来求解型如式(3)的双凸优化类问题：

(4)

其中：函数f可微，且对于变量x、y，当固定其中任一个，函数f对于另一个变量为凸函数；rx、ry是值扩充凸函数。

BPG方法的第k步迭代中，x、y更新公式为：

(5a)

(5b)

在满足一些边界条件下，文献[16]证实了该算法中子序列的收敛性。假如进一步满足KL(Kurdyka- Lojasiewicz)[17]性质，则式(5)生成的序列{xk，yk}全局收敛于式(4)中某一稳定点。

2.2 字典学习

通过求解式(3)，从数据样本X中学习字典。

构建函数：

显然，上式为式(3)中的保真项；将式(5)代入式(3)，即可得D、Y的更新公式：

(6a)

(6b)

式(6)更新公式可以改写成：

(7a)

(7b)

其中，pD(·)表示在上的投影，其定义为：

Sτ(·)表示软阈值算子，定义如下：

‖(D-D)YYT‖F≤‖YYT‖‖D-D‖F, ∀D,D

本文中，通过数值测验，设置Lipschitz常数和外推算法中涉及的权重：

(8)

(9a)

(9b)

其中

本文采用近端梯度算法进行优化求解，过程中同时更新D和Y，这区别于KSVD、OLM采用最小化方法交替更新D和Y。维持对关于D和Y子问题拥有封闭解，降低了算法每一步迭代的复杂度；同时采用上述外推设计，进一步加速了收敛，减少了迭代次数，大大缩短了运算时间。概述如下：

算法：基于近端梯度快速字典学习。

数据：训练样本X，λ>0。

初始点(D-1,Y-1)=(D0,Y0)。

如果F(Dk，Yk)>F(Dk-1,Yk-1),则令Dk=Dk-1，Yk=Yk-1，并根据 (7a)(7b)重新更新Dk、Yk；

如果满足停止条件(*)，则停止运算，并输出(Dk,Yk)。

2.3 收敛分析

式(3)的优化问题等价于：

(10)

假定(D,Yk)为根据上述算法生成的序列对，如果序列{Dk}与{Yk}都一致地偏离起始点，那么(Dk,Yk)将收敛于(10)式或(3)式中的一个稳定点。

3 数值实验

本文设置了2组对比实验，即分别与经典的KSVD、OLM在合成数据上进行对比实验。之所以选择用KSVD和OLM作对比，是因为这2种算法使用广泛，还因为这2种算法的效果得到充分验证。测试的实验指标为：平均计算速度，字典学习的效率。

字典学习的效率，本文是如下界定的。从原始字典D中恢复的每一个原子d满足：

则称字典更新是成功的。其中，di是预测字典D的第i列。本文用字典更新成功率指代字典学习的效率。

本文算法的终止条件为：

结合文献[7,10]，按下述步骤展开实验：

第1步，生成实验所需数据。首先，生成字典D∈Rn×K(即randn(n,K))，并对每一列进行归一化；然后，在n维空间生成p个信号，组成训练样本X(X∈Rn×p)。其中，每一个样本都是均匀地随机选择字典D中的r列原子进行线性组合形成的，且组合系数是高斯随机生成的。

第3步，取3组不同数据对(K，p)来进行实验，且在每组(K，p)中测试5组不同稀疏度r下的数据，其中r的变化范围为{4,6,8,10,12}。每组实验我们独立运行100次，然后统计计算其平均运行时间(T)和恢复准确率(R)。

统计3组实验数据，分别如表1所示。

表1 第1组(K，p)下3种算法实验结果对比

与KSVD对比，相同条件下字典学习效果相当(即字典的更新成功率相当时)，但本文算法所用时间明显比KSVD短，计算速度优势明显；当稀疏度r值较大(如r=12)或者训练样本有限时(如，p=20n)，相同条

表2 第2组(K，p)下3种算法实验结果对比

表3 第3组(K，p) 下3种算法实验结果对比

件下本文算法字典更新成功率明显要高，即本文算法字典学习效果显著优于KSVD；

与OLM对比，观察第1组组数据，实验结果如表1所示，可以发现相同条件下OLM字典更新成功率低于本文算法，即本文算法的字典学习效果优于OLM的字典学习效果。后2组组实验中，实验结果如表2、表3所示，当不考虑运行时间，相同条件下OLM算法与本文算法字典更新成功率相近；考虑运算时间，易于发现相同条件下本文算法与OLM算法字典学习效果相当，但本文算法所用时间明显要短，即其收敛速度更快。

4 结 语

字典学习在图像处理等领域的应用越来越广，而算法的复杂度和收敛性很大程度上制约着字典学习应用与推广，也逐渐成为研究的重点。本文中，发展了一种新的字典学习算法，不同于其它求解字典学习问题的方法，引用了近端梯度算法来求解字典学习涉及的组合优化问题。算法主要针对非凸光滑函数与可分离的凸函数的组合函数的优化，采用联合优化，同时进行字典原子更新和稀疏表示求解，降低了每一步迭代的复杂度，加快了计算速度，同时能够确保收敛于稳定点，具有较强的实用性，也为稀疏表示问题求解提供一种借鉴。

[1] DONOHO D L. COMPRESSED SENSING[J]. INFORMATION THEORY, IEEE TRANSACTIONS ON, 2006, 52(4): 1289-1306.

[2] MICHAEL Elad, MICHAL Aharon. Image denoising via sparse and redundant representations over learned dictionaries [J]. Image Processing, IEEE Transactions on, 2006, 15(12): 3736-3745.

[3] MALLAT S G, ZHANG Z. Matching pursuits with time-frequency dictionaries[J]. Signal Processing, IEEE Transactions on, 1993, 41(12): 3397-3415.

[4] CANDES Emmanuel, ROMBERG Justin, TAO Terence. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59(8): 1207-1223.

[5] KREUTZ-DELGADO K, MURRAY J F, RAO B D,etal. Dictionary learning algorithms for sparse representation[J]. Neural computation, 2003, 15(2): 349-396.

[6] MAIRAL J, PONCE J, SAPIRO G,etal. Supervised dictionary learning[C]//Advances in Neural Information Processing Systems. 2009: 1033-1040.

[7] MICHAEL Elad, MICHAL Aharon, BRUCKSTEIN A. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[J]. Signal Processing, IEEE Transactions on, 2006, 54(11): 4311-4322.

[8] MAIRAL J, BACH F, PONCE J,etal. Online learning for matrix factorization and sparse coding [J]. The Journal of Machine Learning Research, 2010, 11: 19-60.

[9] RUBINSTEIN Ron, TOMERPeleg, MICHAELElad. Analysis K-SVD: A dictionary-learning algorithm for the analysis sparse model [J]. Signal Processing, IEEE Transactions on, 2013, 61(3): 661-677.

[10] MAIRAL J, BACH F, PONCE J,etal. Online dictionary learning for sparse coding[C]//Proceedings of the 26th Annual International Conference on Machine Learning. ACM, 2009: 689-696.

[11] TOSIC I, FROSSARD P. Dictionary learning [J]. Signal Processing Magazine, IEEE, 2011, 28(2): 27-38.

[12] BRUCKSTEIN A M, DONOHO D L, MICHAEL Elad. From sparse solutions of systems of equations to sparse modeling of signals and images [J]. SIAM Review, 2009, 51(1): 34-81.

[13] MAIRAL J, BACH F, PONCE J. Task-driven dictionary learning [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012, 34(4): 791-804.

[14] MAIRAL J, PONCE J, SAPIRO G,etal. Supervised dictionary learning[C]//Advances in Neural Information Processing Systems. 2009: 1033-1040.

[15] ENGAN K, AASE S O, HUS?Y J H. Multi-frame compression: Theory and design [J]. Signal Processing, 2000, 80(10): 2121-2140.

[16] XU Y, YIN W. A block coordinate descent method for multiconvex optimization with applications to nonnegative tensor factorization and completion[R]. RICE UNIV HOUSTON TX DEPT OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2012.

[17] BOLTE J, DANIILIDIS A, LEWIS A. The Lojasiewicz inequality for nonsmoothsubanalytic functions with applications to subgradient dynamical systems[J]. SIAM Journal on Optimization, 2007, 17(4): 1205-1223.

[18] BECK A, TEBOULLE M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202.

Research on Fast Dictionary Learning Algorithm Under Compressed Sensing Framework

ZHANGDe-sheng,ZHANGLi-hua

(School of Information Engineering, Huanghuai University, Zhumadian 463000, China)

The construction of sparse base concerns the degree of signal sparse representation, thereby affects the restoration effect of signal under compressed sensing. For this problem, a variety of algorithms for dictionary learning such as KSVD, OLM (Online dictionary learning), etc. have been proposed. These algorithms use overlapping image blocks to build dictionary. These algorithms may result in a plethora of sparse coefficient, lead to over-fitting and calculation slow phenomenon, and their convergence cannot be ensured. Focusing on this problem, the paper designs a fast dictionary learning algorithm based on proximal gradient. Based on the analysis of the proximal gradient algorithm for solving the multiple convex optimization problem, the paper applies it to solve the optimization problem involved in the dictionary learning. The algorithm proposed reduces the complexity and overhead in iterations, and ensures global convergence. Experiments on synthetic data show that the algorithm can get a better dictionary, while its speed and quality are more competitive.

dictionary learning; sparse representation; proximal gradient method; global convergence; compressed sensing

2015-04-21

河南省科技厅发展计划(142102110088)；河南省科技攻关项目(No.122102210430)

张得生(1982-)，男，河南汝南人，硕士，实验师，主要从事计算机应用、信息安全等研究。E-mail: zds9802@qq.com

TP 391.43

A

1006-7167(2015)11-0094-05