鄭思龍　　李元祥　　魏憲　　彭希帥

基于字典學習的非線性降維方法

鄭思龍1李元祥1魏憲2彭希帥1

目前，眾多的數(shù)據(jù)降維（Dimensionality reduction，DR）方法（如經(jīng)典的PCA（Principle component analysis），ISOMAP（Isometric mapping））能夠使降維后的數(shù)據(jù)保留原始信號的重要特征，但是從降維后的數(shù)據(jù)中很好地恢復出原始信號仍舊是一個挑戰(zhàn).近年來，稀疏表示（Sparse representation，SR）在信號重構(gòu)研究中受到廣泛關(guān)注，信號可以利用過完備字典中少數(shù)原子的線性組合來描述.本文提出一種基于字典學習的非線性降維方法.從高維輸入信號到低維特征的降維過程中，期望一些重要的幾何特征（內(nèi)積、距離和夾角）得以保留，同時又能夠從低維數(shù)據(jù)中恢復出原始信號.為達此目的，本文采用CDL（Concentrated dictionary learning）算法訓練一個字典對（高維字典D和低維字典P），使高維原始信號的能量能夠聚集于低維子空間中.字典D用來獲取稀疏表示系數(shù)，字典P是D的直接降維采樣，CDL算法能夠保證P聚集D中的大部分能量.這樣，信號的降維與恢復問題就轉(zhuǎn)變?yōu)樽值鋵Φ挠柧殕栴}，信號的降維即為從D到P的能量保留過程.實驗表明: CDL可在RIP（Restricted isomery property）條件的限制之外具有一定的信號重建能力，能在更低的維度條件下恢復圖像，優(yōu)于傳統(tǒng)的壓縮感知方法.此外，在噪聲較大的情況下，CDL圖像壓縮效果優(yōu)于JPEG2000.

數(shù)據(jù)降維，稀疏表示，壓縮感知，字典學習

引用格式鄭思龍，李元祥，魏憲，彭希帥.基于字典學習的非線性降維方法.自動化學報，2016，42（7）:1065-1076

觀測空間中的數(shù)據(jù)達到上千維甚至上萬維時，巨大的數(shù)據(jù)計算量對計算系統(tǒng)來說是一個挑戰(zhàn).對圖像、音頻、視頻和網(wǎng)絡(luò)搜索來說，通過降低數(shù)據(jù)維度來提高處理速度顯得尤為重要.

為解決“維數(shù)災難”問題，許多文獻假設(shè)數(shù)據(jù)具有低維的固有屬性（例如：低秩、稀疏性、低維流形），然后根據(jù)這些假設(shè)建立各種不同的模型.一個簡單有效的假設(shè)是：觀測數(shù)據(jù)落在一個低維流形子空間中.基于這樣的假設(shè)，利用PCA（Principlecomponent analysis）、LDA（Linear discriminant analysis）、ICA（Independent component analysis）、LPP（Locality preserving projection）等不同的線性降維算法，對高維空間做線性投影處理，以得到數(shù)據(jù)所在的子空間［1］.另一方面，非線性降維算法（例如ISOMAP（Isometric mapping）、LLE （Locally linear embedding））在降維處理中，可保留數(shù)據(jù)的非線性幾何結(jié)構(gòu)［1］.

上述兩類算法側(cè)重于挖掘和發(fā)現(xiàn)原始數(shù)據(jù)在低維空間中的內(nèi)在屬性，而對數(shù)據(jù)的恢復能力仍有待改進.壓縮感知（Compressed sensing，CS）算法的出現(xiàn)，使得我們能從更低的采樣信號中（低于奈奎斯特采樣率）較好地恢復原始信號［2］.

CS在減少觀測次數(shù)來表示一個有限維向量x∈Rm的同時，更加注重于原始信號x的稀疏性.假設(shè)y=Φx，其中Φ∈Rd×m，d?m是觀測到的信號，由于觀測矩陣Φ的行數(shù)小于列數(shù)，通過觀測信號y來獲取原始信號x是不適定的反問題.但是如果信號x在給定的字典D下足夠稀疏，那么在一定的條件下，只要維數(shù)d不低于某個限定值，觀測信號y可以唯一重構(gòu)x［3-4］.求解原始信號x在字典D下的稀疏表示α的過程可表述為

我們認為x=Dα+ε，其中ε是高斯白噪聲，α 是x在D下的稀疏表示.大多數(shù)圖像、語音等自然信號，在某些字典下都有很好的稀疏性.

式（1）所表達的稀疏編碼框架具有很強的魯棒重建能力，并且在數(shù)據(jù)壓縮、超分辨率重建、去噪、分類等領(lǐng)域成功應用.一方面，任務驅(qū)動的數(shù)據(jù)降維方法認為特定的任務（如圖像識別、數(shù)據(jù)可視化等）需要特定的降維方法將數(shù)據(jù)從高維降至低維，因此提取的特征也不一樣.文獻［5-7］認為在稀疏域中，信號的幾何關(guān)系是一種有效的結(jié)構(gòu)信息.文獻［5］通過字典學習，得到原始信號的稀疏表示系數(shù)α，利用α的幾何結(jié)構(gòu)信息，建立一個通用有效的框架來解決不同任務的字典學習問題.類似地，文獻［6］依據(jù)α的幾何結(jié)構(gòu)信息，直接利用PCA作用于稀疏系數(shù)α上，實現(xiàn)數(shù)據(jù)降維.文獻［7］有針對性地保留稀疏域中信號間的內(nèi)積關(guān)系，通過學習得到原始信號到降維信號的線性投影來完成數(shù)據(jù)降維.另一方面，數(shù)據(jù)驅(qū)動的數(shù)據(jù)降維方法采用將CS框架與高斯隨機投影結(jié)合的框架.文獻［8］利用高斯隨機矩陣將原始特征映射到觀測空間，證明在低維空間中并沒有發(fā)生重大的信息丟失，并給出結(jié)論：低維空間的特征保留了原始信號的主要信息.類似地，文獻［9-12］假設(shè)信號是在一個嵌入高維空間的低維流形中，因此在降維的過程中，一些重要的幾何信息（例如：角度、距離）得以保留.文獻［13］認為通過學習得到的觀測矩陣比隨機投影更加有效.上述基于CS框架的方法都必須服從RIP（Restricted isometry property）條件，這對于數(shù)據(jù)降維中的可視化（2D或者3D）來說是不適合的.而且，雖然文獻［9-12，14］給出了將CS框架搭建在流形上的理論分析，但是實際可行的算法很少.

上述工作都是基于一個先驗給定的字典D，不需要學習字典.更進一步的研究認為：在采樣和重建的過程中不需要知道字典D的先驗知識，而是從訓練樣本中學習字典（本文稱為“在數(shù)據(jù)降維中的字典學習方法”）.盲壓縮感知是這個框架下一個典型的例子，在嚴格的條件下，字典D可以通過低維的觀測值訓練學習而來［15-16］.文獻［17-20］認為高維信號X與低維信號Y之間，在字典Dx和Dy下共同享有稀疏表示系數(shù).字典對Dx和Dy是分別對應高維數(shù)據(jù)x和降維數(shù)據(jù)y的高維字典和低維字典，是從數(shù)據(jù)降維過程中學習而來的.

本文結(jié)合降維算法中保留數(shù)據(jù)結(jié)構(gòu)特征和CS算法中數(shù)據(jù)恢復能力的優(yōu)點，提出聚能量字典學習（Concentrated dictionary learning，CDL）算法. CDL算法既能夠在CS中RIP下界的維數(shù)限制之外具有一定的信號重建能力，又結(jié)合了流形的特點，在降維后的空間中保留原始信號中的特征（例如：內(nèi)積、距離、夾角）［21］.并且，利用訓練得到的字典，仿照CS算法設(shè)計算法框架.為驗證算法的有效性，將CDL與CS+K-SVD（K-means-singular value decomposition）［22-23］等算法進行數(shù)據(jù)恢復對比實驗，結(jié)果表明本文算法相比傳統(tǒng)算法有明顯的提升.同時，進行了圖像數(shù)據(jù)的3維觀測性實驗，本文算法表現(xiàn)良好.在噪聲污染嚴重的圖像壓縮實驗中，本文算法相對于JPEG2000，也具有一定程度的優(yōu)勢.

其余章節(jié)安排如下：第1節(jié)回顧CS算法及KSVD字典訓練算法.第2節(jié)闡述本文字典學習算法推導及思路，對于內(nèi)積、距離、夾角特征推導出字典對D和P的具體形式.第3節(jié)進行圖像重構(gòu)、3D可視化和圖像壓縮的對比實驗.最后，總結(jié)全文，討論本文算法的應用拓展性.

1　CS及字典學習回顧

本文算法基于CS算法框架，下面對CS算法框架進行簡要的回顧.CS算法框架如圖1所示，X為原始信號，Y是觀測值，Φ是觀測矩陣，α是稀疏表示系數(shù)，D是字典.典型的CS算法選取Φ為高斯隨機矩陣，Φ：Rm→Rd，d?m，y=Φx；字典D由標準正交基組成，如小波基、離散余弦變換（Discrete cosine transform，DCT）字典）.

CS通過正交匹配追蹤算法 （Orthogonalmatching pursuit，OMP）［4，24-25］解決如式（2）的最優(yōu)化問題得到稀疏系數(shù)α，最后由字典D恢復原始信號x：x=Dα.

其中，ε∈R+.在此過程中，低維觀測值y∈Rd的維數(shù)d受到一定條件的限制：d>O（Cslog（k/s）），其中，C為常數(shù)，C∈（0，1），s是稀疏系數(shù)的稀疏性，k是字典的原子的個數(shù)，這種限制被稱為RIP條件［3-4］.一旦采樣信號y的維數(shù)低于d，那么就無法從y中恢復原始信號x，或者恢復的效果很差.例如，如果需要同時將數(shù)據(jù)可視化（二維或三維）和信號恢復作為目標，那么傳統(tǒng)的CS算法遠遠滿足不了實際需求.

圖1CS算法示意圖Fig.1　CS algorithm schematic

在CS算法框架中所用到的字典往往是給定的正交基字典.不同于給定字典的思路，K-SVD算法提供了很好的字典學習方法［22-23］.從訓練集中訓練學習得到的字典比給定的正交基字典表現(xiàn)更加出色，通過字典D能夠得到最佳的稀疏系數(shù).它的優(yōu)勢主要表現(xiàn)在：

1）靈活性：能夠與任何的匹配追蹤算法相結(jié)合，確保所選的匹配追蹤算法能夠適合于所要求的時間限制；

2）有效性：K-SVD算法復雜度低，具有高效性和快速收斂性，更新字典原子和稀疏表示系數(shù)是同時進行的.

2CDL算法

以CS框架為基礎(chǔ)，利用K-SVD字典算法的優(yōu)點，本文提出基于字典學習的信號降維和重建算法.該算法可在RIP條件的限制之外具有一定的信號重建能力，即能夠從較低維的觀測值中恢復出原始信號.

原始信號x可看作是高維稀疏系數(shù)α通過字典D，在低維子空間中的一種表現(xiàn)形式.不同于觀測矩陣Φ的做法，本文直接將稀疏系數(shù)α通過映射函數(shù)P（α，y）投影到另一低維子空間y中，如式（3）所示.那么信號x與y之間的映射關(guān)系F（x，y）就可以通過稀疏系數(shù)α搭建橋梁，建立模型.理論證明該做法具有保留幾何結(jié)構(gòu)特性的作用［21］.

為了得到映射函數(shù)P（α，y），可簡單地認為α到y(tǒng)的投影是通過一個矩陣P來實現(xiàn)的.而矩陣P是通過字典D獲取的.那么式（3）可以轉(zhuǎn)為如下表達形式：

假設(shè)已知P與D的關(guān)系，那么x到y(tǒng)的映射函數(shù)F（x，y）也就確定下來.在本文中，僅考慮x和y之間的關(guān)系有：內(nèi)積、距離、夾角.那么x到y(tǒng)的降維算法就轉(zhuǎn)換為字典D到P的函數(shù)關(guān)系，如式（5）所示.維空

設(shè)間X 中R=m［x 的1，xn2，個···輸，x入n］信∈號.R給m×定n字表典示D高，α=［α1，α2，···，αn］∈.Rk×n是X在字典（Dx，y下），的n個稀疏表示系數(shù)給定映射函數(shù) F Y=［y1，y2，···，yn］∈Rd是低維空間中的特征.那么通過稀疏系數(shù)α搭建的橋梁，（X，Y）可以表示為如下形式：

其中，噪聲ε1∈Rm，ε2∈Rd.

2.1內(nèi)積關(guān)系

當期望X內(nèi)部xi與xj之間的內(nèi)積關(guān)系能在Y中保留下來時，定義將式（6）帶入其中，得到關(guān)于P的最優(yōu)化問題：

為了解決上述最優(yōu)化問題，定義核函數(shù)：

那么f2（xi，xj；yi，yj）的表示如下：

假設(shè)（xi，xj）和（yi，yj）內(nèi)部相互獨立，那么：

其中，σ1，σ2為ε1，ε2的方差，由式（11），式（7）最終轉(zhuǎn)化為求解下式：

2.2距離關(guān)系

同樣地，若期望在Y中保留X 內(nèi)部xi與 xj之間的距離關(guān)系，定義寫成如下形式：

同樣地，將式（6）帶入式（13）得到一個關(guān)于P的最優(yōu)化問題：

上式中第二部分h2（xi；yi）推導如下：

可以看出，得到的結(jié)果與內(nèi)積關(guān)系式（12）相同.

2.3夾角關(guān)系

定義X和Y內(nèi)部的夾角關(guān)系為

事實上，在處理數(shù)據(jù)集時，常常將數(shù)據(jù)集歸一化，即：||xi||2=1.可以看出夾角關(guān)系與內(nèi)積關(guān)系是相似的.

2.4理論推導

從內(nèi)積、距離、夾角關(guān)系中可看出，需要解決如下問題：

將上式重寫為

通過求解式（17）得到的特征Y的維數(shù)可以比CS算法更低，因此該算法框架可在CS算法的RIP限制之外具有恢復信號的能力［25］.

由式（18），可認為字典P是字典D的PCA降維，不妨假設(shè)：

當字典維數(shù)較低時，DCT及K-SVD字典在降維后，無法保留較多的主成分.因此，本文通過訓練字典，使得能量聚集于較低的維度內(nèi)（見圖4），保留較多的主成分，以滿足式（19）的需求.

文獻［25］中提到D與P是具有如下條件的矩陣：

且

式（21）說明，奇異值分解中的Θ總能量是保持不變的，如果Θ中靠后的（m-d）個奇異值越小，那么前d個奇異值越大.因此，為了使字典D前d維聚集更多的能量，應滿足下述條件：

1）原始信號X在字典D下表示系數(shù)足夠稀疏；

2）給定正整數(shù)q，當d＜q時，D的奇異值分

解：D=UΘVT中，關(guān)于奇異值Θ有：

其中，Θd是奇異值Θ取前d行d列，td是設(shè)定的主成分閾值.

3）為了保證D的滿秩性，要求奇異值Θ后m-d個奇異值很小卻非零.

當D滿足上述條件時，字典P可以保留字典D中較多的主成分.設(shè)D的奇異值分解為

式（19）中，取A=Ud，則有：

式（25）中，如果能夠保證Θd足夠大，即：

2.5字典訓練

通過上述分析，明確訓練字典D的兩個目標：

1）字典D要使得測試圖像在該字典下的表示系數(shù)足夠稀疏.

為了達到上述目標，利用式（25）的性質(zhì)，令：

其中

令

更新奇異值分解：D=UΘVT中Θ：

令

將上述更新過程寫作：

輸入.訓練圖集X，迭代次數(shù)T.

輸出.訓練好的字典D、P.

初始化.從訓練圖集中隨機選取16×16的圖像塊，并將每個小塊排列成列向量形式xi（256×1），令X=［x1，x2，···，xn］.初始化DCT字典D.

第一階段.稀疏編碼

1）稀疏編碼

對每一個xi，利用匹配追蹤算法得到稀疏表示系數(shù)αi［24-25］：

α←minα12||X-Dα||22+λ||α||1其中，

第α二=階［α 段1.，α字2，典···，α更n］新∈Rk×n. DDD

2）對DTD作奇異值分解：DTD=uΛvT；

5）仿照K-SVD 字典學習算法［22-23］，將Ek限定在wk集合中，得到

6）對EkR做奇異值分解做如下更新=?（1，1）n1；

第三階段.字典 PPP 計算

8）根據(jù)式（23）字典D的奇異值分解得到Ud，則字典

2.6訓練結(jié)果

圖3所示的CDL字典是利用自然圖像（如圖2所示）訓練得到的，見第3.1節(jié)描述.根據(jù)式（23）字典D的奇異值分解得到Ud（d=16），令即可得到對應的低維字典.字典P如圖3（b）所示.

CDL字典能夠?qū)⒅鞒煞旨杏谳^低的維數(shù)中，具有能量聚集的作用，如圖4所示.當選取90%主成分（td=0.9）時，CDL字典的能量集中于前16維，而K-SVD字典則需要148維，DCT字典需要207維.當字典的維數(shù)降得較低時，DCT，K-SVD字典在降維后，無法保留較多的主成分.

圖2 自然圖像示例Fig.2　Natural image examples

圖3 由CDL算法訓練得到的字典對Fig.3　Coupled dictionaries trained by CDL

圖4　不同字典奇異值的分布（當選取90%主成分（td=0.9）時，圖中的點代表所需的字典維數(shù).DCT字典: 207，K-SVD字典:148，CDL字典:16）Fig.4　Distribution of singular values from different dictionaries（When selecting 90%component of dictionaries（td=0.9），the dots represent the required dimensions for different dictionaries.DCT:207，K-SVD: 148，CDL:16）

3　實驗結(jié)果分析

為了驗證本文算法的有效性，分別從圖像重構(gòu)與數(shù)據(jù)可視化、RIP條件驗證和圖像壓縮三個方面進行實驗和分析.實驗中的圖像包括：自然圖像、USPS手寫數(shù)字和PIE人臉圖像.

3.1圖像重構(gòu)和3D可視化

本文的對比算法有：CS+K-SVD、PCA、LPP［1］.低維空間的維數(shù)分別為：d=8，16，32，64.CS+KSVD算法中，降維采樣矩陣分別用高斯隨機陣（GAU）和主成分分析（PCA）.重構(gòu)圖像的質(zhì)量評價用峰值信噪比（Peak signal to noise ratio，PNSR）表示.

1）自然圖像重構(gòu)

自然圖像集包括13張圖片［19］，尺寸為256×256或者512×512，如圖2所示.訓練時，隨機選取圖集中的圖像塊13 000個（16×16）.分別用K-SVD算法和本文CDL算法訓練字典.測試用的圖像分別為：Lena（512×512）、Boat（512×512），測試結(jié)果如圖5、圖6所示.由表1和表2可看出，CDL重構(gòu)效果明顯優(yōu)于其他算法，比CS+K-SVD（GAU）高出3 dB以上.

表1　Lena圖像重構(gòu)對比Table 1　Comparison of reconstructed Lena images

表2　Boat圖像重構(gòu)對比Table 2　Comparison of reconstructed Boat images

2）手寫數(shù)字重構(gòu)和3D可視化

手寫數(shù)字圖片來自USPS庫1，包含9298個圖片（16×16）.選取其中每類數(shù)字的一半做訓練，分別降至8，16，32和64維，利用訓練得到的CDL字典對剩余的一半數(shù)字做重構(gòu)測試.如圖7及表3所示，給出d=16時各種方法的重構(gòu)結(jié)果，并統(tǒng)計出不同方法恢復結(jié)果的平均PSNR值.表4統(tǒng)計不同維數(shù)下各方法重構(gòu)的PSNR平均值，可看出CDL的重構(gòu)效果優(yōu)于其他算法.

1http：//www.cad.zju.edu.cn/home/dengcai/Data/data.html

圖5Lena圖像重構(gòu)對比（原始圖像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、LPP、CDL，d=16）Fig.5 Reconstructed images of Lena（Original image，CS+K-SVD（GAU），CS+K-SVD（PCA），PCA，LPP，CDL，d=16）

圖6Boat圖像重構(gòu)對比（原始圖像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、LPP、CDL，d=32）Fig.6 Reconstructed images of Boat（Original image，CS+K-SVD（GAU），CS+K-SVD（PCA），PCA，LPP，CDL，d=32）

圖7　USPS手寫數(shù)字重構(gòu)對比（從上到下:原始圖像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、CDL，d=16）Fig.7　Reconstructed images of USPS（From top to bottom:original image，CS+K-SVD（GAU），CS+K-SVD （PCA），PCA，CDL，d=16）

同時，在USPS中取3類數(shù)據(jù)（數(shù)字0、3、4），共3229個.利用CDL、CS+PCA［6］和PCA算法降至3維后，給出3維平面上的數(shù)據(jù)分布，如圖8所示.圖8給出的3D可視化結(jié)果表明，通過CDL降維后的數(shù)據(jù)可分性很強，而CS+PCA由于受到RIP條件的限制，導致算法失效，具體分析見第3.2 節(jié).在圖像重構(gòu)方面，CDL仍然能夠?qū)⒔抵?維后的數(shù)據(jù)恢復，如圖9所示.

圖8　USPS手寫數(shù)字三類樣本（0、3、4）可視化結(jié)果（d=3）Fig.8　The visualization results of USPS（0，3，4）（d=3）

表3　USPS手寫數(shù)字重構(gòu)對比（d=16）Table 3　Comparison of reconstructed USPS（d=16）

表4　USPS手寫數(shù)字重構(gòu)對比（d=8、16、32、64）Table 4　Comparison of reconstructed USPS （d=8，16，32，64）

圖9　USPS手寫數(shù)字三類樣本（0、3、4）圖像重構(gòu)對比（從上到下:原始圖像、CDL、CS+K-SVD（GAU））Fig.9　Reconstructed images of USPS（0，3，4）（From top to bottom:original image，CDL，CS+K-SVD（GAU））

圖10　PIE人臉圖像重構(gòu)對比（從上到下:原始圖像、CS+K-SVD（GAU）、CS+K-SVD （PCA）、PCA、CDL，d=16）Fig.10　Reconstructed images of PIE（From top to bottom:original image，CS+K-SVD（GAU），CS+K-SVD （PCA），PCA，CDL，d=16）

3）人臉重構(gòu)

人臉圖像來自PIE庫1（16×16）.選取其中的10類樣本1700個圖片，一半用于訓練字典，另一半用于測試，分別計算將數(shù)據(jù)降至8、16、32和64維時的PSNR值，并統(tǒng)計不同方法的PSNR平均值（如圖10和表5所示）.從表5可看出在PIE上CDL也優(yōu)于其他算法.

另外，文獻［6］中提到：CS+PCA在滿足RIP條件的情況下可以得到很好的降維效果，可以用于數(shù)據(jù)可視化和數(shù)據(jù)分類.針對上述PIE庫，用本文中的字典P和直接對α做PCA降維的方法得到降維數(shù)據(jù)（d=64），本文算法可以有效恢復圖像；而文獻［6］采用CS+PCA方法，則無法恢復出原始數(shù)據(jù)（如圖11所示）.

從上述實驗可以看出，本文CDL算法的圖像重構(gòu)效果明顯優(yōu)于其他算法.

表5　PIE人臉圖像重構(gòu)對比（d=8、16、32、64）Table 5　Comparison of reconstructed PIE （d=8，16，32，64）

3.2RIP條件驗證

另外，回顧第3.1節(jié)中CS+PCA［6］在USPS數(shù)據(jù)集上3D可視化的結(jié)果（如圖8所示），在實驗中，k=784，s=10，RIP條件為：d>18.94.當維數(shù)降至3維時不滿足RIP條件限制，其低維（3D）嵌入也喪失了原始數(shù)據(jù)的可分性結(jié)構(gòu).CS算法只有在嚴格的條件限制下具有一定的信息保持能力，詳見文獻［9］.

圖11PIE人臉圖像重構(gòu)對比（從上到下:原始圖像、CS+PCA、CDL）（d=64）Fig.11　Reconstructed images of PIE（From top to bottom:original image，CS+PCA，CDL）（d=64））

圖12　Lena圖像和Barara圖像重構(gòu)對比（d=4）Fig.12　Reconstructed images of Lena and Barara（d=4）

表6　USPS手寫數(shù)字三類樣本（0、3、4）圖像重構(gòu)對比Table 6　Comparison of reconstructed USPS（0，3，4）

利用USPS數(shù)字0、3、4做圖像重構(gòu)實驗時，針對RIP條件，對比CDL和CS+K-SVD的性能.首先，分別用CDL和K-SVD訓練字典，字典規(guī)格均為256×784，即k=784.實驗中稀疏系數(shù)的稀疏性s=6，則RIP條件：d>12.7.CDL算法中利用字典P降維；CS算法中，降采樣矩陣為高斯隨機陣.實驗中兩種算法同時對數(shù)據(jù)降至12維和3維，實驗結(jié)果如圖9和表6所示.可以發(fā)現(xiàn)，當d=12時，在RIP條件臨界值附近，CS+K-SVD算法依然有效，但是當維數(shù)更低時（d=3?12），CS+K-SVD算法無法完成圖像重構(gòu)；而CDL在d=3仍然能夠恢復數(shù)據(jù).因此，CDL能夠在RIP條件限制之外仍具有較好的圖像重構(gòu)能力.

3.3圖像壓縮

從壓縮的角度出發(fā)，為了最大限度地減少數(shù)據(jù)量，在本文算法的基礎(chǔ)上，不重疊的取出測試圖像塊.實驗中，仍然取圖像塊大小為16×16，并分別降維至64、32、16、8，即分別對應壓縮比CR為 4、8、16和32.測試圖像為Lena（512×512），分別在無噪聲，添加方差為10、20、40的噪聲情況下（如圖13～圖16所示），進行壓縮重建.CDL與JPEG2000進行對比，用PSNR來評判解壓圖像質(zhì)量的優(yōu)劣，如表7～表10所示.

實驗表明：1）無噪聲時，JPEG2000解壓效果優(yōu)于CDL.2）但在噪聲環(huán)境下，CR較低時，CDL優(yōu)于JPEG2000；隨著噪聲的增加，CDL相比JPEG2000的優(yōu)勢越明顯.由于在重構(gòu)的過程中，當原始信號X通過字典D轉(zhuǎn)化為稀疏系數(shù)α表示時，此過程中存在一定去噪的功能，而Y在字典P轉(zhuǎn)化為α表示時，恢復過程同樣有一定的去噪功能.因此，本文CDL算法對噪聲具有很好的魯棒性.

表7　Lena圖像壓縮重建（無噪聲）Table 7　Comparison of reconstructed Lena（No noise）

圖13　Lena圖像壓縮重建（從左到右:原始圖像、JPEG2000（38.45dB）、CDL（30.56dB））（無噪聲，CR=16）Fig.13　Reconstructed images of Lena（From left to right:original image，JPEG2000（38.45dB），CDL（30.56dB））（No noise，CR=16）

圖14　Lena圖像壓縮重建（從左到右:原始圖像、加噪圖像（28.15dB）、JPEG2000（32.04dB）、CDL（30.24dB）（σ=10，CR=16））Fig.14　Reconstructed images of Lena（From left to right:original image，noisy image（28.15dB），JPEG2000 （32.04dB），CDL（30.24dB）（σ=10，CR=16））

圖15　Lena圖像壓縮重建（從左到右:原始圖像、加噪圖像（22.09dB）、JPEG2000（25.93dB）、CDL（29.34dB）（σ=20，CR=16）Fig.15　Reconstructed images of Lena（From left to right:original image，noisy image（22.09dB），JPEG2000 （25.93dB），CDL（29.34dB）（σ=20，CR=16））

圖16　Lena圖像壓縮重建（從左到右:原始圖像、加噪圖像（16.09dB）、JPEG2000（19.76dB）、CDL（26.96dB）（σ=40，CR=16））Fig.16　Reconstructed images of Lena（From left to right:original image，noisy image（16.09dB），JPEG2000 （19.76dB），CDL（26.96dB）（σ=40，CR=16））

表8　Lena圖像壓縮重建（σ=10）Table 8　Comparison of reconstructed Lena（σ=10）

表9　Lena圖像壓縮重建（σ=20）Table 9　Comparison of reconstructed Lena（σ=20）

表10　Lena圖像壓縮重建（σ=40）Table 10　Comparison of reconstructed Lena（σ=40）

4　結(jié)束語

本文提出一種聚能量字典學習算法，應用于圖像降維與恢復.基于字典學習的理論，本文算法通過字典對（高維字典D和低維字典P），能夠在原始信號X到特征Y的降維過程中保留高維信號的本質(zhì)特征，并且能夠在RIP條件限制之外仍具有較好的信號重構(gòu)能力.在自然圖像、人臉圖像、手寫數(shù)字上的實驗驗證了本文算法的優(yōu)越性.

從X到Y(jié)降維的同時，因為Y中保留了X的幾何結(jié)構(gòu)特征，因此可以從Y中恢復出原始信號X.算法本身并不局限于內(nèi)積、距離、夾角等特征，只要能找到合適映射關(guān)系，可推導出不同的模型，以實現(xiàn)不同任務需求：如目標識別、目標跟蹤、視頻分析等.

References

1 Van der Maaten L J P，Postma E O，Van den Herik H J. Dimensionality reduction：a comparative review.Journal of Machine Learning Research，2009，10：66-71

2 Donoho D L.Compressed sensing.IEEE Transactions on Information Theory，2006，52（4）：1289-1306

3 Cand′es E J，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on Information Theory，2006，52（2）：489-509

4 Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit.IEEE Transactions on Information Theory，2007，53（12）：4655-4666

5 Mairal J，Bach F，Ponce J.Task-driven dictionary learning.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（4）：791-804

6 Gao J B，Shi Q F，Caetano T S.Dimensionality reduction via compressive sensing.Pattern Recognition Letters，2012，33（9）：1163-1170

7 Gkioulekas I A，Zickler T.Dimensionality reduction using the sparse linear model.In：Proceedings of the 2011 Advances in Neural Information Processing Systems.Granada，Spain：Morgan Kaufmann，2011.271-279

8 Calderbank R，Jafarpour S，Schapire R.Compressed Learning：Universal Sparse Dimensionality Reduction and Learning in the Measurement Domain.Technical Report，Princeton University，USA，2009

9 Baraniuk R G，Wakin M B.Random projections of smooth manifolds.Foundations of Computational Mathematics，2009，9（1）：51-77

10 Hegde C，Wakin M B，Baraniuk R G.Random projections for manifold learning.In：Proceedings of the 2008 Advances in Neural Information Processing Systems.Vancouver，Canada：Morgan Kaufmann，2008.641-648

11 Chen M H，Silva J，Paisley J，Wang C P，Dunson D，Carin L.Compressive sensing on manifolds using a nonparametric mixture of factor analyzers：algorithm and performance bounds.IEEE Transactions on Signal Processing，2010，58（12）：6140-6155

12 Baraniuk R，Davenport M，DeVore R，Wakin M.A simple proof of the restricted isometry property for random matrices.Constructive Approximation，2008，28（3）：253-263

13 Weiss Y，Chang H S，F(xiàn)reeman W T.Learning compressed sensing.In：Proceedings of the 24th Annual Allerton Conference on Communications，Control and Computing.Illinois，USA：Citeseer，2007.535-541

14 Baraniuk R G，Cevher V，Duarte M F，Hegde C.Modelbased compressive sensing.IEEE Transactions on Information Theory，2010，56（4）：1982-2001

15 GleichmanS，EldarYC.Blindcompressedsensing. IEEE Transactions on Information Theory，2011，57（10）：6958-6975

16 Silva J，Chen M H，Eldar Y C，Sapiro G，Carin L.Blind compressed sensing over a structured union of subspaces. eprint arXiv：1103.2469，2011.

17 Zeyde R，Elad M，Protter M.On single image scale-up using sparse-representations.In：Proceedings of the 7th International Conference on Curves and Surfaces.Avignon，F(xiàn)rance：Springer，2012.711-730

18 Yang J C，Wang Z W，Lin Z，Cohen S，Huang T.Coupled dictionary training for image super-resolution.IEEE Transactions on Image Processing，2012，21（8）：3467-3478

19 Yang J C，Wright J，Huang T S，Ma Y.Image superresolution via sparse representation.IEEE Transactions on Image Processing，2010，19（11）：2861-2873

20 Adler A，Hel-Or Y，Elad M.A shrinkage learning approach for single image super-resolution with overcomplete representations.In：Proceedings of the 11th European Conference on Computer Vision.Heraklion，Crete，Greece：Springer，2010.622-635

21 Wei X，Kleinsteuber M，Shen H.Invertible nonlinear dimensionality reduction via joint dictionary learning.In：Proceedings of the 12th International Conference on Latent Variable Analysis and Signal Separation.Liberec，Czech Republic：Springer，2015.279-286

22 Aharon M，Elad M，Bruckstein A.K-SVD：an algorithm for designing overcomplete dictionaries for sparse representation.IEEE Transactions on Signal Processing，2006，54（11）：4311-4322

23 Elad M，Aharon M.Image denoising via sparse and redundant representations over learned dictionaries.IEEE Transactions on Image Processing，2006，15（12）：3736-3745

24 Pati Y C，Rezaiifar R，Krishnaprasad P S.Orthogonal matching pursuit：recursive function approximation with applications to wavelet decomposition.In：Proceedings of the 27th Asilomar Conference on Signals，Systems and Computers.Pacific Grove，USA：IEEE，1993.40-44

25 Tropp J A.Greed is good：algorithmic results for sparse approximation.IEEE Transactions on Information Theory，2004，50（10）：2231-2242

鄭思龍上海交通大學航空航天學院碩士研究生.主要研究方向為圖像處理，計算機視覺與模式識別.

E-mail:zhengsilong@sjtu.edu.cn

（ZHENG Si-LongMaster student at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.His research interest covers image processing，computer vision，and pattern recognition.）

李元祥上海交通大學航空航天學院副教授.2001年獲得清華大學電子工程系博士學位.主要研究方向為遙感圖像解譯，圖像識別，圖像重構(gòu)與評估，臺風云圖信息提取與漢字信息處理.本文通信作者.E-mail:yuanxli@sjtu.edu.cn

（LI Yuan-XiangAssociate professor at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.He received his Ph.D.degree from the Department of Electronic Engineering，Tsinghua University in 2001.His research interest covers remote sensing image interpretation，image recognition，image reconstruction and evaluation，typhoon image information extraction，and Chinese information processing.Corresponding author of this paper.）

魏憲慕尼黑工業(yè)大學電氣與計算機工程系博士研究生.主要研究方向為幾何優(yōu)化，數(shù)據(jù)表達與圖像處理.

E-mail:xianweich@gmail.com

（WEI XianPh.D.candidate in the Department of Electrical and Computer Engineering，Technische Univesitaet M¨unchen，Germany.His research interest covers geometry optimization，data representation，and image processing.）

彭希帥上海交通大學航空航天學院博士研究生.主要研究方向為圖像處理，計算機視覺，機器學習.

E-mail:xishuaipeng@sjtu.edu.cn

（PENG Xi-ShuaiPh.D.candidate at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.His research interest covers image processing，computer vision，and machine learning.）

Nonlinear Dimensionality Reduction Based on Dictionary Learning

ZHENG Si-Long1LI Yuan-Xiang1WEI Xian2PENG Xi-Shuai1

Most classic dimensionality reduction（DR）algorithms（such as principle component analysis（PCA）and isometric mapping（ISOMAP））focus on finding a low-dimensional embedding of original data，which are often not reversible.It is still challenging to make DR processes reversible in many applications.Sparse representation（SR）has shown its power on signal reconstruction and denoising.To tackle the problem of large scale dataset processing，this work focuses on developing a differentiable model for invertible DR based on SR.From high-dimensional input signal to the low-dimensional feature，we expect to preserve some important geometric features（such as inner product，distance and angle）such that the reliable reconstruction from the low dimensional space back to the original high dimensional space is possible.We employ the algorithm called concentrated dictionary learning（CDL）to train the high dimensional dictionary to concentrate the energy in its low dimensional subspace.Then we design a paired dictionaries:D and P，where D is used to obtain the sparse representation and P is a direct down-sampling of D.CDL can ensure P to capture the most energy of D.Then，the problem about signal reconstruction is transformed into how to train dictionaries D and P，so the process of input signal X to feature Y is transformed into the process of energy retention from D to P.Experimental results show that without the restrictions of linear projection using restricted isometry property（RIP），CDL can reconstruct the image at a lower dimensional space and outperform state-of-the-art DR methods（such as Gaussian random compressive sensing）.In addition，for noise-corrupted images，CDL can obtain better compression performance than JPEG2000.

Dimensionality reduction（DR），sparse representation（SR），compressed sensing（CS），dictionary learning CitationZheng Si-Long，Li Yuan-Xiang，Wei Xian，Peng Xi-Shuai.Nonlinear dimensionality reduction based on dictionary learning.Acta Automatica Sinica，2016，42（7）:1065-1076

10.16383/j.aas.2016.c150557

2015-09-02錄用日期2016-01-13
Manuscript received September 2，2015；accepted January 13，2016
國家自然科學基金（U1406404，61331015，41174164）資助
Supported by National Natural Science Foundation of China （U1406404，61331015，41174164）
本文責任編委胡清華
Recommended by Associate Editor HU Qing-Hua
1.上海交通大學航空航天學院上海200240中國2.慕尼黑工業(yè)大學電氣與計算機工程系慕尼黑D-80333德國
1.School of Aeronautics and Astronautics，Shanghai Jiao Tong University，Shanghai 200240，China2.Department of Electrical and Computer Engineering，Technische Universitaet M¨unchen，Munich D-80333，Germany