基于加權矩陣的多維廣義特征值并行分解算法

高迎彬 徐中英

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

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

滿足上述方程的向量w和標量λ分別記為矩陣束(Ry,Rx)的廣義特征向量和廣義特征值.基于特征值分解的算法是進行廣義特征值分解的傳統方法,而基于神經網絡的算法是近些年來涌現出的一類新型算法.相比傳統算法,神經網絡類算法具有計算量低、實時性強、能夠處理非平穩信號等優點[11],已經成為廣義特征值分解領域內一個主流的研究方向.

基于神經網絡,學者們提出了很多優秀的廣義特征值分解算法.例如RNNM (Recurrent neural network model)算法[12]、R-GEVE (Reduced-rank generalized eigen-decomposition extraction)算法[13]、基于NOCS (Nested orthogonal complement structure)架構的算法[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 算法是多維分解算法.由于廣義特征向量可以看作子空間的一組特殊基,因此多維分解算法也適用于子空間算法的領域;同時當多維分解算法提取維數為1 時,多維分解算法退化為單維分解算法.綜上可知,多維分解算法具有最廣泛的應用范圍[10],即研究多維分解算法更具有普適性.

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

基于加權矩陣的思想,本文提出一個多維廣義特征值并行分解算法,并詳細分析了算法的收斂性和穩定性.相比串行算法,所提算法可以實現多維廣義特征向量的并行計算,實時性較強.本文結構安排如下: 第1 節提出新型廣義特征值分解算法并對其進行收斂性和穩定性分析;第2節是仿真實驗和實例驗證;第3 節是全文的總結.

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

1.1 算法的提出

基于神經網絡模型,Oja 算法[15]首次提出了下述特征值分解算法:

其中,R∈Rn×n是信號的自相關矩陣,w∈Rn×1是神經網絡的狀態向量,η是算法的學習因子,n為輸入信號的維數.然而該算法只能估計單個矩陣R的特征向量,并非矩陣束的廣義特征向量;此外該算法只能實現單維分解,不能進行多維分解.Oja 算法是特征值分解算法領域最為經典的算法,很多現有算法在基礎理論方面和Oja 算法是相同的,因此如果以Oja 算法為代表進行研究并成功將其擴展為多維廣義特征向量估計算法,該研究結果對其他算法勢必具有很強的借鑒意義.

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

其對應的n個關于Rx正交的廣義特征向量vi(i=1,2,···,n)也相應進行排列.根據矩陣理論[16]有

其中,δij是Kroneckerδ函數.

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

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

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

1.2 算法的收斂性分析

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

定理 1.當且僅當神經網絡的狀態矩陣時,所提算法達到穩定的收斂狀態,其中,U=[v1,v2,···,vr] 是由矩陣束 (Ry,Rx) 最大的r個廣義特征值對應的廣義特征向量構成的矩陣.

證明.定義矩陣函數

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

當且僅當學習步長等于零時算法達到收斂狀態,即J(W)=0,進而有

對式(9)同時左乘WTRx,并經過適當簡化,有

由狀態矩陣W的任意性,可得

其中,Q∈Rr×r是一個正交矩陣,Σ∈Rr×r是一個對角矩陣.將式(12)代入式(9)并進行適當化簡,有

1.3 自穩定特性分析

自穩定特性是指不論初始化狀態矩陣如何選擇,狀態矩陣模值最終能夠收斂到一個固定的常值[18].由于自穩定特性可以保證狀態矩陣模值的穩定性,因此已經成為算法發展中一個重要的研究內容.接下來將對所提算法進行自穩定特性分析,為后續方便使用,首先定義如下矩陣范數.

容易證明,上述定義符合矩陣范數的規定.基于定義1,定理2 給出所提算法的自穩定特性分析.

定理 2.當輸入信號是有界的且學習因子η足夠小時,所提算法(6)中狀態矩陣W模值是自穩定的,且狀態矩陣模值‖W‖Rx的收斂值等于 t r(D).

由于η足夠小,因此省去式(14)中η的二階項.對比相鄰時刻狀態矩陣模值,有

由式(15)可得

2 仿真實驗和實例應用

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

2.1 算法能力驗證

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

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

第2 個指標是狀態矩陣列向量之間關于矩陣Rx的范數,即

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

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

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

圖4 不同列向量內積關系曲線Fig.4 The inner product curves of different column vectors

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

表1 兩種算法的計算時間Table 1 The time cost of the two algorithms

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

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

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

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

2.2 自穩定特性實驗

2.3 盲分離實驗

實驗3 將所提算法應用于解決盲分離問題,其中四個源信號取自ICALAB 工具箱中的ABio7.mat 文件[19].圖6是四個源信號的波形曲線.

圖6 源信號波形Fig.6 The waveform of source signals

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

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

圖7 觀測信號曲線Fig.7 The waveform of observed signals

圖8 分離信號曲線Fig.8 The waveform of separated signals

3 結束語

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