壓縮感知框架下快速字典的學(xué)習(xí)算法

張得生, 張莉華

(黃淮學(xué)院 信息工程學(xué)院， 河南 駐馬店 463000)

?

壓縮感知框架下快速字典的學(xué)習(xí)算法

張得生, 張莉華

(黃淮學(xué)院 信息工程學(xué)院， 河南 駐馬店 463000)

信號(hào)稀疏基的構(gòu)造，關(guān)系信號(hào)稀疏表示的程度，進(jìn)而影響應(yīng)用壓縮感知對(duì)信號(hào)進(jìn)行恢復(fù)重構(gòu)的效果。針對(duì)這一問題，多種字典學(xué)習(xí)算法如KSVD，OLM等予以提出；這些算法使用重疊的圖像塊來構(gòu)建字典，產(chǎn)生了大量稀疏系數(shù)，從而導(dǎo)致過擬合及計(jì)算過緩，且不能確保收斂；基于此，設(shè)計(jì)一種基于近端梯度的快速字典學(xué)習(xí)算法。算法在分析近端梯度求解多重凸優(yōu)化問題的基礎(chǔ)上，將其應(yīng)用于字典學(xué)習(xí)涉及的優(yōu)化求解上，降低了每次迭代的復(fù)雜度，減少了迭代開銷，同時(shí)能夠確保收斂。在合成數(shù)據(jù)上的實(shí)驗(yàn)表明，該算法字典學(xué)習(xí)速度快，所耗時(shí)間短，且獲得的字典更好。

字典學(xué)習(xí)； 稀疏表示； 近端梯度； 全局收斂; 壓縮感知

0 引 言

壓縮感知是一種利用信號(hào)的可壓縮性或者稀疏性對(duì)信號(hào)進(jìn)行重構(gòu)的技術(shù)。壓縮感知顛覆了傳統(tǒng)的信號(hào)采樣方法，它對(duì)信號(hào)進(jìn)行稀疏表示來保證原始信號(hào)的主要結(jié)構(gòu)，能夠通過更少的數(shù)據(jù)采樣來對(duì)信號(hào)進(jìn)行恢復(fù)重構(gòu)，已發(fā)展成為一種新型的數(shù)據(jù)采樣技術(shù)；不言而喻，其優(yōu)勢(shì)在于降低了數(shù)據(jù)采樣率，直接獲得信號(hào)的稀疏表示，大大縮減了數(shù)據(jù)信息的獲取時(shí)間和存儲(chǔ)空間。圖1給出了壓縮感知的理論過程，壓縮感知包括信號(hào)的稀疏表示、觀測(cè)矩陣的設(shè)計(jì)、信號(hào)重構(gòu)。

假定信號(hào)x在基D下能夠進(jìn)行稀疏表示，則只要獲得在給定基D下信號(hào)x的線性測(cè)量值b=x+ξ(ξ為噪聲)，就能夠由其稀疏表示來恢復(fù)信號(hào)x。上述問題等價(jià)于優(yōu)化求解[2]

(1)

其中：‖y‖0為l0范數(shù)，表示向量中非零元素的個(gè)數(shù)；ε為控制誤差。式(1) 求解出y，則由x=Dy就可以獲得原信號(hào)x。

Mallat于1993年提出使用超完備字典作為基對(duì)信號(hào)進(jìn)行表示[3]，以求得信號(hào)的最稀疏表示，這開啟了稀疏表示先河。經(jīng)研究發(fā)現(xiàn)[4]，信號(hào)經(jīng)稀疏表示后越稀疏則信號(hào)重建后的精度越高，而且稀疏表示可以根據(jù)信號(hào)的自身結(jié)構(gòu)特點(diǎn)自適應(yīng)的選擇合適的過完備字典，從而對(duì)信號(hào)稀疏表示的目的在于尋找一個(gè)自適應(yīng)字典使信號(hào)能夠最稀疏表達(dá)。因此稀疏表示核心問題在于選擇一個(gè)最優(yōu)的字典和合適的稀疏分解算法。

字典可分為分析字典和學(xué)習(xí)字典兩大類。常用的分析字典有小波字典[4]、過完備DCT字典和Curvelets等，使用分析字典進(jìn)行稀疏表示，簡(jiǎn)單易實(shí)現(xiàn)，但信號(hào)表示形式單一且不具備自適應(yīng)性；相比之下，學(xué)習(xí)字典能更好地適應(yīng)不同的圖像數(shù)據(jù)，自適應(yīng)能力強(qiáng)[1,5-6]，常用的學(xué)習(xí)字典的方法有：Michael Elad提出的KSVD算法[7];Mairal提出的OLM算法[8]。

KSVD、OLM核心思想是交替迭代優(yōu)化，主要有兩步：信號(hào)稀疏表示——固定字典下稀疏表示；字典更新——固定稀疏系數(shù)下的字典更新。這類字典學(xué)習(xí)算法使用重疊圖像塊構(gòu)建字典進(jìn)行稀疏表示，同時(shí)應(yīng)用交替迭代更新的優(yōu)化方法，計(jì)算復(fù)雜度高，而且無法確保算法的收斂性。

針對(duì)以上問題，本文提出一種基于加速近端梯度的字典學(xué)習(xí)算法。該算法在每次迭代中，采用聯(lián)合優(yōu)化，同時(shí)進(jìn)行字典原子更新和稀疏表示求解，即在稀疏表示優(yōu)化求解過程中不限制字典更新。對(duì)比于其它算法，該算法大大降低了每一步迭代的復(fù)雜度，運(yùn)算更快，同時(shí)能確保全局收斂。

1 字典學(xué)習(xí)

假定訓(xùn)練數(shù)據(jù)集X∈Rn×p，矩陣中每一列即為一個(gè)信號(hào)向量；字典D∈Rn×K。KSVD通過求解下述優(yōu)化問題來實(shí)現(xiàn)字典學(xué)習(xí)[7,9]：

(2)

其中:‖di‖2表示l2范數(shù);s為表示稀疏度的參數(shù);di是字典的第i列。

KSVD算法交替更新Y和D來求解式(2)，其迭代過程主要包括：① 在當(dāng)前字典下對(duì)X中的信號(hào)進(jìn)行稀疏分解，實(shí)現(xiàn)這類稀疏表示的算法很多，如OMP、BP算法；② 更新字典中的原子，其核心為SVD算法。其中，優(yōu)化求解涉及矩陣的SVD計(jì)算，計(jì)算量很大，很大程度上限制了計(jì)算速度；當(dāng)圖像尺寸、迭代次數(shù)較大時(shí)，所產(chǎn)生的計(jì)算總量及計(jì)算消耗巨大，所需時(shí)間過長，實(shí)用價(jià)值受到較大限制，同時(shí)該算法無法確保收斂。

另一個(gè)典型的字典學(xué)習(xí)方法是OLM (Online Dictionary Learning)[8,10],其通過求解下述優(yōu)化問題來實(shí)現(xiàn)字典學(xué)習(xí)：

(3)

(1) 稀疏表示。固定字典D，隨機(jī)選取矩陣X中的信號(hào)向量，組合成信號(hào)小塊，然后求取在字典D上的稀疏表示系數(shù)YS(其中，S為選取樣本塊的索引)；

(2) 字典更新。求解下述優(yōu)化問題，更新字典D：

其中:XS表示矩陣X的子矩陣，其元素為矩陣X中所有包含索引S指代的元素。該算法運(yùn)行效率依賴于訓(xùn)練樣本的分布，當(dāng)樣本為同分布時(shí)其比KSVD算法運(yùn)行得更快，但是仍難以保證其收斂性；每步迭代涉及矩陣塊運(yùn)算，計(jì)算量很大[10]。

當(dāng)然還有很多其他字典學(xué)習(xí)的算法[11]和更為復(fù)雜的稀疏表示模型[12-14]，在此不再贅述。

本文致力于式(3)的快速求解方法的研究,其基本思路是引入加速近端梯度，采用聯(lián)合優(yōu)化策略，在每一次迭代中，更新字典和系數(shù)矩陣，加速計(jì)算，同時(shí)確保收斂。

2 基于近端梯度快速字典學(xué)習(xí)

通過字典學(xué)習(xí)，獲得的字典更適應(yīng)于自然圖像表示，能更好地表示信號(hào)。學(xué)習(xí)字典的方法有很多，如MOD[15]、KSVD、OLM等，本文采用一種新的方法來實(shí)現(xiàn)字典學(xué)習(xí)，即應(yīng)用近端梯度算法來加速求解式(3)優(yōu)化問題。

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

對(duì)于多重凸優(yōu)化問題， Xu等提出了一種基于BPG(Block Proximal Gradient)的求解方法[16]； Ma提出了一種基于APG (Alternating Proximal Gradient) 的求解方法。本文我們將結(jié)合這兩種方法來求解型如式(3)的雙凸優(yōu)化類問題：

(4)

其中：函數(shù)f可微，且對(duì)于變量x、y，當(dāng)固定其中任一個(gè)，函數(shù)f對(duì)于另一個(gè)變量為凸函數(shù)；rx、ry是值擴(kuò)充凸函數(shù)。

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

(5a)

(5b)

在滿足一些邊界條件下，文獻(xiàn)[16]證實(shí)了該算法中子序列的收斂性。假如進(jìn)一步滿足KL(Kurdyka- Lojasiewicz)[17]性質(zhì)，則式(5)生成的序列{xk，yk}全局收斂于式(4)中某一穩(wěn)定點(diǎn)。

2.2 字典學(xué)習(xí)

通過求解式(3)，從數(shù)據(jù)樣本X中學(xué)習(xí)字典。

構(gòu)建函數(shù)：

顯然，上式為式(3)中的保真項(xiàng)；將式(5)代入式(3)，即可得D、Y的更新公式：

(6a)

(6b)

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

(7a)

(7b)

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

Sτ(·)表示軟閾值算子，定義如下：

‖(D-D)YYT‖F(xiàn)≤‖YYT‖‖D-D‖F(xiàn), ?D,D

本文中，通過數(shù)值測(cè)驗(yàn)，設(shè)置Lipschitz常數(shù)和外推算法中涉及的權(quán)重：

(8)

(9a)

(9b)

其中

本文采用近端梯度算法進(jìn)行優(yōu)化求解，過程中同時(shí)更新D和Y，這區(qū)別于KSVD、OLM采用最小化方法交替更新D和Y。維持對(duì)關(guān)于D和Y子問題擁有封閉解，降低了算法每一步迭代的復(fù)雜度；同時(shí)采用上述外推設(shè)計(jì)，進(jìn)一步加速了收斂，減少了迭代次數(shù)，大大縮短了運(yùn)算時(shí)間。概述如下：

算法：基于近端梯度快速字典學(xué)習(xí)。

數(shù)據(jù)：訓(xùn)練樣本X，λ>0。

初始點(diǎn)(D-1,Y-1)=(D0,Y0)。

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

如果滿足停止條件(*)，則停止運(yùn)算，并輸出(Dk,Yk)。

2.3 收斂分析

式(3)的優(yōu)化問題等價(jià)于：

(10)

假定(D,Yk)為根據(jù)上述算法生成的序列對(duì)，如果序列{Dk}與{Yk}都一致地偏離起始點(diǎn)，那么(Dk,Yk)將收斂于(10)式或(3)式中的一個(gè)穩(wěn)定點(diǎn)。

3 數(shù)值實(shí)驗(yàn)

本文設(shè)置了2組對(duì)比實(shí)驗(yàn)，即分別與經(jīng)典的KSVD、OLM在合成數(shù)據(jù)上進(jìn)行對(duì)比實(shí)驗(yàn)。之所以選擇用KSVD和OLM作對(duì)比，是因?yàn)檫@2種算法使用廣泛，還因?yàn)檫@2種算法的效果得到充分驗(yàn)證。測(cè)試的實(shí)驗(yàn)指標(biāo)為：平均計(jì)算速度，字典學(xué)習(xí)的效率。

字典學(xué)習(xí)的效率，本文是如下界定的。從原始字典D中恢復(fù)的每一個(gè)原子d滿足：

則稱字典更新是成功的。其中，di是預(yù)測(cè)字典D的第i列。本文用字典更新成功率指代字典學(xué)習(xí)的效率。

本文算法的終止條件為：

結(jié)合文獻(xiàn)[7,10]，按下述步驟展開實(shí)驗(yàn)：

第1步，生成實(shí)驗(yàn)所需數(shù)據(jù)。首先，生成字典D∈Rn×K(即randn(n,K))，并對(duì)每一列進(jìn)行歸一化；然后，在n維空間生成p個(gè)信號(hào)，組成訓(xùn)練樣本X(X∈Rn×p)。其中，每一個(gè)樣本都是均勻地隨機(jī)選擇字典D中的r列原子進(jìn)行線性組合形成的，且組合系數(shù)是高斯隨機(jī)生成的。

第3步，取3組不同數(shù)據(jù)對(duì)(K，p)來進(jìn)行實(shí)驗(yàn)，且在每組(K，p)中測(cè)試5組不同稀疏度r下的數(shù)據(jù)，其中r的變化范圍為{4,6,8,10,12}。每組實(shí)驗(yàn)我們獨(dú)立運(yùn)行100次，然后統(tǒng)計(jì)計(jì)算其平均運(yùn)行時(shí)間(T)和恢復(fù)準(zhǔn)確率(R)。

統(tǒng)計(jì)3組實(shí)驗(yàn)數(shù)據(jù)，分別如表1所示。

表1 第1組(K，p)下3種算法實(shí)驗(yàn)結(jié)果對(duì)比

與KSVD對(duì)比，相同條件下字典學(xué)習(xí)效果相當(dāng)(即字典的更新成功率相當(dāng)時(shí))，但本文算法所用時(shí)間明顯比KSVD短，計(jì)算速度優(yōu)勢(shì)明顯；當(dāng)稀疏度r值較大(如r=12)或者訓(xùn)練樣本有限時(shí)(如，p=20n)，相同條

表2 第2組(K，p)下3種算法實(shí)驗(yàn)結(jié)果對(duì)比

表3 第3組(K，p) 下3種算法實(shí)驗(yàn)結(jié)果對(duì)比

件下本文算法字典更新成功率明顯要高，即本文算法字典學(xué)習(xí)效果顯著優(yōu)于KSVD；

與OLM對(duì)比，觀察第1組組數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如表1所示，可以發(fā)現(xiàn)相同條件下OLM字典更新成功率低于本文算法，即本文算法的字典學(xué)習(xí)效果優(yōu)于OLM的字典學(xué)習(xí)效果。后2組組實(shí)驗(yàn)中，實(shí)驗(yàn)結(jié)果如表2、表3所示，當(dāng)不考慮運(yùn)行時(shí)間，相同條件下OLM算法與本文算法字典更新成功率相近；考慮運(yùn)算時(shí)間，易于發(fā)現(xiàn)相同條件下本文算法與OLM算法字典學(xué)習(xí)效果相當(dāng)，但本文算法所用時(shí)間明顯要短，即其收斂速度更快。

4 結(jié) 語

字典學(xué)習(xí)在圖像處理等領(lǐng)域的應(yīng)用越來越廣，而算法的復(fù)雜度和收斂性很大程度上制約著字典學(xué)習(xí)應(yīng)用與推廣，也逐漸成為研究的重點(diǎn)。本文中，發(fā)展了一種新的字典學(xué)習(xí)算法，不同于其它求解字典學(xué)習(xí)問題的方法，引用了近端梯度算法來求解字典學(xué)習(xí)涉及的組合優(yōu)化問題。算法主要針對(duì)非凸光滑函數(shù)與可分離的凸函數(shù)的組合函數(shù)的優(yōu)化，采用聯(lián)合優(yōu)化，同時(shí)進(jìn)行字典原子更新和稀疏表示求解，降低了每一步迭代的復(fù)雜度，加快了計(jì)算速度，同時(shí)能夠確保收斂于穩(wěn)定點(diǎn)，具有較強(qiáng)的實(shí)用性，也為稀疏表示問題求解提供一種借鑒。

[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

河南省科技廳發(fā)展計(jì)劃(142102110088)；河南省科技攻關(guān)項(xiàng)目(No.122102210430)

張得生(1982-)，男，河南汝南人，碩士，實(shí)驗(yàn)師，主要從事計(jì)算機(jī)應(yīng)用、信息安全等研究。E-mail: zds9802@qq.com

TP 391.43

A

1006-7167(2015)11-0094-05