K-L變換觀測矩陣優化算法

王海艷，佟 岐，連志鵬，汲清波

1.哈爾濱工程大學 信息與通信工程學院，哈爾濱 150001

2.北京航天發射技術研究所，北京 100076

1 引言

傳統的奈奎斯特（Nyquist）采樣定理表明為了不失真的重構出模擬信號，離散信號系統的采樣頻率必須至少是模擬信號帶寬的兩倍。然而隨著人們對信息需求量的增加，信號帶寬也隨之不斷的增加，導致人們對信號的采集變得越來越困難。近年來由Candès、Donoho和華裔科學家Tao等人提出的壓縮感知（Compressed Sensing，CS）理論[1-2]，不受奈奎斯特采樣定理中采樣速率至少是信號帶寬兩倍的局限，該理論通過投影觀測得到較少觀測數據，然后利用重構算法求解優化問題從而高概率地從壓縮觀測數據中重構原始信號。CS理論直接采集壓縮后的數據，避免了先采樣后壓縮編碼而產生大量冗余信息的情況。它在減少冗余數據，節省存儲空間上具有較大的優勢。

壓縮感知理論中包含三個重要組成部分：信號的稀疏表示、觀測矩陣的構造、重構算法的設計[3]。其中觀測矩陣的構造對信號的重構至關重要，合理的觀測矩陣可以高精度的重構出原始信號，目前常用的觀測矩陣包括隨機高斯矩陣、隨機伯努利矩陣、隨機傅里葉矩陣等[4]。這些直接構造出的觀測矩陣所產生的性能并不是最優的，所以許多學者針對觀測矩陣的優化進行了研究。研究表明優化觀測矩陣的方法之一是減小觀測矩陣與稀疏矩陣之間的互相關性[5]，根據此方法，Xu[6]、Abolghasemi[7]、Tian[8]等人提出了相應的優化觀測矩陣的算法，這三種算法都是利用迭代的思想對觀測矩陣進行優化，但存在迭代次數較多，運算量較大，并且在觀測數據較少的情況下重構圖像質量較差的問題。針對這些缺點，本文提出了K-L（Karhunen-Loeve）變換觀測矩陣優化算法，該算法通過對傳感矩陣（觀測矩陣與稀疏矩陣的乘積）進行K-L變換來減小觀測矩陣與稀疏矩陣之間的互相關性，從而實現優化觀測矩陣的目的。最后通過實驗驗證了K-L變換觀測矩陣優化算法的性能。

2 壓縮感知理論

壓縮感知的理論基礎為信號本身是稀疏的，或者信號在某一變換域是可壓縮的，因此信號的稀疏表示是壓縮感知理論首要的研究任務。 稀疏信號是指信號本身絕大多數元素為零或近似等于零，或者在某一變換域上絕大多數元素為零或近似等于零的信號。假設x是一個長度為N的實值一維離散信號，記為x∈RN×1。信號x可以稀疏表示成一組正交基的線性組合：

利用一個與稀疏矩陣Ψ不相關的矩陣Φ對信號x進行線性隨機投影得到觀測量y：

由上式可以很自然地想到利用解線性方程組的方法求解x，但是由于觀測矩陣Φ的維度M＜N，所以通過式（2）中y的M 個觀測值求解x是一個病態問題，方程無解或有無窮多個解。將式（1）帶入式（2）得：

式中，D是M×N(M＜N)矩陣，稱為傳感矩陣。

因為上式中的s是稀疏的，只有K(K?N)個值不為零，所以信號的重構表示為：

式中，求解l0最小范數是一個NP難的非凸優化問題。由Candès和Donoho提出的l1范數下的凸優化壓縮感知重構框架，將式（4）的非凸優化問題轉變成了一個凸優化問題：

通過凸優化算法[9]便可求出s的近優解。

3 K-L變換優化觀測矩陣

觀測矩陣的設計是為了將信號從N維投影到M維(M＜N)從而獲得M個觀測值，并保證這M個觀測值中包含了重構信號的足夠信息，以便可以成功地重構出原始信號或者稀疏系數向量[10]。為了能夠從獲得的觀測值中準確的重構原始信號，Candès和Tao提出并證明了觀測矩陣Φ必須滿足有限等距性（Restricted Isometry Property，RIP）條件[11]，RIP等距特性在觀測矩陣Φ的構造與優化中具有重要意義[12-13]。但是RIP等距特性很難直接應用，Baraniuk在文獻[14]給出了RIP準則的等價條件為觀測矩陣Φ與稀疏矩陣Ψ幾乎不相關，因此減小觀測矩陣與稀疏矩陣之間的互相關性可以提高信號的重構概率。

對于觀測矩陣的優化，首先將觀測矩陣與稀疏矩陣之間的互相關系數μ定義為：

式中，di、dj為傳感矩陣D中的任意兩列向量。互相關系數μ代表著觀測矩陣與稀疏矩陣之間的相關性，μ的值越大代表兩個矩陣的相關性越大，那么重構出的原始信號質量越差，為了能夠較高精度的重構原始信號，希望μ的值盡量減小。同時，互相關系數還影響著信號的可稀疏度界限[15]。

式（7）表明觀測矩陣與稀疏矩陣之間的互相關性越小，則稀疏系數s的上界限越大，所以越有利于原始信號的重構。本文的主要思想是通過對傳感矩陣D進行K-L變換，來減小觀測矩陣與稀疏矩陣之間的互相關性。

K-L變換又稱為特征矢量變換或霍特林（Hotelling）變換，它是以原始數據協方差矩陣的特征向量構成的正交矩陣作為變換矩陣，對原始數據進行正交變換。用原始數據協方差矩陣的特征向量構成的正交矩陣作為變換矩陣，會使變換后數據的協方差矩陣中除對角線之外大部分協方差等于零或者近似等于零，即原來像素間的相關性在很大程度上被減弱。K-L變換的原理是設為N×1維隨機矢量，mX=E(X)和分別為其平均值向量和協方差矩陣，ei和λi分別為CX的特征向量和特征值，其中i=1,2,…,N，則K-L變換式為Y=AX。其中變換矩陣A的每一行為協方差矩陣CX對應于特征值λi的特征向量，即

式中，eij(i,j=1,2,…,N)表示第i個特征向量的第 j個分量，滿足A×AT=I，其中I表示單位陣。

根據K-L變換式Y=AX得到Y的平均值為：

Y的協方差矩陣為：

因為A×AT=I，所以Y的協方差矩陣進一步化簡為：

由上述推導得到變換后的矢量Y的協方差矩陣是對角矩陣，除對角線以外其他的元素全部等于零，即

在協方差矩陣中主對角線上的元素σi2(i=1,2,…,N)表示各分量的方差，它代表著各分量能量的大小以及離散程度。方差越大分量的能量越大，分布越離散，而主對角線以外的元素表示分量Yi與分量Yj之間相關程度的協方差，對角矩陣表明了經過K-L變換得到新的分量Yi與Yj彼此之間的相關性在很大程度上被減弱，對角矩陣中主對角線上的方差分布為從大到小，即代表變換后的矢量Y中前面分量比后面分量的能量大，離散程度高。

變換后的矢量為Y=(Y1,Y2,…,YN)T，Y中各分量如下所示：

由上式看出，實際上K-L變換是使原始矢量X中各個分量加上一個權重系數，實現線性變換，重新組合成了矢量Y。它是綜合了原來各個分量的信息，并不是對原始矢量進行簡單的取舍，從而使矢量Y可以較好的反映事物的本質特征。

由于K-L變換是對一維信號的變換，所以在對二維圖像信號進行變換時，本文將圖像按照每一行都為一個一維信號的原則，從上到下依次對圖像的每一行進行K-L變換，具體方法如下所示：

這樣便可以使用K-L變換對M×N維傳感矩陣進行變換，進而得到優化后的觀測矩陣。

K-L變換優化觀測矩陣的步驟如下。

1.初始化i=1；

a.將傳感矩陣D的第i行轉置得到d′，計算d′的均值u=E(d′)，協方差矩陣Cd′=E{(d′-u)(d′-u)T；

b.Cd′Vj=λjVj，1≤j≤N ，式中 λj是特征值并且 (λ1＞λ2＞…＞λN)，相應的特征向量是 Vj，特征向量矩陣為V=[V1V2…Vn]；

c.將V 正交化得V*，變換矩陣A=V*T；

d.變換后的 d′=V*T(d′-u)=A(d′-u)；

e.變換后的傳感矩陣D(i,:)=d′T；

2.i=i+1，如果 i=I，則執行（3）；否則執行第1步的a；

3.更新 DI=D(i,:)；

4.計算ΦI=DI×Ψ-1；

輸出：優化后的觀測矩陣Φ=ΦI

4 實驗結果

為了驗證所提算法優化觀測矩陣的有效性和可靠性，本文選取一幅大小為256×256的Lena圖像進行仿真實驗。實驗中稀疏矩陣Ψ選取DCT稀疏基，重構算法選用凸優化類算法中的BP算法[9，16]，本次實驗中定義M=102，即觀測矩陣的大小為102×256，采樣率r≈0.4，分別用隨機高斯矩陣和本文算法優化后的隨機高斯矩陣作為觀測矩陣，對Lena圖像進行仿真實驗，得到的仿真效果圖如圖1所示。

圖1 優化算法在采樣率為0.4時重構圖像效果圖

從圖1仿真結果可知，利用本文算法優化后的觀測矩陣重構圖像的PSNR值大于利用未優化的觀測矩陣重構圖像的PSNR值，這里以PSNR值的大小來衡量圖像重構質量的優劣，比較重構出的兩幅圖像可以看出由本文算法優化后的觀測矩陣重構出的Lena圖像具有更加清晰的輪廓。由以上分析可知，所提優化算法可以對觀測矩陣進行優化。

在以上實驗的基礎上，只改變觀測數目M的大小來驗證本文算法優化觀測矩陣的可靠性，表1中列出了在M為26～126的情況下，分別利用優化后的隨機高斯矩陣和未優化的隨機高斯矩陣為觀測矩陣重構出Lena圖像的PSNR值。從表1中可以看出隨著觀測數目的增加，由兩個觀測矩陣重構圖像的PSNR值都隨之增大。但是在不同的觀測數目下，利用本文算法優化后所得觀測矩陣重構圖像的PSNR值始終大于未優化的隨機高斯矩陣重構圖像的PSNR值，即證明了利用所提優化算法優化觀測矩陣的可靠性。

表1 不同觀測數目下優化后觀測矩陣與未優化觀測矩陣重構圖像的PSNR值比較

為了進一步說明所提優化算法的性能，繼續進行本文算法和Xu算法、Vahid算法以及Tian算法的比較實驗，本次實驗選取兩幅大小均為256×256的Lena圖像和Mandi圖像進行仿真實驗。實驗中稀疏矩陣Ψ依然選取DCT稀疏基，觀測矩陣Φ分別選用本文算法、Xu算法、Vahid算法以及Tian算法，重構算法依然采用凸優化類算法中的BP算法，用PSNR值的大小來代表兩幅圖像的重構質量。本次實驗在采樣率r=0.5的情況下，得到的仿真結果如圖2所示。

從圖2和圖3可以明顯的看出，用本文算法優化后的觀測矩陣重構圖像的PSNR值大于用其他三種算法優化后的觀測矩陣重構圖像的PSNR值。從圖中可以看出，由本文算法優化后的觀測矩陣重構出的圖像具有更加清晰的視覺效果，重構的兩幅圖像帽子邊沿、眼睛以及胳膊等部位的輪廓更加清晰，這說明相比較其他三種優化算法優化的觀測矩陣，用本文算法優化后的觀測矩陣重構圖像的質量和視覺效果最好。

圖2 不同算法在采樣率為0.5時重構Lena圖像效果對比

圖3 不同算法在采樣率為0.5時重構Mandi圖像效果對比

表2為在采樣率r=0.5時，重構算法為凸優化類算法中BP算法的情況下，對兩幅大小為256×256的Lena圖像和Mandi圖像進行仿真實驗，對比各算法對圖像重構時間的長短。從表2中可以看出，與Xu算法、Vahid算法、Tian算法優化后所得觀測矩陣以及未優化的隨機高斯矩陣重構圖像所用的時間相比，利用本文算法優化后所得觀測矩陣重構的兩幅圖像所用的時間最短。這意味著，和文中所提其他優化算法相比，本文算法在不增加重構時間的基礎上可以得到更高質量的重構圖像。

表2 不同算法在采樣率為0.5時重構圖像時間對比

對比四種算法優化后的觀測矩陣以及未優化的隨機高斯矩陣，在采樣率為0.2～0.65之間對Lena圖像和Mandi圖像重構的重構誤差值，兩幅圖像重構誤差曲線圖如圖4所示。

圖4 各優化算法在采樣率為0.2到0.65之間兩幅圖像重構誤差關系曲線

圖5 各優化算法在采樣率為0.2到0.65之間兩幅圖像重構的峰值信噪比關系曲線

從圖4可以看出，在采樣率為0.2～0.65之間，隨著采樣率的增加4種算法優化后的觀測矩陣以及未優化的隨機高斯矩陣對于圖像的重構誤差都逐漸減小。在采樣率為0.2～0.5之間，利用本文方法優化后的觀測矩陣與另外三種方法優化后的觀測矩陣以及未優化的隨機高斯矩陣相比具有更低的圖像重構誤差，圖像的重構誤差越小代表著圖像的重構質量越高。由仿真圖可知，在采樣率為0.5～0.65時，相比于另外三種方法優化后的觀測矩陣以及未優化的隨機高斯矩陣重構圖像的重構誤差，利用本文方法優化后的觀測矩陣重構圖像的重構誤差存在優劣交替的不穩定現象。兩幅圖像重構的峰值信噪比值曲線圖如圖5所示。

從圖5中可以看出，所有的方法重構得到的PSNR值都隨著采樣率的增加而增大，這是因為采樣率增加所得到的觀測數目隨之增多，采樣得到原始信號的信息也會隨之增加，所以重構信號的PSNR值越大，即重構質量越好。相比較來說，本文方法在采樣率為0.2～0.5的時候重構質量最好，這說明使用本方法重構的觀測矩陣在較少的觀測數據下就可以較好的重構出原始信號。由仿真圖可知，在采樣率為0.5～0.65時重構質量幾乎持平于Xu方法、Vahid方法以及Tian方法。通過分析以上仿真實驗結果，得出了在觀測數目較少的情況下，本文算法相對于文中所提其他算法對圖像的重構具有更好的效果。

5 結束語

根據減小觀測矩陣與稀疏矩陣之間互相關性的思想，本文提出了利用K-L變換減小觀測矩陣與稀疏矩陣之間的互相關系數來優化觀測矩陣的方法。通過對實驗結果進行分析，本文提出的觀測矩陣優化算法能夠對觀測矩陣進行優化，利用本文所提優化算法優化后的觀測矩陣重構出的圖像具有較高的精度，尤其是在采樣率較小時本文提出的優化算法相對于其他優化算法的優勢更加明顯，這將為今后在壓縮感知方面的研究工作提供一定的參考。