基于信赖域的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.