高迎彬 徐中英

廣義特征值分解是現(xiàn)代信號(hào)處理領(lǐng)域內(nèi)重要的分析工具,已經(jīng)廣泛應(yīng)用于多個(gè)領(lǐng)域[1-6].在工程實(shí)際中,不同的信號(hào)處理問題需要廣義特征值分解的維數(shù)是不一樣的.根據(jù)提取廣義特征向量的維數(shù),廣義特征值分解可以分為3 類[7]:1)僅能估計(jì)出矩陣束最大(小)廣義特征值對(duì)應(yīng)的廣義特征向量的單維分解算法[8];2)能夠估計(jì)出若干個(gè)廣義特征向量張成空間的子空間跟蹤算法[9];3)能夠準(zhǔn)確估計(jì)任意個(gè)廣義特征向量的多維分解算法[10].

假定存在矩陣束 (Ry,Rx),其中,Ry和Rx分別是兩個(gè)n×n維對(duì)稱正定矩陣,則廣義特征值分解就是要計(jì)算出一個(gè)n×1 維向量w和一個(gè)標(biāo)量λ,使得

滿足上述方程的向量w和標(biāo)量λ分別記為矩陣束(Ry,Rx)的廣義特征向量和廣義特征值.基于特征值分解的算法是進(jìn)行廣義特征值分解的傳統(tǒng)方法,而基于神經(jīng)網(wǎng)絡(luò)的算法是近些年來涌現(xiàn)出的一類新型算法.相比傳統(tǒng)算法,神經(jīng)網(wǎng)絡(luò)類算法具有計(jì)算量低、實(shí)時(shí)性強(qiáng)、能夠處理非平穩(wěn)信號(hào)等優(yōu)點(diǎn)[11],已經(jīng)成為廣義特征值分解領(lǐng)域內(nèi)一個(gè)主流的研究方向.

基于神經(jīng)網(wǎng)絡(luò),學(xué)者們提出了很多優(yōu)秀的廣義特征值分解算法.例如RNNM (Recurrent neural network model)算法[12]、R-GEVE (Reduced-rank generalized eigen-decomposition extraction)算法[13]、基于NOCS (Nested orthogonal complement structure)架構(gòu)的算法[9]、ANQ (Adaptive normalized quasi-Newton)算法[14]、GChen (Generalized Chen algorithm)算法[8]、GDM (Generalized Douglas minor component analysis)算法[10]等.在上述算法中,RNNM 算法、R-GEVE 算法、ANQ 算法和GCHen 算法是單維廣義特征值分解算法;NOCS 算法屬于子空間跟蹤算法;只有GDM 算法是多維分解算法.由于廣義特征向量可以看作子空間的一組特殊基,因此多維分解算法也適用于子空間算法的領(lǐng)域;同時(shí)當(dāng)多維分解算法提取維數(shù)為1 時(shí),多維分解算法退化為單維分解算法.綜上可知,多維分解算法具有最廣泛的應(yīng)用范圍[10],即研究多維分解算法更具有普適性.

在多維廣義特征值分解算法領(lǐng)域主要存在兩類算法:串行算法和并行算法.串行算法中多維廣義特征向量是依次串行獲取的,即先用單維分解算法計(jì)算出最小廣義特征值對(duì)應(yīng)的廣義特征向量,然后利用膨脹技術(shù)再計(jì)算出次小廣義特征值對(duì)應(yīng)的廣義特征向量,依次類推[10].文獻(xiàn)[8]提出了一種壓縮技術(shù),文獻(xiàn)[10]詳細(xì)分析了該壓縮技術(shù)并對(duì)其進(jìn)行了改進(jìn),實(shí)現(xiàn)了多維廣義特征向量的串行提取.相比并行算法,串行算法有如下兩點(diǎn)不足: 1)由于串行算法中廣義特征向量是串行依次提取,整個(gè)提取過程需要時(shí)間較長(zhǎng),因此串行算法不適合實(shí)時(shí)性要求較高的場(chǎng)合;2)串行算法在廣義特征向量的估計(jì)過程中會(huì)用到上一次的估計(jì)結(jié)果,而前一次的估計(jì)誤差會(huì)累積到本次估計(jì)過程中,因此會(huì)造成估計(jì)誤差的累積傳播[11].然而,目前多維廣義特征值分解算法還不多見,因此發(fā)展并行多維算法仍是非常有意義的工作.

基于加權(quán)矩陣的思想,本文提出一個(gè)多維廣義特征值并行分解算法,并詳細(xì)分析了算法的收斂性和穩(wěn)定性.相比串行算法,所提算法可以實(shí)現(xiàn)多維廣義特征向量的并行計(jì)算,實(shí)時(shí)性較強(qiáng).本文結(jié)構(gòu)安排如下: 第1 節(jié)提出新型廣義特征值分解算法并對(duì)其進(jìn)行收斂性和穩(wěn)定性分析;第2節(jié)是仿真實(shí)驗(yàn)和實(shí)例驗(yàn)證;第3 節(jié)是全文的總結(jié).

1 新型廣義特征值分解算法

1.1 算法的提出

基于神經(jīng)網(wǎng)絡(luò)模型,Oja 算法[15]首次提出了下述特征值分解算法:

其中,R∈Rn×n是信號(hào)的自相關(guān)矩陣,w∈Rn×1是神經(jīng)網(wǎng)絡(luò)的狀態(tài)向量,η是算法的學(xué)習(xí)因子,n為輸入信號(hào)的維數(shù).然而該算法只能估計(jì)單個(gè)矩陣R的特征向量,并非矩陣束的廣義特征向量;此外該算法只能實(shí)現(xiàn)單維分解,不能進(jìn)行多維分解.Oja 算法是特征值分解算法領(lǐng)域最為經(jīng)典的算法,很多現(xiàn)有算法在基礎(chǔ)理論方面和Oja 算法是相同的,因此如果以O(shè)ja 算法為代表進(jìn)行研究并成功將其擴(kuò)展為多維廣義特征向量估計(jì)算法,該研究結(jié)果對(duì)其他算法勢(shì)必具有很強(qiáng)的借鑒意義.

假定Ry,Rx ∈Rn×n是兩個(gè)信號(hào)的自相關(guān)矩陣,其廣義特征值和廣義特征向量分別為λi和vi,其中,i=1,2,···,n.為后續(xù)方便使用,這里將矩陣束 (Ry,Rx) 的n個(gè)正廣義特征值進(jìn)行降序排列,即

其對(duì)應(yīng)的n個(gè)關(guān)于Rx正交的廣義特征向量vi(i=1,2,···,n)也相應(yīng)進(jìn)行排列.根據(jù)矩陣?yán)碚揫16]有

其中,δij是Kroneckerδ函數(shù).

為了計(jì)算矩陣束 (Ry,Rx) 的多維廣義特征向量,通過對(duì)Oja 算法添加加權(quán)矩陣,提出如下的多維分解算法:

其中,W∈Rn×r是神經(jīng)網(wǎng)絡(luò)的狀態(tài)矩陣;D=diag{d1,d2,···,dr}是一個(gè)對(duì)角矩陣,其對(duì)角線元素滿足d1＞d2＞···＞dr ＞0,這里將其稱為加權(quán)矩陣;r是需要計(jì)算的廣義特征向量的維數(shù).通過式(6)給定狀態(tài)矩陣更新規(guī)則,狀態(tài)矩陣W進(jìn)行更新迭代,最終將收斂到矩陣束(Ry,Rx) 最大的r個(gè)廣義特征值對(duì)應(yīng)的廣義特征向量.

通過對(duì)式(6)進(jìn)行分析可以發(fā)現(xiàn),如果令式(6)中Rx=In和D=Ir,且進(jìn)行單維分解(即r=1),式(6)就會(huì)退化為Oja 算法.因此可以說式(6)是Oja 算法的擴(kuò)展.式(2)是單維特征向量估計(jì),如果利用文獻(xiàn)[10]中的壓縮技術(shù)將其擴(kuò)展為串行算法,則其計(jì)算復(fù)雜度為 O(n3r/3+4n2r+2nr),而式(6)是多維廣義特征向量估計(jì),其計(jì)算復(fù)雜度為O(n3/3+2n2r+2nr2),顯然要低于串行算法的計(jì)算復(fù)雜度.由于加權(quán)矩陣的加入,使得狀態(tài)矩陣在收斂過程中對(duì)廣義特征向量與其構(gòu)成子空間的夾角更為敏感[17],進(jìn)而通過在迭代過程中對(duì)神經(jīng)網(wǎng)絡(luò)狀態(tài)矩陣施加的隱形Gram-Schmidt 正交化(GS orthogonalization,GSO)操作,使得狀態(tài)矩陣能夠收斂到廣義特征向量,而非其構(gòu)成的子空間.加權(quán)矩陣僅需滿足約束條件d1＞d2＞···＞dr ＞0,在實(shí)際使用中該約束條件很容易達(dá)到(如可以取一等差數(shù)列),因此,式(6)是符合實(shí)際使用需要的.

1.2 算法的收斂性分析

算法是否能夠準(zhǔn)確地計(jì)算出矩陣束 (Ry,Rx) 的廣義特征向量,是算法發(fā)展過程中首先要解決的問題,本節(jié)將通過定理1 證明算法的收斂性.

定理 1.當(dāng)且僅當(dāng)神經(jīng)網(wǎng)絡(luò)的狀態(tài)矩陣時(shí),所提算法達(dá)到穩(wěn)定的收斂狀態(tài),其中,U=[v1,v2,···,vr] 是由矩陣束 (Ry,Rx) 最大的r個(gè)廣義特征值對(duì)應(yīng)的廣義特征向量構(gòu)成的矩陣.

證明.定義矩陣函數(shù)

其中,Λr=diag{λ1,λ2,···,λr}是一個(gè)對(duì)角矩陣,其對(duì)角線元素由矩陣束 (Ry,Rx) 最大的r個(gè)廣義特征值構(gòu)成.

當(dāng)且僅當(dāng)學(xué)習(xí)步長(zhǎng)等于零時(shí)算法達(dá)到收斂狀態(tài),即J(W)=0,進(jìn)而有

對(duì)式(9)同時(shí)左乘WTRx,并經(jīng)過適當(dāng)簡(jiǎn)化,有

由狀態(tài)矩陣W的任意性,可得

其中,Q∈Rr×r是一個(gè)正交矩陣,Σ∈Rr×r是一個(gè)對(duì)角矩陣.將式(12)代入式(9)并進(jìn)行適當(dāng)化簡(jiǎn),有

1.3 自穩(wěn)定特性分析

自穩(wěn)定特性是指不論初始化狀態(tài)矩陣如何選擇,狀態(tài)矩陣模值最終能夠收斂到一個(gè)固定的常值[18].由于自穩(wěn)定特性可以保證狀態(tài)矩陣模值的穩(wěn)定性,因此已經(jīng)成為算法發(fā)展中一個(gè)重要的研究?jī)?nèi)容.接下來將對(duì)所提算法進(jìn)行自穩(wěn)定特性分析,為后續(xù)方便使用,首先定義如下矩陣范數(shù).

容易證明,上述定義符合矩陣范數(shù)的規(guī)定.基于定義1,定理2 給出所提算法的自穩(wěn)定特性分析.

定理 2.當(dāng)輸入信號(hào)是有界的且學(xué)習(xí)因子η足夠小時(shí),所提算法(6)中狀態(tài)矩陣W模值是自穩(wěn)定的,且狀態(tài)矩陣模值‖W‖Rx的收斂值等于 t r(D).

由于η足夠小,因此省去式(14)中η的二階項(xiàng).對(duì)比相鄰時(shí)刻狀態(tài)矩陣模值,有

由式(15)可得

2 仿真實(shí)驗(yàn)和實(shí)例應(yīng)用

本節(jié)將通過仿真實(shí)驗(yàn)和實(shí)例應(yīng)用來驗(yàn)證所提算法的性能.實(shí)驗(yàn)1 考察算法多維廣義特征向量的估計(jì)能力;實(shí)驗(yàn)2 考察算法的自穩(wěn)定性;實(shí)驗(yàn)3 考察算法在信號(hào)處理中的實(shí)用性.在仿真實(shí)驗(yàn)開始前,首先隨機(jī)生成兩個(gè)對(duì)稱正定矩陣,該矩陣束 (Ry,Rx) 最大的3 個(gè)廣義特征值對(duì)應(yīng)的廣義特征向量分別如式(16)～ (18)所示(見本頁下方).

2.1 算法能力驗(yàn)證

實(shí)驗(yàn)1 分別利用所提算法和GDM 算法[10]對(duì)矩陣束(Ry,Rx)最大的3 個(gè)廣義特征值對(duì)應(yīng)的廣義特征向量進(jìn)行估計(jì),即計(jì)算v1,v2,v3.在算法的迭代過程中計(jì)算兩個(gè)指標(biāo),第1 個(gè)指標(biāo)是狀態(tài)矩陣列向量與v1,v2,v3之間的方向余弦(Directional cosine,DC),即

其中,i=1,2,3,Wi(k) 表示第k次迭代時(shí)狀態(tài)矩陣W(k) 的第i列向量.

第2 個(gè)指標(biāo)是狀態(tài)矩陣列向量之間關(guān)于矩陣Rx的范數(shù),即

兩個(gè)算法的初始化狀態(tài)矩陣是隨機(jī)產(chǎn)生的,學(xué)習(xí)因子η=0.25.GDM 算法中,參數(shù)τ=3;所提算法中,加權(quán)矩陣取D=diag{3,2,1},滿足d1＞d2＞d3＞0 的要求.在仿真過程中,為了更好地衡量算法性能,這里進(jìn)行了100 次獨(dú)立實(shí)驗(yàn),然后分別計(jì)算每次實(shí)驗(yàn)過程中數(shù)據(jù)的均值和上下界.表1 是兩種算法完成3 個(gè)廣義特征向量所需的平均時(shí)間.圖1 和圖2 分別是所提算法和GDM 算法的方向余弦曲線,其中實(shí)線是方向余弦的平均值,虛線是數(shù)據(jù)上界,點(diǎn)劃線是數(shù)據(jù)下界.為了清晰起見,圖3 和圖4 分別只給出了所提算法的列向量模值曲線(平均值)和不同列向量之間內(nèi)積關(guān)系曲線(平均值).

圖1 所提算法方向余弦曲線Fig.1 The DC curves of the proposed algorithm

圖3 列向量模值曲線Fig.3 The norm curves of the column vectors

圖4 不同列向量?jī)?nèi)積關(guān)系曲線Fig.4 The inner product curves of different column vectors

圖5 不同對(duì)角矩陣下狀態(tài)矩陣模值曲線Fig.5 The norm curves of the state matrix with different diagonal matrices

表1 兩種算法的計(jì)算時(shí)間Table 1 The time cost of the two algorithms

從圖1 中可以看出,所提算法在經(jīng)歷了最快10 次,最慢140 次,平均90 次左右的迭代運(yùn)算后,3 條方向余弦曲線均能收斂到單位1.表明不論收斂快慢,神經(jīng)網(wǎng)絡(luò)的3 個(gè)列向量均能準(zhǔn)確地收斂到3 個(gè)廣義特征向量v1,v2,v3的方向,且其對(duì)應(yīng)的廣義特征值也是按照降序排列的.從圖3中可以看出,在方向余弦收斂時(shí),狀態(tài)矩陣的各個(gè)列向量模值也都收斂到一個(gè)常值,即算法具有很好的收斂性.綜合圖1 和圖3 可以得知,所提算法能夠有效地估計(jì)矩陣束的廣義特征向量.

從圖2 中可以看出,GDM 算法是串行算法,所有廣義特征向量是一個(gè)接一個(gè)順序估計(jì)的.由于下次估計(jì)過程只有在上一次廣義特征向量估計(jì)完成后才可以開始,因此后兩次迭代開始時(shí)刻分別是200 和400,而并非0.顯然這樣會(huì)產(chǎn)生較長(zhǎng)的等待時(shí)間,且當(dāng)估計(jì)廣義特征向量維數(shù)增加時(shí),該等待時(shí)間會(huì)更長(zhǎng).

表1 中,本文所提算法的平均運(yùn)行時(shí)間是2.16 ms,遠(yuǎn)小于GDM 算法的14.61 ms.通過對(duì)比圖1 和圖2 以及綜合表1可得,由于所提算法僅需要一次迭代運(yùn)算,進(jìn)而避免了等待時(shí)間,因此計(jì)算時(shí)間較短.需要注意的是,由于串行算法需要信號(hào)采樣完成后才可以進(jìn)行運(yùn)算,而并行算法可以邊采樣邊計(jì)算,因此,實(shí)際運(yùn)行時(shí)并行算法在實(shí)時(shí)性方面會(huì)更有優(yōu)勢(shì).

此外,通過研究圖3 和圖4 中的收斂結(jié)果可以發(fā)現(xiàn):各個(gè)列向量模值的收斂值分別為 3,2,1,剛好等于加權(quán)矩陣對(duì)角線上的元素;而兩個(gè)不同的列向量關(guān)于Rx的內(nèi)積最終收斂到了零,即狀態(tài)矩陣中不同列向量是關(guān)于矩陣Rx正交的.綜合圖2 和圖3 可知,WTRxW=D=diag{3,2,1},顯然該結(jié)果與定理1 中的理論分析結(jié)果是一致的.

2.2 自穩(wěn)定特性實(shí)驗(yàn)

2.3 盲分離實(shí)驗(yàn)

實(shí)驗(yàn)3 將所提算法應(yīng)用于解決盲分離問題,其中四個(gè)源信號(hào)取自ICALAB 工具箱中的ABio7.mat 文件[19].圖6是四個(gè)源信號(hào)的波形曲線.

圖6 源信號(hào)波形Fig.6 The waveform of source signals

源信號(hào)經(jīng)過混合矩陣M,并添加加性白噪聲以后得到觀測(cè)信號(hào)x.盲分離問題就是找出合適的分離矩陣W,使得分離信號(hào)s=WTx彼此相互獨(dú)立.文獻(xiàn)[20]提出了一個(gè)基于廣義特征值分解的盲分離算法,而分離矩陣W是由矩陣束 (Ry,Rx) 所有廣義特征向量構(gòu)成的,其中Rx=E[xxT] 和Ry=E[yyT],y是一個(gè)濾波器的輸出.接下來利用所提算法求解該分離矩陣,算法的初始化參數(shù)設(shè)置與實(shí)驗(yàn)1 相同,加權(quán)矩陣取D=diag{4,3,2,1},混合矩陣為

圖7 和圖8 分別是混合后的信號(hào)和所提算法獲得的分離信號(hào).從圖7 中可以看出,經(jīng)過混合矩陣后,源信號(hào)與觀測(cè)信號(hào)具有非常大的差別.而對(duì)比圖8 和圖6 可以發(fā)現(xiàn),分離信號(hào)與源信號(hào)具有相似的波形.通過計(jì)算,四個(gè)分離信號(hào)與源信號(hào)之間的相關(guān)系數(shù)分別為0.9999,1.0000,0.9989,0.9665,即分離信號(hào)與源信號(hào)相似程度非常高,表 明所提算法能夠有效地解決盲分離問題.

圖7 觀測(cè)信號(hào)曲線Fig.7 The waveform of observed signals

圖8 分離信號(hào)曲線Fig.8 The waveform of separated signals

3 結(jié)束語

多維廣義特征值分解是應(yīng)用范圍最廣的一類廣義特征值分解算法.針對(duì)串行算法的缺點(diǎn),本文利用加權(quán)矩陣法提出了一個(gè)并行廣義特征值分解算法,并分析了算法的收斂性和自穩(wěn)定特性.與以往算法相比,所提算法可以在一次迭代過程中完成多維廣義特征向量的同時(shí)估計(jì),因此具有很好的實(shí)時(shí)性和準(zhǔn)確性.仿真實(shí)驗(yàn)和應(yīng)用實(shí)驗(yàn)表明所提算法能夠有效地估計(jì)出所需的廣義特征向量,而且能夠應(yīng)用于解決盲分離問題.后續(xù)研究將會(huì)考慮如何能夠進(jìn)一步降低算法的復(fù)雜度和加權(quán)矩陣法推廣應(yīng)用的問題,這將有利于多維分解算法的發(fā)展.