潘子宇,酆廣增,孔媛媛(.南京工程學(xué)院通信工程學(xué)院,南京67;.南京郵電大學(xué)通信與信息工程學(xué)院,南京0003)
一種改進(jìn)的批處理常模算法?
潘子宇1,酆廣增2,孔媛媛2
(1.南京工程學(xué)院通信工程學(xué)院,南京211167;2.南京郵電大學(xué)通信與信息工程學(xué)院,南京210003)
分析了傳統(tǒng)批處理常模算法的缺點(diǎn),提出了一種新的批處理常模算法——基于共軛梯度方向的批處理常模算法(CG-BPCMA)。新算法采用共軛梯度方向作為下降方向,推導(dǎo)出共軛梯度方向的解析形式。在平坦瑞利衰落信道環(huán)境下的MIMO盲均衡系統(tǒng)中的仿真結(jié)果表明,新算法有效地克服了SD-BPCMA和NT-BPCMA的缺點(diǎn),不僅獲得了較低的算法復(fù)雜度,而且能快速收斂到常模代價(jià)函數(shù)的最小值點(diǎn)。
MIMO;盲均衡系統(tǒng);批處理算法;常模算法;共軛梯度
常模(CM)算法在盲信道估計(jì)、盲多用戶檢測、盲信源分離等領(lǐng)域有廣泛的應(yīng)用[1]。一般而言,常模算法基于最陡下降算法,算法簡單且具有全局收斂性,但收斂速度很慢,從而限制了其在信號(hào)處理中的應(yīng)用。
文獻(xiàn)[2]提出了一種最優(yōu)化方法——批處理常模算法(BPCMA)。作為一種線性搜索迭代算法,BPCMA包含三方面因素,即搜索方向、步長和初始值。基于牛頓方向的BPCMA(NT-BPCMA)有效克服了傳統(tǒng)最陡下降算法(SD-BPCMA)收斂慢的缺點(diǎn),實(shí)現(xiàn)了算法的快速收斂,經(jīng)幾步迭代即可收斂到極小值點(diǎn)。然而,牛頓法具有以下幾點(diǎn)缺陷[3]:第一,牛頓法并不是全局收斂的;第二,由于信號(hào)和信道的隨機(jī)性,代價(jià)函數(shù)J(g)的Hessian矩陣▽2J(g)有時(shí)候是奇異或病態(tài)的。在這種情況下,下降方向?qū)o法確定;第三,牛頓法收斂于鞍點(diǎn)或極大值點(diǎn)的可能性并不小于最小值點(diǎn);第四,牛頓法需要進(jìn)行矩陣求逆運(yùn)算,而這是最優(yōu)化方法力求避免的問題。
綜合考慮到最陡下降法和牛頓法的各種利弊,本文提出了基于共軛梯度法的批處理常模算法,稱之為CG-BPCMA。本文研究了新算法的收斂性和復(fù)雜度,與SD-BPCMA和NT-BPCMA作了仿真比較。結(jié)果表明,本文提出的算法有效地兼顧了算法復(fù)雜度、收斂性兩方面的矛盾,取得了較好的均衡效果。
考慮如下的信號(hào)模型,其接收信號(hào)為
其中,s(n)=[s1(n),…,sK(n)]T是K維的發(fā)送信號(hào),每根發(fā)送天線發(fā)送相同的信號(hào);y(n)是P維的經(jīng)過信道后的接收天線的接收信號(hào);hk是長度為P的信道矢量;H=[h1,…,hK]則是P×K信道矩陣;w(n)是加性噪聲分量。系統(tǒng)模型如圖1所示。
為了討論問題方便起見,我們對信道模型做如下假設(shè)。
(1)sk(n)是零均值非高斯的信號(hào),
若sk(n)為復(fù)變量,則E{sk(n=0,說明發(fā)送信號(hào)為均勻?qū)ΨQ。
(3)信道轉(zhuǎn)移矩陣H是滿秩矩陣。
其中,J(g)=E{(|z(n)|2-γ)2}為常模代價(jià)函數(shù),γ為輸出信號(hào)的期望模值。
本節(jié)將給出我們提出的線性搜索批處理常模算法的算法原理。我們知道,線性搜索算法首先確定一個(gè)搜索方向,繼而以降低代價(jià)函數(shù)值為目標(biāo)由本次迭代走向下一步迭代[4]。迭代過程的數(shù)學(xué)表達(dá)式如下:
式中,正參數(shù)μ為迭代步長。為了討論問題簡便,本文采用定步長的方法。因此,我們僅需要討論其余兩點(diǎn)因素——搜索方向和初始權(quán)值。
3.1 搜索方向
本文中我們將采用共軛梯度方向代替牛頓方向進(jìn)行迭代。共軛梯度法是共軛方向法的一種,共軛方向法可表示如下[5]:
其中,▽iJ為常模代價(jià)函數(shù)的梯度,βi-1為修正系數(shù)且由下式確定:
在式(5)中,G是代價(jià)函數(shù)J的Hessian矩陣。在每一步迭代時(shí)計(jì)算G是比較麻煩的,因此我們必須尋求βi-1不顯含G的表達(dá)形式。
注意到
由于式(6)中βi-1完全由代價(jià)函數(shù)的梯度▽J確定,我們稱之為共軛梯度法。若βi-1=0,共軛梯度法便退化為最陡下降法(SD-BPCMA),牛頓法(NTBPCMA)的下降方向?yàn)閜i=-G-1i▽J(gi)。
3.2 初始權(quán)值
文獻(xiàn)[6]指出,常模估計(jì)器的權(quán)值在由信道轉(zhuǎn)移矩陣H的列向量張成的信號(hào)子空間中。因此,我們可以從信號(hào)子空間中提取初始權(quán)值g1。信號(hào)子空間可以由接收信號(hào)的自相關(guān)矩陣做特征值分解(ED)得到[7]:
假設(shè)ps為一P×K矩陣,其列向量張成信號(hào)子空間,初始權(quán)值可以簡單取為其中的任意一列g(shù)1= ps,k,k=1,…,K。文獻(xiàn)[2]將矩陣ps的列向量做一線性組合,從而作為初始權(quán)值,即?gk=x1ps,1+x2ps,2+…+xkps,k,其中組合系數(shù)xk由下式確定:
求解式(7)中xk的常規(guī)方法是做線性搜索。然而,我們注意到代價(jià)函數(shù)φ(x)=J(?gk-1+x ps,k)是一個(gè)四次多項(xiàng)式:
由于期望運(yùn)算和求導(dǎo)運(yùn)算可以交換次序,其一階導(dǎo)函數(shù)為
令φ′(x)=0,我們得到一個(gè)三次方程。一般而言,求解三次方程需要用數(shù)值分析的方法求解。本文中,我們采用一個(gè)比較簡單的方法求解x。上述三次方程可轉(zhuǎn)化為如下形式:
[(g+x p)Ty]3·(pTy)=[(g+x p)Ty]·(pTy)(10)注意,方程(10)是方程φ′(x)=0的充分條件而非充分必要條件。注意到(g+x p)Ty和pTy均為非零值,則方程的解為
最終的組合系數(shù)x由下式確定:
迭代到第K步時(shí)得到?gK=x1ps,1+x2ps,2+…+xKps,K,這就是我們要確定的初始權(quán)值g1。
因此,CG-BPCMA的算法步驟如下:
Step 1:初始化g1、μ,令i=1;
Step 2:計(jì)算▽iJ=▽J(gi);
由于本文算法選取初始權(quán)值的方法和文獻(xiàn)[2]相似,復(fù)雜度相當(dāng),我們只需比較選取搜索方向部分的算法復(fù)雜度。在共軛梯度算法中,乘法運(yùn)算的計(jì)算量為K2(K為權(quán)向量g的維數(shù)),其余計(jì)算量(如加法運(yùn)算)均為K的線性函數(shù),因此整個(gè)算法的時(shí)間復(fù)雜度為O(K2)。在牛頓法中,乘法運(yùn)算的計(jì)算量為1/6K3+O(K2),其余運(yùn)算量同樣為K的線性函數(shù),因此整個(gè)算法的時(shí)間復(fù)雜度為O(K3)。相比之下,本文算法使得算法的時(shí)間復(fù)雜度降低了一個(gè)數(shù)量級(jí)。
本節(jié)中,我們用數(shù)值仿真的手段對新算法的收斂性能做進(jìn)一步分析??紤]圖1所示的系統(tǒng)模型,信源個(gè)數(shù)K=8,接收天線數(shù)P=10,信道采用平坦瑞利衰落信道,且在一幀數(shù)據(jù)內(nèi)不變化,發(fā)送信號(hào)為QPSK信號(hào),一幀數(shù)據(jù)長N=500,發(fā)送信噪比為SNR=20 dB,步長μ=10-8。采用均方誤差(MSE)作為衡量算法收斂性能的指標(biāo),仿真結(jié)果如圖2~3所示??紤]信號(hào)和信道的隨機(jī)性,本文采用50次獨(dú)立運(yùn)行的平均。
圖2 是CG-BPCMA和SD-BPCMA、NT-BPCMA的MSE性能比較圖。從圖中可以看出NT-BPCMA出現(xiàn)了發(fā)散現(xiàn)象,不能收斂到極小值點(diǎn),這是由于信道的隨機(jī)選取導(dǎo)致了G-1可能無法計(jì)算。若G-1能夠計(jì)算,算法向收斂方向迭代;反之,算法將走向發(fā)散(在這50次獨(dú)立運(yùn)行的過程中,NT-BPCMA算法出現(xiàn)了43次發(fā)散,僅有7次是收斂的),這是圖2中牛頓法曲線怪異的根本原因。但是,我們提出的CG-BPCMA則很好地避免了這一問題。從圖2中還可以看出,CG-BPCMA的收斂速度明顯高于SD-BPCMA。此外,在仿真過程中,我們還發(fā)現(xiàn),一旦步長因子μ≥10-6,算法將走向發(fā)散。
圖3是CG-BPCMA的MSE性能圖,兩條曲線分別對應(yīng)初始權(quán)值隨機(jī)選取和由子空間分解法得出。從圖中可以明顯看出,和隨機(jī)選取初始權(quán)值的方法相比,利用子空間分解計(jì)算初始權(quán)值的方法使得算法收斂速度和穩(wěn)態(tài)性能大大提高。
本文分析了傳統(tǒng)批處理常模算法的優(yōu)缺點(diǎn),針對最陡下降法收斂慢以及牛頓法不能準(zhǔn)確收斂的問題,提出了一種基于共軛梯度法的新的批處理常模算法(CG-BPCMA),并將其和傳統(tǒng)批處理常模算法做了仿真比較。結(jié)果表明,本文提出的新算法不僅能克服傳統(tǒng)算法的缺點(diǎn),且復(fù)雜度低,收斂速度較快。因此,CG-BPCMA有效地兼顧了收斂速度和復(fù)雜度之間的矛盾。此外,利用子空間分解計(jì)算初始權(quán)值的方法能夠大大提高算法的收斂速度,使得算法收斂“贏在起點(diǎn)上”,但子空間分解也需要消耗相當(dāng)一部分計(jì)算資源,從算法整體收斂所需的CPU絕對時(shí)間上看,該方法不比隨機(jī)選取初始值節(jié)省時(shí)間。如何進(jìn)一步降低子空間分解的算法復(fù)雜度、實(shí)現(xiàn)快速分解將是本批處理常模算法進(jìn)一步研究的方向之一。
[1]Abrar S,Nandi A K.An Adaptive ConstantModulus Blind E-qualization AlgorithMand Its Stochastic Stability Analysis[J]. IEEE Signal Processing Letters,2010,17(1):55-58.
[2]Xu Changjiang,Li Jian.A Batch processing ConstantModulus Algorithm[J].IEEE Communications Letters,2004,8(9):582-584.
[3]Argyros IK.Newton Method on Lie Groups[J].Journal of Applied Mathematics and Computing,2009,31(1-2):217-228.
[4]Wang Jian,WuWei,Zurada JM.Deterministic Convergence of Conjugate Gradient Method for Feedforward Neural Networks[J].Neurocomputing,2011,74(14):2368-2376.
[5]Dietl G,Botsch M,Dietrich F A,et al.Robust and reducedrankmatrixWiener filter based on the conjugate gradient algorithm[C]//Proceedings of 2005 IEEE 6th Workshop on Signal Processing Advances in Wireless Communications.NeWYork:IEEE,2005:555-559.
[6]代松銀,袁嗣杰,董書攀.基于子空間分解的信道階數(shù)估計(jì)算法[J].電子學(xué)報(bào),2010,38(6):1245-1248. DAISong-yin,YUAN Si-jie,DONG Shu-pan.Effective Channel Order Estimation Based on Subspace Decomposition[J].Acta Electronic Sinica,2010,38(6):1245-1248.(in Chinese)
[7]Dong Enqing,Zhu Caihua,Evans L.Blind Multiuser Detector Based on Reduced Rank Subspace and Least Square Constant Modulus Algorithm[C]//Proceedings of the 8th International Conference on Signal Processing.Beijing:IEEE,2006:1-7.
PAN Zi-yu was born in Jiangyan,Jiangsu Province,in 1984. He received the M.S.degree froMNanjing University of Posts and Telecommunications in 2008.He is noWa lecturer.His research concernsmobile communications and communication signal processing,information processing technology.
Email:panziyu@sohu.com,panziyu@njit.edu.cn
酆廣增(1943—),男,江蘇無錫人,教授、博士生導(dǎo)師,主要研究方向?yàn)閿?shù)字移動(dòng)通信與通信信號(hào)處理;
FENG Guang-zeng was born in Wuxi,Jiangsu Province,in 1943.He is noWa professor and also the Ph.D.supervisor.His research concerns digital mobile communications and communication signal processing.
Email:gzfeng@njupt.edu.cn
孔媛媛(1982—),女,山東煙臺(tái)人,講師,主要研究方向?yàn)橐苿?dòng)通信與通信信號(hào)處理。
KONG Yuan-yuan was born in Yantai,Shandong Province,in 1982.She is noWa lecturer.Her research concerns digitalmobile communications and communication signal processing.
Email:yyk@njupt.edu.cn
A Modified Batch Processing Constant Modulus Algorithm
PAN Zi-yu1,F(xiàn)ENGGuang-zeng2,KONG Yuan-yuan2
(1.Communication Engineering Institute,Nanjing Institute of Technology,Nanjing 211167,China;2.Communication and Information Engineering Institute,Nanjing University of Posts&Telecommunications,Nanjing 210003,China)
By analysing the shortages of traditional batch processing algorithm,a neWbatch processing constant modulus algorithMderived by conjugate gradientdirection tominimizing the constantmodulus criterion(CG-BPCMA)is presented.The neWalgorithMuses conjugate gradient direction to choose the search direction and the analytical forMof conjugate gradient direction is deduced.Simulation results shoWthat in flat Rayleigh fading synchronous channelenvironmentblind equalization system,the neWalgorithMovercomes the shortcomings of SDBPCMA and NT-BPCMA effectively,not only has lower complexity,but also can converge to theminima of the constantmodulus criterion quickly.
MIMO;blind equalization system;batch processing algorithm;constantmodulus;conjugate gradient
Youth Fund of Nanjing Institute of Technology(QKJB2010009)
TN911
A
10.3969/j.issn.1001-893x.2012.11.013
潘子宇(1984—),男,江蘇姜堰人,2008年于南京郵電大學(xué)獲工學(xué)碩士學(xué)位,現(xiàn)為講師,主要研究方向?yàn)橐苿?dòng)通信與通信信號(hào)處理、信息處理技術(shù)等;
1001-893X(2012)11-1774-04
2012-03-27;
2012-05-23
南京工程學(xué)院青年基金項(xiàng)目(QKJB2010009)