利用參數結構的快速非酉聯合對角化算法

劉文娟,馮大政,袁明冬

(西安電子科技大學雷達信號處理國家重點實驗室,710071,西安)

?

利用參數結構的快速非酉聯合對角化算法

劉文娟,馮大政,袁明冬

(西安電子科技大學雷達信號處理國家重點實驗室,710071,西安)

針對基于快速Frobenius范數對角化(FFDIAG)的盲信號分離算法不能直接處理復數數據從而導致分離性能差的問題,提出一種利用參數結構的快速非酉聯合對角化(PSJD)算法。該算法首先將由觀測信號的統計量得到的復目標矩陣轉化為實對稱矩陣;通過對代價函數的二階近似,將解聯合對角化問題轉化為一系列的線性最小二乘問題,直接得到更新矩陣元素的估計。在每次迭代中,通過充分利用轉化后的目標矩陣的結構信息,減少估計分離矩陣及更新目標矩陣的計算復雜度。同時,針對FFDIAG算法采用的固定步長難以兼顧收斂速度與更新矩陣嚴格對角占優性的問題,采用僅由當前更新矩陣的估計值決定的自適應學習率,提高算法的收斂性能。仿真實驗表明,在一定的取值范圍內,PSJD算法的收斂速度對步長參數的變化不敏感,在步長參數同為0.1的情況下,PSJD算法達到收斂所需的迭代次數比采用固定步長的算法減少了42%左右。

盲信號分離;聯合對角化;目標矩陣;自適應學習率

盲信號分離(Blind Source Eeparation,BSS)由于其數學模型具有一般性,可適用于大多數觀測數據,同時不需要訓練序列或過多的先驗信息,僅利用觀測信號就可以有效恢復源信號,因此在電子偵察、無線通信、語音信號處理、圖像處理及生物醫學等領域具有廣闊的應用前景[1]。基于聯合對角化的BSS算法以其分離精度高、計算復雜度低而受到廣泛關注。根據表征聯合對角化近似程度的代價函數的不同,現有的聯合對角化算法主要分為兩大類:①利用目標矩陣非對角部分的Frobenius范數作為代價函數[2-5],最小化此代價函數直接得到分離矩陣的估計;②利用最小二乘代價函數[6-8]得到混迭矩陣的估計。這兩類代價函數均為待估計的矩陣的四次函數,計算復雜度高。相對于基于Frobenius范數代價函數的算法,基于最小二乘代價函數的算法不僅需要估計混迭矩陣,還需要估計一組對角矩陣,而這些對角矩陣的取值通常是盲信號處理不關心的,從而導致待估計的未知參數數目增加;另一方面,當估計的混迭矩陣的條件數較大時,矩陣求逆運算將會放大其估計誤差,從而影響算法性能。

在現有的基于Frobenius范數的非正交聯合對角化算法中,Ziehe等提出的快速Frobenius對角化(Fast Frobenius DIA Gonalization,FFDIAG)算法[3]采用乘性迭代機制更新分離矩陣,在每次迭代中,利用更新矩陣及更新后的目標矩陣的非對角線元素很小的假設,對代價函數進行合理近似,將其轉化為一個最小二乘問題,同時,利用矩陣的稀疏性直接計算更新矩陣的元素,避免矩陣求逆運算,該算法因其收斂性能好、計算復雜度低而受到廣泛關注,但是其只能應用于實數域,無法直接推廣至復數域。徐先鋒等提出的復值快速Frobenius對角化(Complex-Valued Fast Frobenius DIA Gonalization,CVFFDIAG)算法[4]利用對未知參數的特殊表述,分開求解復未知參數的實部和虛部,將文獻[3]算法推廣至復數域,并利用Hessian矩陣的塊對角結構,降低算法的計算復雜度。但是,該算法同FFDIAG一樣,需要人為地選擇一個步長因子θ(0<θ<1),使分離矩陣滿足嚴格對角占優條件,保證分離矩陣可逆性。這一學習規則主要存在如下缺點:θ過小,算法收斂速度會降低;θ過大,則可能無法保證嚴格對角占優條件。

本文針對復數域聯合對角化問題,提出一種利用參數結構的快速非醞酉聯合對角化(PSJD)算法。通過將復矩陣轉化為實對稱矩陣,該算法將FFDIAG推廣至復數領域,利用矩陣的特殊結構,提高算法性能、降低算法的計算復雜度,實現復目標矩陣組的聯合對角化,同時該算法采用自適應學習率,避免固定的步長因子存在的問題。

1 矩陣結構信息

簡要介紹復矩陣轉化為實對稱矩陣的方法[2],并詳細分析轉化后的矩陣的結構,為新算法的提出做準備。

1.1 復矩陣轉化為實矩陣的方法

考慮K個維數為M×M的目標矩陣集合{R1,R2,…,RK},其中第k個目標矩陣Rk滿足如下可聯合對角化結構

(1)

式中:A為可逆的混迭矩陣;Dk為復對角矩陣。對于目標矩陣Rk,首先將其轉化為2K個Hermitian矩陣[2]

(2)

式中:Re(·)和Im(·)分別表示取實部和虛部;i=(-1)1/2。其次,將這2K個維數為M×M的Hermitian矩陣轉化為2M×2M的實矩陣[2]

(3)

1.2 擴展的目標矩陣的結構

從式(2)和式(3)發現,擴展的目標矩陣具有如下結構信息。

(4)

(5)

(6)

(7)

(8)

(9)

(10)

2 算法描述

2.1 PSJD算法

(11)

(12)

(13)

為推導簡便,在不引起歧義的情況下,省略表示迭代次數的上標(t)和(t+1),代價函數可以表示為

(14)

式中:off(·)表示所有非對角線元素的平方和;wm,n和em,n,k分別表示W和Ek的第(m,n)個元素。定義子函數

J(wm,n,wn,m)=

(15)

可以看出,式(15)僅與元素wm,n和wn,m有關,所以,代價函數(14)可以分解為M(2M-1)個相互獨立的子代價函數。由于擴展的目標矩陣組為2K個2M×2M維的矩陣,直接執行FFDIAG算法的運算量較大,下面將充分利用擴展的目標矩陣的結構信息,降低算法的計算復雜度。

由矩陣的結構信息可知,為使擴展的目標矩陣組在迭代過程中保持塊一致結構,分離矩陣必須具有塊一致結構,因此待估計的更新矩陣參數僅為2M(M-1)個。為充分利用上述結構,將更新矩陣分解為4個M×M維的子塊獨立地進行處理,具體步驟如下。

(1)假設1≤m

(16)

(17)

(2)對于坐標為(m+M,n+M)的元素,利用塊一致結構式(8)可將關于該子塊內元素的代價函數表示為

(18)

該函數具有與式(16)相同的形式,該子塊中元素的估計滿足

(19)

(3)對于坐標為(m,n+M)的元素,根據塊一致結構式(8),關于該子塊元素的優化問題式(15)可以寫為

(20)

該子塊中元素的最小二乘估計為

(21)

(4)類似地,對于坐標為(m+M,n)的元素,由塊一致結構式(8)和塊內反對稱結構式(7),該子塊中元素的子代價函數為

(22)

對比式(20)和(22)可知

(23)

(5)對于坐標為(m,m+M)的元素,由塊一致結構式(8)和零對角結構式(10)可得

(24)

2.2 自適應學習率

2.3 算法步驟

利用PSJD算法實現復目標矩陣聯合對角化的步驟總結如下。

輸入 復目標矩陣組{R1,R2,…,RK};

重復如下步驟,直至算法收斂:

Fort=1,2,…

步驟1 根據如下子步驟估計更新矩陣W(t):

Form=1,2,…,M-1;n=m+1,m+2,…,M

(1)分別根據式(17)和(21)計算wm,n和wm,n+M;

(2)分別根據式(19)和(23)計算wm+M,n+M和wn,m+M;

(3)判斷I+f-1(W(t))是否嚴格對角占優,如果不是,則W(t)?F(W(t))W(t);

步驟2 根據式(11)更新聯合對角化矩陣,根據式(12)更新目標矩陣組;

考慮式(17)和(21)有相同的形式w=-B-1e,令B的第(i,j)個元素為Bi,j(i,j=1,2),利用

(25)

可以簡化計算。

3 性能分析

3.1 計算復雜度分析

由前文的分析可知,本文算法每次迭代(執行1次步驟1和2)需進行8M(M-1)K次實數乘除法運算(Number of Multiplications and Divisions,MDN),這里忽略了階數低于O(M3K)和O(M4)的項。CVFFDIAG算法、基于高斯迭代的均勻加權完全對角化(Uniformly Weighted Exhaustive Diagonalization with Gauss Iterations,UWEDGE)算法[10]每次更新需進行8M3K次實數MDN,雙迭代算法(bi-iterative algorithm,BIA)[7]每次迭代需進行12M3K次實數MDN。

3.2 收斂性分析

顯然,代價函數C(V)的下界存在且大于等于零。這表明代價函數至少存在一個全局最小點。眾所周知,非正交聯合對角化為非線性優化問題,因此,嚴格的收斂性分析往往比較困難。通常借助于動力學理論中著名的Lyapunov函數和LaSalle’s不變定理[11-12]來分析算法的收斂性能。

(1)函數g(V(t))連續;

(2)對于離散點t,有g(V(t))≤g(V(t-1));

那么,g(V)稱為Lyapunov函數。

(1)由于代價函數C(V)是可微分的,因此是連續的;

上述3點分析表明,代價函數是Lyapunov函數。根據定理1可知,離散序列V(t)收斂到C(V)的不變集UInvar。

綜上分析,PSJD算法可漸進收斂到全局或至少是局部最小點。

4 仿真實驗

通過與CVFFDIAG算法[4]、BIA算法[7]和UWEDGE算法[10]的比較,詳細評估PSJD算法的性能。為了便于比較,采用盲信號分離算法中常用的性能參數——全局拒絕水平(Gglobal Rejection Level,GRL)[2-7,9,12]來衡量算法的有效性

(26)

式中:Gm,n為全局傳輸矩陣G=VA的第(m,n)個元素。全局拒絕水平LGR為一個非負的參數,描述了G與廣義置換矩陣E=DP的接近程度,其中D為非奇異的對角陣(表示尺度不確定性),P為置換矩陣(表示排列不確定性)。LGR越小,表示G越接近于廣義置換矩陣,分離性能越好。為了便于比較,在所有的實驗中,若滿足‖V(t)-V(t-1)‖F<ε則認為算法收斂,停止迭代,這里V(t)表示第t次迭代中分離矩陣的估計值。每個算法的最大迭代(掃描)次數設為500次,收斂門限ε=10-8。算法運行環境:MATLAB R2010a,Pentium(R) Dual-Core E5200 CPU @2.50 GHz,2 GB內存。

下面通過兩組仿真實驗比較各算法的性能。

圖1 參數θ對收斂所需迭代次數的影響

圖2 步長因子不同時2種算法的全局拒絕水平隨迭代次數變化的曲線

為了評估參數選擇對算法性能的影響,在RNE=0 dB的條件下進行了100次獨立實驗,得到PSJD算法和CVFFDIAG算法收斂所需的平均迭代次數隨參數θ的變化曲線,如圖1所示。可以看出,當θ為0.1、矩陣維數M分別為6、10、12、14時,PSJD算法所需迭代次數比CVFFDIAG算法分別減少約27%、42%、41%和39%,且參數θ越接近于1,算法的性能越穩健。圖2表示在RNE=0 dB時PSJD算法(θ=0.1)以及CVFFDIAG算法取不同θ時的GRL隨迭代次數變化的曲線。可以看出,θ的取值較大時,雖然收斂速度相對較快,但收斂狀態不穩定,其原因主要是在迭代的初始階段,更新矩陣及目標矩陣的非對角元素不滿足范數很小的假設,較大的θ不能保證更新矩陣滿足嚴格對角占優條件;而自適應學習規則分開考慮分離矩陣的每一行,僅對不滿足條件的行賦予較小的步長,在確保更新矩陣滿足嚴格對角占優條件的同時,保持較快的收斂速度,因而在收斂速度與收斂狀態之間取得了一個很好的平衡。

(a)收斂LGR隨RNE變化的曲線

(b)收斂所需時間隨RNE變化的曲線圖3 RNE對4種算法性能的影響

圖3表示經過100次獨立實驗PSJD算法(θ=0.17)、CVFFDIAG算法(θ=0.9)、UWEDGE算法和BIA算法的收斂LGR和收斂時間隨RNE變化的曲線。相應地,圖4給出RNE=0 dB時,LGR隨迭代次數變化的曲線。可以看出,PSJD算法具有與CVFFDIAG算法相似的收斂性能,且優于其他2個算法,PSJD算法的收斂所需的平均時間低于CVFFDIAG算法和BIA算法,高于UWEDGE算法,但平均LGR較UWEDGE算法降低了5 dB左右,與CVFFDIAG算法相比,得到相同的LGR所需時間更短。由4.1節可知,CVFFIDAG算法與PSJD算法每次迭代所需的MDN相同,圖3b可間接說明PSJD算法比CVFFDIAG算法的平均收斂速度更快。UWEDGE算法的參數更新是以向量或矩陣的形式進行的,避免了大量的循環迭代,因此在MATLAB環境下效率更高,而BIA算法在兩組參數間交替迭代,計算復雜度最高,收斂速度最慢。

圖4 4種算法的全局拒絕水平隨迭代次數變化的曲線

實驗2 采用一組復信號測試所提算法應用于盲信號分離的性能。源信號為4個0均值的相互獨立的復信號

(27)

采樣點數為1 000,接收陣列為7個陣元構成的均勻線陣,陣元間距半波長,即混迭矩陣A=[a(φ1),a(φ2),…,a(φ4)],a(φ)=[1,e-iπcosφ,…,e-i6πcosφ]T,各信號的入射角度分別為φ1=20+10γ,φ2=50+15γ,φ3=75+10γ,φ4=115+15γ,其中,γ∈[0,1]隨機產生。取時延為3k(k=1,2,…,15)構造目標矩陣組,由于混迭矩陣為高矩陣,因此需要一個白化降維預操作。為衡量算法的分離性能,采用估計信號的信干噪比來表征分離信號的獨立性,信干噪比為

(28)

(a)收斂LGR隨RSN變化的曲線

(b)收斂信干噪比隨RSN變化的曲線

(c)收斂時間隨RSN變化的曲線

(d)迭代次數隨RSN變化的曲線圖5 信噪比對4種算法性能參數的影響

圖5為經過100次獨立實驗,4種算法的平均性能參數隨信噪比RSN變化的曲線。可以看出,由于預白化的影響,4種算法的分離性能相近,但PSJD算法(θ=0.1)與CVFFDIAG算法(θ=0.9)、BIA算法相比,得到相近的LGR所需的迭代次數和時間較少。這是因為即使W(t)的某些行不滿足嚴格對角占優條件,CVFFDIAG算法所用的固定步長都對W(t)所有行進行調節,這將使W(t)相對于其最優值產生較大的偏離,從而影響收斂速度;而PSJD算法采用的自適應學習率對W(t)的每行分開考慮,某行的1-范數越小則說明經過t-1次迭代,該行對應的分離信號與源信號越接近,因此無需對該行進行處理,從而提高了算法的收斂速度。同時,這也是‖W(t)‖F<ε可以作為此算法收斂條件的原因。圖6表示RSN=25 dB時,源信號和對應的分離信號的星座圖,可見所提算法能夠有效地恢復源信號。

(a)s1(t)(b)s2(t)(c)s3(t) (d)s4(t)

圖6 源信號、分離信號的星座圖

5 結 論

本文通過將復矩陣轉化為實對稱矩陣,將FFDIAG算法推廣至復數域,利用轉化后的目標矩陣的結構信息,降低算法的計算復雜度。同時,采用自適應學習規則,改善了在初始迭代狀態中,更新矩陣和目標矩陣的非對角部分不滿足假設條件時,采用固定步長因子無法確保嚴格對角占優性而導致收斂狀態不穩定的情況,確保了分離矩陣的可逆性,且避免了收斂速度對參數選擇的依賴,提高了算法的收斂性能。仿真實驗表明,同CVFFDIAG算法相比,本文所提PSJD算法達到相同的全局拒絕水平所需的運算時間更短。

[1] CHABRIEL G, KLEINSTEUBER M, MOREAU E, et al. Joint matrices decompositions and blind source separation: a survey of methods, identification, and applications [J]. IEEE Signal Processing Magazine, 2014, 3(31): 34-43.

[2] MESLOUB A, ABED-MERAIM K, BELOUCHRANI A. A new algorithm for complex non orthogonal joint diagonalization based on Shear and Givens rotations [J]. IEEE Transactions on Signal Processing, 2014, 62(8): 1913-1925.

[3] ZIEHE A, LASKOV P, NOLTE G, et al. A fast algorithm for joint diagonalization with non-orthogonal transformations and its application to blind source separation [J]. Journal of Machine Learning Research, 2004, 5(3): 777-800.

[4] XU Xianfeng, FENG Dazheng, ZHENG Weixing. A fast algorithm for nonunitary joint diagonalization and its application to blind source separation [J]. IEEE Transactions on Signal Processing, 2011, 59(7): 3457-3463.

[5] 叢豐裕, 雷菊陽, 許海翔, 等. 在線增強型復值混合信號盲分離算法研究 [J]. 西安交通大學學報, 2006, 40(9): 1070-1073. CONG Fengyu, LEI Juyang, XU Haixiang, et al. Online blind separation of enforced mixed complex-value signal sources [J]. Journal of Xi’an Jiaotong University, 2006, 40(9): 1070-1073.

[6] 聶衛科, 馮大政, 劉建強. 二維波達方向估計的非酉聯合對角化方法 [J]. 西安交通大學學報, 2008, 42(6): 747-750. NIE Weike, FENG Dazheng, LIU Jiangiang. Non-unitary joint diagonalization method for estimating two-dimension direction of arrival [J]. Journal of Xi’an Jiaotong University, 2008, 42(6): 747-750.

[7] FENG Dazheng, ZHANG Hua, ZHENG Weixing. Bi-iterative algorithm for extracting independent components from array signals [J]. IEEE Transactions on Signal Processing, 2011, 59(8): 3636-3646.

[8] ZENG Tiaojun, FENG Quanyuan. Non-orthogonal joint diagonalization algorithm based on hybrid trust region method and its application to blind source separation [J]. Neurocomputing, 2014, 133(8): 280-294.

[9] 陸建濤, 成瑋, 訾艷陽, 等. 變步長等變自適應盲源分離算法 [J]. 西安交通大學學報, 2015, 49(12): 83-89. LU Jiantao, CHENG Wei, ZI Yanyang, et al. Variable step-size algorithm for equivariant adaptive separation via independent [J]. Journal of Xi’an Jiaotong University, 2015, 49(12): 83-89.

[10]TICHAVSKY P, YEREDOR A. Fast approximate joint diagonalization incorporating weight matrices [J]. IEEE Transactions on Signal Processing, 2009, 57(3): 878-891.

[11]LASALLE J P. The stability of dynamical system [M]. Philadelphia, PA, USA: SIAM Press, 1976: 49-50.

[12]張偉濤, 樓順天, 張延良. 非對稱非正交快速聯合對角化算法 [J]. 自動化學報, 2010, 36(6): 829-836. ZHANG Weitao, LOU Shuntian, ZHANG Yanliang. Non-symmetrical non-orthogonal fast joint diagonalization algorithm [J]. Acta Automatica Sinica, 2010, 36(6): 829-836.

[本刊相關文獻鏈接]

王玉璽,黃國策,李偉,等.非均勻廣義對角加載穩健波束形成算法.2016,50(8):64-69.[doi:10.7652/xjtuxb201608011]

劉健伶,陳志剛,王磊.一種自適應廣義空間調制及其低復雜度算法.2016,50(4):48-53.[doi:10.7652/xjtuxb201604008]

王富平,水鵬朗.采用多尺度方向微分比率的角點檢測算法.2016,50(4):68-75.[doi:10.7652/xjtuxb201604011]

趙凱,王闖,李尊朝,等.結合平衡和濾波技術抑制GaN電源轉換器的電磁干擾.2016,50(02):38-42.[doi:10.7652/xjtuxb201602007]

孫黎,徐洪斌.協作式終端直通系統中星座旋轉輔助的干擾避免策略.2015,49(12):6-11.[doi:10.7652/xjtuxb201512 002]

張東偉,郭英,齊子森,等.采用空間極化時頻分布的跳頻信號多參數聯合估計算法.2015,49(8):17-23.[doi:10.7652/xjtuxb201508004]

巴斌,鄭娜娥,朱世磊,等.利用蒙特卡羅的最大似然時延估計算法.2015,49(8):24-30.[doi:10.7652/xjtuxb201508005]

吳一全,孟天亮,吳詩婳.人工蜂群優化的非下采樣Shearlet域引導濾波圖像增強.2015,49(6):39-45.[doi:10.7652/xjtuxb201506007]

熊濤,江樺,崔鵬輝,等.應用基擴展模型的混合信號單通道盲分離算法.2015,49(6):60-66.[doi:10.7652/xjtuxb201506 010]

郝雯潔,齊春.一種魯棒的稀疏信號重構算法.2015,49(4):98-103.[doi:10.7652/xjtuxb201504016]

王云龍,吳瑛.聯合時延與多普勒頻率的直接定位改進算法.2015,49(4):123-129.[doi:10.7652/xjtuxb201504020]

尚佳棟,王祖林,周麗娜,等.采用隨機共振增強的混合擴頻信號跳頻參數估計.2014,48(10):42-48.[doi:10.7652/xjtuxb201410007]

儲穎,牟軒沁,洪偉.采用形狀一致性特征的盲圖像質量評價方法.2014,48(8):12-17.[doi:10.7652/xjtuxb201408003]

吳仁斌,姚敏立,賈維敏,等.采用幅度響應約束的魯棒自適應波束形成算法.2014,48(4):109-114.[doi:10.7652/xjtuxb201404019]

郝紅俠,劉芳,焦李成,等.采用結構自適應窗的非局部均值圖像去噪算法.2013,47(12):71-76.[doi:10.7652/xjtuxb 201312013]

穆為磊,高建民,王昭,等.考慮人眼視覺特性的射線檢測數字圖像質量評價方法.2013,47(7):91-95.[doi:10.7652/xjtuxb201307017]

(編輯 劉楊)

A Fast Non-Unitary Joint Diagonalization Algorithm Based on Utilizations of Parametric Structures

LIU Wenjuan,FENG Dazheng,YUAN Mingdong

(National Laboratory of Radar Signal Processing, Xidian University, Xi’an 710071, China)

A parametric structures based fast joint diagonalization (PSJD) algorithm for non-unitary diagonalization of a set of complex target matrices is presented to cope with the problem that the blind source separation by fast Frobenius diagonalization (FFDIAG) algorithm is not applicable in the complex-valued space and its separation performance is lower. The algorithm firstly transforms the complex target matrices into real-symmetric ones. Secondly, the problem of simultaneous diagonalization of matrices is transformed into a series of linear least-squares problems through second-order approximation to contract functions, and the elements of the updating matrix are directly estimated. The computational complexity for estimating the diagonalizer and for updating the target matrices is significantly reduced by making full use of the structure information of the transformed target matrices. In order to overcome the drawback of fixed step size adopted in the FFDIAG that may not strike a balance between the convergence rate and strictly diagonally dominant property of the update matrix, the proposed algorithm uses the adaptive learning rate determined from the estimation of the update matrix in each iteration to improve the convergence property. Results of numerical simulations show that the convergence rate of PSJD algorithm is not very sensitive in a wide range of step-size values. When the step size is 0.1, the number of iterations required to reach convergence is 42% less than that of the fixed step-size method.

blind source separation; joint diagonalization; target matrix; adaptive learning rate

2016-03-08。 作者簡介:劉文娟(1986—),女,博士生;馮大政(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61271293,61373177)。

時間:2016-10-10

10.7652/xjtuxb201612017

TN911.7

A

0253-987X(2016)12-0106-08

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20161010.1743.002.html