張得生, 張莉華

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

?

壓縮感知框架下快速字典的學習算法

張得生, 張莉華

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

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

字典學習； 稀疏表示； 近端梯度； 全局收斂; 壓縮感知

0 引 言

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

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

(1)

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

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

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

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

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

1 字典學習

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

(2)

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

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

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

(3)

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

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

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

當然還有很多其他字典學習的算法[11]和更為復雜的稀疏表示模型[12-14]，在此不再贅述。

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

2 基于近端梯度快速字典學習

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

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

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

(4)

其中：函數f可微，且對于變量x、y，當固定其中任一個，函數f對于另一個變量為凸函數；rx、ry是值擴充凸函數。

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

(5a)

(5b)

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

2.2 字典學習

通過求解式(3)，從數據樣本X中學習字典。

構建函數：

顯然，上式為式(3)中的保真項；將式(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

本文中，通過數值測驗，設置Lipschitz常數和外推算法中涉及的權重：

(8)

(9a)

(9b)

其中

本文采用近端梯度算法進行優(yōu)化求解，過程中同時更新D和Y，這區(qū)別于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)的優(yōu)化問題等價于：

(10)

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

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ǒng)計計算其平均運行時間(T)和恢復準確率(R)。

統(tǒng)計3組實驗數據，分別如表1所示。

表1 第1組(K，p)下3種算法實驗結果對比

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

表2 第2組(K，p)下3種算法實驗結果對比

表3 第3組(K，p) 下3種算法實驗結果對比

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

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

4 結 語

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

[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ā)展計劃(142102110088)；河南省科技攻關項目(No.122102210430)

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

TP 391.43

A

1006-7167(2015)11-0094-05