基于最小特征值的信號稀疏表示方法

王三福，劉 勍，王艷麗，王聃聃，劉 麗，李 娟

（天水師范學院 數學與統計學院，甘肅 天水 741001）

隨著人類社會的快速發(fā)展，人們生活中的信息數據量急劇增加，大數據處理已成為整個世界面臨的重大課題，人們想盡各種辦法來壓縮數據的存儲量.信號的稀疏表示問題成為數字信號處理的熱點問題和處理大數據的重要手段.關于信號的稀疏表示問題，已經有很多相關的模型被構建，有力地推動了人工智能領域中智能學習的研究.

2011年Boaz Ophir,Michael Elad等人，在歐洲的信號處理會議（European Signal Processing Confer?ence）上，發(fā)表論文“Sequential minimal eigenval?ues-an approach to analysis dictionary learning”，提出了最小特征值方法（SME）.[1]目前該論文被引用62次，在信號稀疏表示領域具有一定的影響力.2013年由Rubinstein和Elad等人提出了Analysis K_SVD模型，[2]從另外一個視角研究了信號的稀疏表示問題.將K_SVD算法引入到分析字典學習模型中，收到良好的效果.

稀疏表示及其計算已經是在信號處理和圖像處理方面的眾所周知的熱點問題，[3-8]信號的稀疏表示為提供了一種用低維數據表達高維數據各種信息的手段.[9,10]2019年王凱等人將信號的稀疏表示用于相干信號測向，[11]2020年司韋建等人將數字信號的稀疏表示應用于參數估計，[12]這對信號稀疏表示的應用研究具有推動作用.

關于信號的稀疏表示模型，主要有合成模型與分析模型兩個研究方向.目前的方法都存在對稀疏度控制不夠靈活的問題.本文結合了最小特征值方法與矩陣偽逆計算方法，提出了求解信號稀疏表示合成模型的最小特征值偽逆方法.既加快了數字信號稀疏表示的運算速度，也增加了對稀疏度控制的靈活性.

1 稀疏表示模型

把研究的信號的全集記為Φ，將信號樣本訓練集V(V1,V2,…,Vn)(Vi∈Φ)，分解為字典D(D1,D2,…,Dn)與系數矩陣X(X1,X2,…,Xn)的乘積，即為

其中，字典D的每一列Di稱為字典的一個原子，X的每一列Xi就是對應信號Vi的一組系數，有Vi=DXi.由于

所以要求系數X是列稀疏，也就是X的第i列(x1i,x2i,…,xki)T作為Vi的系數有很少的非零元素.這樣，信號Vi可由很少個字典原子的線性組合來表示，可見字典D的構造成為圖像稀疏表示問題中的關鍵環(huán)節(jié).

1.1 稀疏表示的合成模型

對于一個未知信號x∈Rd，觀察到的v∈Rm往往是它的某種線性變換后的近似結果（m＜d），即

其中e∈Rm是滿足的加性噪聲.這里的任務是利用觀察到的一組數據V(V1,V2,…,Vn)，得到變換矩陣D和原信號X(X1,X2,…,Xn).若不計加性噪聲（e=0），則問題變成：已知樣本V，求矩陣D和X，使得

為了表示一個信號v∈Rm，需要一個字典D∈Rm×k，D的每一列就是一個原子，它由k個原子組成，即D(D1,D2,…,Dk).其表示過程為：

其中列向量Xi為信號Vi在字典D下的表示系數.如果Xi的非零元素很少，則Xi稱為Vi的稀疏表示.在稀疏表示中，字典D是非常重要的，字典D的獲得，通常使用已有的n個樣本數據V(V1,V2,…,Vn)進行訓練得到的.

增加了系數的稀疏性約束條件，該問題可以表示為

該模型稱為信號稀疏表示的合成模型（synthe?sis model）.

1.2 稀疏表示的分析模型

已知n個樣本信號V(V1,V2,…,Vn)，需要求解一個線性變換Ω:Rm→Rp，使變換結果為

其中‖*‖0為向量的非零個數，公式（8）表示相乘后的向量的非零元素很少.

設Xi的長度為p，Xi的稀疏度即零元素個數為l，則

使得列向量Xi是稀疏的，這種模型稱為信號稀疏表示的分析模型（analysis model）.

分析求解稀疏表示的分析字典的基本原理.

對于一組信號V(V1,V2,…,Vn)∈Rm×n，尋找一個分析的字典Ω∈Rp×n，使得字典乘以樣本信號，能夠得到一個稀疏的表示.

目前，解決稀疏表示分析模型最典型的方法是最小特征值方法（SME）.

1.3 分析模型的最小特征值方法（SME）

對于已知信號樣本V(V1,V2,…,Vn)，要求矩陣Ω∈Rp×n，使得

其中p為Xi的長度，l為Xi的稀疏度即零元素個數.

設X(X1,X2,…,Xn)=ΩV，由于列向量Xi中至少有l(wèi)個零元素，所以，X中至少共有n×l個零元素.X有p行，平均每行有個零元素.

設Xi為矩陣X的第i行，則X可以表示成

設ωi為矩陣Ω的第i行，則

現已知V，求ωi，使得（12）式中行向量Xi有個零元素.

行向量Xi的第j個元素，是行向量ωi與V的第j列的乘積，找到一個與V的第j列正交的向量作為ωi，行向量Xi的第j個元素自然就為零了，因為正交向量乘積為零.為了達到稀疏度的要求，要找的行向量ωi至少要和V中的個列向量正交，才能保證Xi中有個零元素.

于是，利用最小特征值，在V中選取恰當的列向量，構成矩陣V∧.

設矩陣V∧V∧′的特征值從小到大為(t1,t2,…)，它們對應的特征向量分別為(T1,T2,…)，于是它們滿足公式

只有選擇最小特征值時，tk(V∧V∧′)等于零或最接近零，就把最小特征值對應的特征向量作為行向量ωi.

接著計算行向量Xi=ωiV，將Xi中最小的個元素設為零，并將這些元素的位置標號記做∧，重新構造V∧V∧′，再重復以上的工作，直到ωi收斂.這樣就可以得到滿足稀疏要求的分析字典Ω的第i行ωi了.

求解Ω中的第i行ωi的方法是用迭代法，具體步驟如下:

第一步，隨機產生向量ω1；

第二步，計算Xi=ωiV.i=1,2,…；

第三步，將Xk中的最小的個元素設為零，并將這些元素的位置標號記做∧，在V中找到與∧對應的列，構造矩陣V∧′；

第四步，計算V∧V∧′的特征值和對應的特征向量，設最小特征值為α，它對應的特征向量為ωk+1；

第五步，如果‖ωk+1-ωk‖2大于一個預定的很小的正數，則轉到二步繼續(xù)循環(huán).否則，停止循環(huán)，所得的ωk+1就是要求的行向量ωi.

具體算法見算法1-1.

算法1-1求解Ω中的一行ωi的方法（1）輸入訓練樣本V，確定閾值θ0，初始閾值較大，為θ；（2）做循環(huán)直到θ≤θ0；（2.1） 隨機產生長度為m的向量ω，做以下四步循環(huán)，直到ω收斂.（a） T=ω*Y ；（b）找出T中最小的nl p個零元素組成向量T∧，令θ T的特征值和對應的特征向量；（d）將ω更新為Y∧Y∧T的最小特征值所對應的特征向量；（2.2）結束ω的循環(huán).（3）結束θ的循環(huán).為T∧中的最大值；（c）將T∧對應的Y中的列構成矩陣Y∧，計算Y∧Y∧

有了計算分析字典Ω中的第i行ωi的方法，那么，令i從1到p，就可以得到整個分析字典Ω.利用矩陣的最小特征值來計算分析字典的算法記為SME算法，具體算法見算法1-2

算法1-2 SME算法（1）輸入訓練樣本V，令V1=V；（2）所求分析字典矩陣Ω有p行，做循環(huán)i=1,2,…,p；（2.1）以Vi為樣本，運行算法1-1，得到m維向量ω.讓Ω的第i行等于ω；（2.2）修改訓練樣本Vi得到Vi+1（a）當i＜l時，從Vi中移除與Ω中的前i行都正交的所有列，得到Vi+1；（b）當i＞l時，從Vi中移除這樣的列，它與Ω的前i行中的至少l行正交，得到Vi+1；（c）當i=l時，Vi+1=V.（3）結束i循環(huán)，得到分析字典矩陣Ω.

1.4 最小特征值方法（SME）的收斂性證明

對于文獻[1]中的SME算法，文章中沒有給出該算法的收斂性證明.為了保證該算法的可靠性，本文給出此迭代方法的收斂性證明.

要證明信號稀疏表示的分析字典的最小特征值（SME）算法的收斂性，就要從矩陣的特征值入手，給出以下引理.

2 基于最小特征值和偽逆的稀疏表示方法

在信號的稀疏表示中，通過對樣本信號的訓練，得到稀疏表示的字典和稀疏系數是的目的.本節(jié)將利用1.3中分析模型得到的結果，以及矩陣的MP-逆運算，從而得到一種新的合成模型的求解方法，記作SMEMP算法.

2.1 MP-逆

偽逆是矩陣計算中的基本運算，對信號稀疏表示的計算也有重要的使用價值.

2.2 合成模型的求解方法

對于某一類信號（如人臉圖像、語音等），需要一個字典D，對其中的每個信號進行稀疏表示.字典的獲得一般采用對樣本信號V的訓練和學習.而本文利用信號稀疏表示的分析算法，得到分析字典矩陣Ω，進而采用矩陣MP-逆的方法，得到信號稀疏表示合成模型的字典D，這就是本節(jié)的SMEMP算法.

對于信號的稀疏表示問題，構建的優(yōu)化模型是：

其中已知V，求D和X，使得V≈DX，即‖V-DX‖最小.

首先，利用1.2中的最小特征值方法，得到關于樣本V的分析字典矩陣Ω，使得

其中X的第i列是V中的第i個樣本的系數，由信號稀疏表示分析模型可知，結果X是列稀疏的.

其次，計算Ω的偽逆Ω+，使得Ω+ΩV=V.從而得到信號稀疏表示的合成模型的分解結果：

其中D=Ω+是稀疏表示合成模型的字典矩陣，X為稀疏的系數.

具體的算法見算法2-1的SMEMP算法.

算法2-1 SMEMP算法（1）輸入訓練樣本V，令V1=V；（2）利用SME算法，求解分析字典Ω；（3）計算Ω的偽逆Ω+；（4）輸出字典矩陣Ω+和稀疏系數H=ΩX.

2.3 合成模型求解算法的收斂性證明

為了證明收斂性，先提出如下引理.

引理 2.2給出矩陣A∈Rm×n,B∈Rm×p，那么，矩陣方程AX=B可解，當且僅當AA+B=B.這時，方程的解為

其中Z∈Rn×p為任意矩陣.顯然，X=A+B是最小范數解.

矩陣方程AX=B是可解的，那么，最小二乘解XLS與公式（24）相同，且XLS=A+B是最小范數的最小二乘解.

定理2.2設有樣本信號矩陣V∈Rm×n，則存在信號稀疏表示的矩陣分解V=DX(D∈Rm×k,X∈Rk×n)，使得X是列稀疏的.

證明這是一個迭代的證明過程.

對于樣本矩陣V∈Rm×n，我們任意構造一個矩陣的分解V=D0X0，這里X0并不滿足稀疏性要求.

設X0是算法1-2中的訓練數據.對任意給定的隨機初始向量ω0∈Rd，利用分析算子Ω0，能得到稀疏矩陣X1≈Ω0X0，使X1的稀疏度滿足我們的要求.利用引理2.2，我們可得X0=Ω0+X1，代入V=D0X0得

同樣地，得到另一個分析矩陣Ω1，使得X2≈Ω1X1，比X1更稀疏，即

經過k次迭代后，假定Xk滿足稀疏度的約束條件，則停止迭代.最后得到

公式（27）就是滿足稀疏約束的收斂性結果.

3 數值實驗

這部分實驗主要是驗證算法1-2的功能.實驗用的環(huán)境為：聯想，Pentium?雙核CPU，內存2.0GB，WIN7系統，MATLAB7.0.1編程軟件.

3.1 利用SME算法獲取字典和稀疏系數X

實驗1隨機產生一個矩陣V(40,80)，并隨機產生字典D(40,60)的初值.利用算法1-2計算，得到最終字典D(40,60)，并得到稀疏的系數X(60,80).為了顯示X的稀疏性，隨機選取了X中的四列系數顯示如圖1.

圖1 稀疏的系數X的條形顯示（隨機選擇4個）

在實驗過程中，把系數的稀疏度參數設置在20%以內.根據這個實驗的結果，長度為60的系數，非零元素有11個左右.

實驗2隨機產生一個矩陣V(50,200)，并隨機產生字典D(50,100)的初值.利用算法1-2計算，得到字典D(50,100)，并得到稀疏的系數X(100,200).為了顯示X的稀疏性，隨機選取了X中的四個系數顯示，如圖2.在這個實驗過程中，為了觀察系數的稀疏度的可控性，把系數的稀疏度參數設置在12%以內.實驗的結果表明，長度為100的系數，非零元素有10個左右，達到了稀疏表示的目的.

圖2 稀疏的系數X的線形顯示（隨機選擇4個）

3.2 利用SMEMP算法對信號進行稀疏分解

為了檢驗合成模型求解算法的功能，隨機產生一個矩陣V(100×120).首先，用SME分析模型求解算法，得到矩陣Ω.稀疏的系數X為

其次，計算Ω的MP-逆矩陣Ω+，使得

則對信號矩陣V進行稀疏分解的字典為D=Ω+，且系數X滿足稀疏度.

利用算法2-1計算，得到字典D(100×90).用字典D和系數X相乘，就可以得到恢復的數據V*，將V*和原數據V相比較，如圖3，隨著迭代次數的增加，恢復的數據與原數據的誤差將逐漸減小.在實驗中，將稀疏度進行調整，讓系數中的零元素逐漸增多，恢復的數據與原數據的誤差將逐漸增大，如圖4.

圖3 恢復的數據與原數據的誤差

圖4 隨著系數中零元個數增加，信號分解的誤差增大

4 結論

本文是在研究信號稀疏表示的基礎上，尋找到一種構造稀疏表示字典的新方法.先利用SME方法求解稀疏表示的分析模型，再將所得結果求解它的偽逆，即可求解稀疏表示的合成模型，得到稀疏表示的字典.經過數值模擬實驗的檢驗與分析，該方法具有運算速度快、稀疏度可控的優(yōu)勢.同時，由于程序中要計算偽逆，如果遇到偽逆不存在，將會使計算無效.對這種異常情況的處理，有待于進一步研究.