基于信賴域的EM算法進行多徑時延估計

摘 要： EM算法進行多徑時延估計時，能將多維問題轉化為一維問題，計算簡單，但是當數據缺失比較多，信噪比低，接收信號比較弱時收斂速度會很慢，有時甚至無法收斂。而信賴域法具有可靠性，有效性和很強的全局收斂性。因此，提出一種將信賴域法和EM算法相結合的思想，即提高了收斂特性，又降低了計算的復雜度。并通過仿真實驗分析，結果表明該方法能有效解決收斂速度慢，及無法收斂的問題。

關鍵詞： 最大估計算法； 信賴域； 多徑信號； 參數估計

中圖分類號： TN955?34 文獻標識碼： A 文章編號： 1004?373X（2013）08?0027?04

多徑傳播會造成電磁波等無線傳輸信號經過不同的時延到達接收端，通過對這些不同的時延進行估計，可以有效了解通信信道的質量，以及判斷輻射源所在位置，目前被廣泛應用于通信系統、雷達系統、地質勘探以及生物醫學等領域。對于時延參數的估計，常采用極大似然估計（Maximum Likelihood Estimation）法，一般通過對一組觀察隨機變量的聯合概率密度函數進行參數最大化得到的[1]。鑒于多信號多參數估計問題所需多維優化的復雜性，在多徑時延估計問題中直接使用極大似然方法會涉及復雜的多維優化運算[2]。1988年為了減小運算復雜度和降低優化維數，Feder等人提出了基于最大似然準則的EM算法，利用迭代的一維優化取代上述多維優化問題，實現了基于最大似然準則的多徑時延估計方法[3]。然而該方法當不可觀測變量的信息量比較大時，收斂速度較緩慢，且當接收信號比較微弱，信噪比較低時，收斂速度更加緩慢甚至有時無法實現收斂。信賴域法是求解最優化問題的另一類有效方法，該方法的基本思想是通過求解一系列二次函數在信賴域中的極小值點逼近最優化問題的解。該方法具有穩定的數值性能，而且迭代次數少，具有可靠性，有效性和很強的全局收斂性。然而該方法也有其缺點，當信賴域子問題的Hessian矩陣不正定時，在數值計算上存在一定困難，其次每次迭代都需要求解信賴域子問題，計算量太大。而EM算法的特點就是降維處理，將多維優化問題轉換為一維問題，因此將這兩種方法結合即提高了多徑時延在弱信號和低信噪比情況下的估計性能，又降低了計算量。并且通過實驗仿真也驗證了該方法在信噪比比較低的情況，在接收信號比較微弱的情況下可以有效提高EM算法的收斂性能。

1 信號模型

假設多徑傳播環境下的接收信號是多條經過一定延時后的直達波信號線性疊加后的信號，則接收信號的離散時間信號模型可以表示為：

[y（n）=i=1Dαis（n-τi）+w（n），n=1，2，…，N] （1）

式中：[D]為接收信號中多徑信號的個數；[N]為連續觀測的樣本數；[w（n）]為接收信號噪聲；[αi]為第[i]路多徑信號分量相對于源信號的幅度衰減系數；[τi]為第[i]路多徑信號相對于直達波的時延差值。

2 利用EM算法對多徑時延進行估計

Feder 和Weinsten于1988年提出利用EM算法對疊加信號進行時延估計，具體方法如圖1所示。

圖1中，[y（n）]是觀測到的信號，其是不完全信號，如式（1）所示。通過[y（n）]確定一組完全數據[x（n）]，可以表示為：

[x（n）=α1s（n-τ1）+w1（n）α2s（n-τ2）+w2（n） ?αis（n-τi）+wi（n）] （2）

式中[α，τ]即為帶估計的參數。并在時域將完全數據進行分解，成為[i]路多徑信號，然后每一路分別進行最大似然估計[3]。有：

[U（θ，θ′）=e-12i=1Dn=1Nxi（n）-αis（n-τi）2（σ2βi）-1] （3）

從式（3）中可以看到，[U（θ，θ′）]要取得最大值，實際上就應該滿足：

[minτ1，τ2，???，τi；α1，α2，???，αin=1Nxi（n）-αis（n-τi）2] （4）

因此，每條支路分別進行E步和M步為：

E步：利用前面迭代的結果[α（m）i，τ（m）i]代替[θ′]，從而構造各個支路的[x（m）i（n）]：

[x（m）i（n）=α（m）is（n-τ（m）i）+βiy（n）-i=1D（α（m）is（n-τ（m）i））] （5）

M步：根據上一步得到的[x（m）i（n）]，通過：

[α（m+1）i=n=1Nx（m）i（n）s?（n-τ）n=1Ns（n-τ）2] （6）

[τ（m+1）i=argmaxxin=1Nx（m）i（n）s?（n-τ）] （7）

通過式（6）和式（7）得到第（m+1）次迭代的參數估計值[θ（m+1）i]。

開始迭代時，每次迭代都會增大每條支路的最大似然函數值，當收斂于似然函數的某一個穩定點時，如果繼續迭代，參數的估計值都不再發生變化，似然函數也不再變化，即可以判斷迭代終止。

3 基于信賴域的EM算法進行多徑時延估計

3.1 信賴域思想

考慮無約束優化問題：

[minf（x）x∈Rn] （8）

式中[f：Rn→R]是連續可微的。在迭代點[xk]，信賴域法利用二次逼近構造信賴域子問題：

[mindk∈Rnqk（d）=?fT（xk）d+12dT?2fxkds.t.dΔk] （9）

式中：[?]表示[Rn]上的歐幾里德范數；[d]為試探步長，是目標函數在可行點的搜索方向，也是求解子問題的主要目的。[Δk]是信賴域半徑，總可以找到一個[d]滿足于信賴域約束條件，使得[qk（d）]達到最小。通過比較代價函數的實際減小值和二次型模型的預測減少值之間的比率[ρk]來更新[xk]和[Δk]，見文獻[4]。

[ρk=fxk-fxk+dkqk0-qkdk] （10）

如果[ρk]足夠大，說明計算出的[dk]是代價函數值較快下降的方向，因此[dk]被接受，有：

[xk+1=xk+dk， ρk>η0xk， ρk≤η0] （11）

式中[η0]是一個給定的值，一般選取0.000 1。

根據信號模型考慮時延估計的代價函數式（4）可以改寫為：

[f（α）=n=1N（x（n）-αs（n-τ））（x（n）-αs（n-τ））?] （12）

其梯度為：

[?f（α）=2n=1N-x?（n）s（n-τ）-αs（n-τ）2] （13）

其Hessian陣為：

[?2f（α）=2n=1Ns（n-τ）2] （14）

從上式可以看到其Hessian矩陣一定為正定的。

求解的具體步驟如下：

Step1：初始化[k=0]，任意給定[α0=0]。

Step2：判斷[?f（αk）=0]是否滿足，若滿足，則求得輸出時延最終解[α=αk]，算法結束；否則[k=k+1]，轉step3；

Step3：求得信賴域子問題的近似解[dk]，即：

[mindk∈Rnqk（d）=?fT（αk）d+12dT?2fαkds.t.d≤Δk]

Step4：根據式（10）計算[ρk]；

Step5：根據式（11）更新[αk]到[αk+1]；

Step6：更新信賴域半徑，并轉Step2；

信賴域約束[Δk]可以按如下規則更新：

[Δk+1∈σ1mind，Δk，σ2Δk， ρk≤η1；Δk+1∈σ1Δk，σ2Δk， ρk∈η1，η2；Δk+1∈Δk，σ3Δk， ρk≥η2] （15）

式中[0<η1<η2<1，0<σ1<σ2<1<σ3]均為常數。可以設定[η1=0.25，][η2=0.75，][σ1=0.25，][σ2=0.5，][σ3=5.0]。將式（14）對[αi]展開，則有：

[minτ1，τ2，???，τi；α1，α2，???，αin=1Nxi（n）2+αis（n-τi）2-2αix（n）s（n-τi）] （16）

為使得式（16）最小，需使式中[αix（n）s（n-τi）]部分最大，即：

[τi=maxn=1Nαix（n）s（n-τi）] （17）

從而可以得到第[i]路多徑信號延時估值[τi]。

3.2 基于信賴域的EM算法

EM算法求解多徑時延估計時，當信噪比較高，接收信號幅度與參考信號幅度可以比擬時，收斂性能和速度都比較好；但是當信噪比較低，接收信號幅度遠小于參考信號幅度時，收斂性能就比較差也收斂速度緩慢。因此，考慮低信噪比和低接收信號幅度時E步保持不變，而M步采用基于信賴域方法對每條支路的進行峰值選擇，然后返回值再進行E步計算，不斷迭代直至最后。

具體步驟：在基于信賴域的EM算法中E步仍然采用文獻[3]中與EM相同的計算過程，而M步則需要進行改正，需要通過信賴域法求出每條支路的幅度和時延。首先利用初始[αk]作為初始值，按信賴域步驟進行，當完成Step6后，根據式（17）得到當前[τk+1]。返回期望步更新[xi（n）]，再繼續估計[τk+2，αk+2]。為了能實現整個過程都有很好的收斂速度，而且要穩定的收斂到一個極大值，EM算法不能做到，而信賴域法確有很好全局收斂特性。并且，由于M步最大似然是一維的，信賴域子問題的計算也比較簡單。具體框圖如圖2所示。

3.3 基于信賴域的EM算法收斂性研究

以前Dempster，Laird曾證明多對于任意初始值EM算法都能該收斂到局部極大。如果涉及的問題存在惟一的極大似然解，則EM算法最終迭代給出的結果就是極大似然的估計值。而通過分析可知，信賴域的Hessian矩陣始終是正定的，則總可以找到一個[dk]，并且只要[dk≤Δk]時，[dk]一定是子問題的最優解，也即得到惟一一個極大似然解，從而保證全局收斂特性。

4 仿真實例

為了驗證本文方法的有效性，將其應用于AM信號的接收仿真試驗中，AM信號中心頻率為100 kHz，帶寬為10 kHz，采樣率為1 MS/s，接收信號中包括3個不同路徑得到的信號源：

[y（n）=i=13αis（n-τi）+w（n）] （18）

各路徑相對于參考信號的延遲，分別為[τ1=100 μs，τ2=200 μs]和[τ3=300 μs。]振幅均為[αi=1，][i=1，2，3]。信噪比為-10 dB。

4.1 算法誤差分析

當參考信號與接收信號之間幅度比為-30 dB時，[e]代表估計值與原始值之間的均方根誤差，算法估計誤差為：

[e=eα1，eα2，eα3，eτ1，eτ2，eτ3]

式中，通過蒙特卡羅100次計算，得到結果如表1所示。

從表1算法估計誤差表可以看到利用信賴域EM算法的估計效果明顯要高于原EM算法，當迭代次數為80次時，信賴域EM算法已經很接近穩定值了，而原EM算法誤差還比較大。如果原EM算法也要實現同樣的效果，至少需要150步以上。

4.2 算法收斂速度分析

基于信賴域的EM算法和EM算法的收斂情況如圖3所示。算法收斂，表示兩種算法的最大似然值及估計參數均保持不變。圖中橫坐標表示接收信號相對與直達波參考信號幅度之比，一般在實際信號接收過程中，散射波信號一般都非常微弱，幅度也都會小于直達波參考信號，所以著重考慮接收信號比較小的情況。縱坐標表示不同幅度比情況下，兩種算法實現收斂所需的迭代次數。

從上述圖中可以看到，EM算法的收斂都是平穩緩慢變化的，當信噪比比較低的情況下，迭代的次數比較多。且為了更好的比較兩者之間的關系，圖中超過200步的均以200步來表示。而且當接收信號幅度比較小的時候，原EM算法有時甚至無法實現正確收斂。不過在圖中也可以看到，如果接收信號幅度與直達波信號幅度之間是可以比擬的情況下，EM算法的收斂速度要優于信賴域EM算法，這是由于信賴域EM算法都要進行信賴域的計算和判斷。而隨著接收信號幅度的降低，利用信賴域進行時延估計相對于EM算法花費時間來說，已經可以忽略不計了。

5 結 語

通過以上實例的仿真分析可以看出，當接收信號信噪比比較低時，以及接收信號相對于直達波信號非常微弱的時候，通過信賴域的EM算法，可以有效地解決原EM算法收斂速度慢，甚至無法收斂的效果。而且由于EM算法將多維優化問題轉換為一維問題，使得信賴域求解變得非常簡單，也保證了信賴域的收斂特性。因此，基于信賴域的EM算法，提高了多徑時延在弱信號和低信噪比情況下的估計性能，也有效提高EM算法的收斂性能。

參考文獻

[1] KIRSTEINS P， QUAZI A. Exact maximun likelihood time delay estimation for deterministic signals [C]// proceedings of EURASIP Conference. [S.l.]： Site Seer， 1988： 531?534.

[2] DEMPSTER A P， LAIRD N， RUBIN D B. Maximun likelihood from incomplete data via the EM algorithm [J]. IEEE Trans. on Vehicular Technology， 1977， 23（3）： 1?23.

[3] FEEDER M， WEINSTEIN E. Parameter estimation of superimposed signals using the EM algorithm [J]. IEEE Transactions on Acoustics， Speech， and Signal Processing， 1988， 36（4）： 477?489.

[4] COLEMAN T F， LI Yu?ying. An interior trust region approach for nonlinear minimization subject to bounds [J]. SIAM OPTIM， 2006， 6（2）： 418?445.

[5] SORENSEN D C. Newton’s method with a model trust region modification [J]. SIAM J. Numer. Anal.， 2006， 19（2）： 409?426.

[6] 山拜·達拉拜，曹紅麗，尤努斯·艾沙.基于遺傳算法的K?means初始化EM算法及聚類應用[J].現代電子技術，2010，33（15）：102?103.