基追踪去噪的高效向量匹配算法

宇哲伦，杨　帆，曾　璇

(复旦大学 专用集成电路与系统国家重点实验室，上海 201203)



基追踪去噪的高效向量匹配算法

宇哲伦，杨帆，曾璇

(复旦大学 专用集成电路与系统国家重点实验室，上海 201203)

提出了一种针对有噪声频率响应的基追踪去噪的高效向量匹配(BPDN-VF)算法，该算法在向量匹配(VF)算法的基础上，利用压缩感知领域的基追踪去噪(Basis Pursuit Denoising， BPDN)方法，可以有效地从有噪声的频率响应中精确恢复传递函数.与基于方差加权的向量匹配算法相比，提出的方法不仅可以减小至少87.5%的采样次数，还可以将从有噪声的频率响应中得到的拟合结果的误差平均减少20.5%.

基追踪去噪； 有理逼近； 宏建模； 向量匹配

在系统理论研究中，常常会用一个有理的极点-零点函数来拟合线性时不变系统的频域响应.由于这个拟合过程是非线性的，确定这样的拟合函数是个难题.为了去除非线性，该拟合函数的分母需要固定在某些选取合适的多项式上.这样做会降低拟合过程的质量，甚至得不到精确的拟合解.

向量匹配(Vector Fitting， VF)算法[1]是一种从测量或仿真的频域数据中拟合有理传递函数模型的高效算法.从一组初始极点开始，VF逐步迭代地把这些极点放在更合适的位置.由于它的鲁棒和高效的表达形式，该算法已经在众多领域得到了广泛应用，如电源系统的瞬态分析[2]、微波系统建模[3-4]以及格林函数的表示[5]等.VF算法的收敛性和精确度在大多数应用中已被证明是非常优秀的.然而，在某些场合，如待拟合的频率响应被噪声污染的情况下，VF算法的精确度和收敛性会受到明显影响.

而松弛向量匹配(Relaxed Vector Fitting， RVF)算法[6]却可以通过在极点确定步骤引进一个松弛的非平凡的限制来提升VF算法重置极点到更合适位置的能力.相比传统的VF算法，RVF算法在有噪声的频率响应情况下可以得到更好的收敛性和精确度，但是仍有进一步提升的空间.近年来，基于方差加权的松弛向量匹配(Variance Weighted Relaxed Vector Fitting， VWRVF)算法[7]应用了最小二乘加权的函数来减小频率响应中的噪声带来的影响，所用的加权函数是噪声数据的方差，可以进一步提升RVF算法的收敛性和精确度.该算法需要抽样检测频率响应很多次来获取含噪声数据的方差，如果这些频率响应是测量得到的数据，需要重复测量很多次才能获得方差，因此代价很高.

本文借鉴了压缩感知领域的基追踪去噪(Basis Pursuit Denoising， BPDN)算法[8]的思想以从含噪声的频率响应中精确地恢复传递函数.在提出的新算法中，保持VF算法的基本思想不变，但应用BPDN算法来求解包含噪声的最小二乘问题.这种新算法被称为基追踪去噪的向量匹配(Basis-Pursuit-Denoising-based Vector Fitting， BPDN-VF)算法.实验结果表明BPDN-VF算法可以从含噪声的频率响应中以更高的收敛性得到更加精确的拟合结果.同时，相比VWRVF算法，该算法不需要重复采样频率响应来获得噪声数据的方差，极大降低了计算代价.

1　背景介绍

VF算法，RVF算法和VWRVF算法的共同目标是通过一个有理函数f(s)来拟合频域的响应H(s)：

(1)

其中：s是拉普拉斯变量，{pn}和{rn}分别代表极点和残量，d和e是可选项的系数.通常，这一拟合问题是个非线性最小二乘(Least-Square， LS)问题.

(2)

其中

(3)

这里{an}是一组初始极点.在RVF算法[6]中，常数1被替换成松弛变量h来进一步提升VF算法重置极点到更合适位置的能力.为了避免式(2)的平凡解，RVF算法在最小二乘问题中附加了一行

(4)

它强制σ(s)的实部在给定的频率采样点上的和等于非零值，而不需要固定式(3)中任何自由变量.

由于f(s)的极点就是σ(s)的零点，因此求解式(2)之后，f(s)的极点{pn}(或σ(s)的零点)可以通过解一个简单的特征值问题得到[1].在求得新的极点后，可以用新的极点{pn}代替旧的极点{an}，重新求解式(2)，并再次求解特征值问题获得新的极点，重复上述过程直到极点收敛.在无噪声的情况下，这个极点重置的过程会在1～3个迭代内收敛.

一旦极点{pn}确定了，f(s)的残量{rn}(以及项d和项e)就可以通过求解式(1)得到，这时式(1)可以看作另一个线性的最小二乘问题(此时，极点已知).因此式(1)中的有理逼近就通过多阶段的线性最小二乘问题估算出来，也避免了非线性优化问题的求解.

为了进一步提高RVF算法的收敛性和精确度，VWRVF算法[7]在最小二乘问题式(1)和式(2)中引入了加权函数

(5)

其中包含了含噪声采样点的方差信息，方差{v(sm)}是在重复测量(至少8次[7])的基础上从含噪声的数据中得到.方差{v(sm)}可以代表数据采样点的质量.通过引入方差作为加权函数，根据数据采样点的质量进行加权，因而减小了噪声的影响.

2　基追踪去噪的高效向量匹配算法

2.1信号和噪声模型

考虑数据采样点是在一组离散频率上测量得到的，在现实应用中，测量的数据会不可避免地受到噪声的影响.假设在sm处测量得到的数据采样点是以下形式：

H(sm)=Hc(sm)+z(sm)，

(6)

其中：H(sm)是测量得到的响应；z(sm)是测量数据采样点时未知的复高斯白噪声；Hc(sm)是未受噪声影响的精确的信号.

2.2基追踪去噪的向量匹配算法

我们借鉴了压缩感知领域的BPDN算法的思想来减小传递函数逼近问题中的噪声的影响.考虑以下问题：

b=Ax+z，

(7)

BPDN算法从A的列中提取出一个子集来表示b，其目标为最小化提取出的列的数量(或等价地，最小化向量x中的非零项的个数).x因此从含噪声的数据b中得以重建.BPDN算法将式(7)转化为如下的优化问题：

(8)

其中λ是松弛参数，平衡了逼近过程中的误差和表示的稀疏性.

式(8)是个典型的凸优化问题，可以利用许多经典算法和软件[9]解决.式(8)可以等价为如下的二次规划问题[8]：

subjecttoΦα+δp=y， α≥0，δ=1，

(9)

其中Φ=(A，-A)，y=b，c=λ.这个问题可以用块协调松弛(Block-Coordinate-Relaxation， BCR)算法[10]来求解.

在提出的算法中，BPDN算法应用在解决VF的最小二乘问题上.对于极点确定问题式(2)，相应的矩阵A可以表示为

(10)

相应的未知向量x和向量b表示为

(11)

(12)

极点确定问题和传统问题式(7)略有不同，是由于在矩阵A的元素中存在含噪声的项f(si)，而传统问题式(7)中的矩阵A的元素是确定性的.取A的包含噪声项f(si)的一列举例：

(13)

利用BPDN迭代求解式(2)后，可以确定出去除噪声干扰的极点.极点确定后，残量可以通过求解式(1)得到，此时由于极点已知，该问题仍然为包含噪声项的线性最小二乘问题.这个最小二乘问题类似传统问题式(7)，仍然可以用BPDN求解.

因此，可将BPDN-VF算法步骤描述如下：

(1) 根据频率数据样本，赋值一组初始极点{an}，构造式(2)的待解方程.

(2) 利用BPDN求解式(2)，得到系数{rn}(以及可能的d和e).通过求解特征值问题，计算极点{pn}.用{pn}代替{an}，重复此步骤，直到{pn}收敛或达到规定的最大迭代次数.

(3) 根据求得的极点{pn}，利用BPDN求解式(1)，得到残量{rn}(以及项d和项e).

通过以上步骤，可以得到拟合的有理函数模型f(s).

3　实验结果及分析

为了验证新提出方法的高效性，分别使用BPDN-VF算法和基于方差加权的VWRVF算法[7]来逼近两个包含噪声的频率响应的测例.两个测例均选自参考文献中的经典测例，通过对比原频率响应与利用不同VF算法拟合后频率响应的误差，可以看出不同VF算法在有噪声情况下的精确度和收敛性.

3.1测例1

第一个测例为18阶的频率范围在0～100kHz的频率响应，来源于文献[1]中的非平滑测例.实验假设的极点、残量、常数项和比例项可以在文献[1]中找到.

在根据测例的极点分析传递函数的频率范围之后，取100个在相应频率范围内均匀分布的采样点.这些采样点会分别受到30dB和20dB复高斯白噪声的污染.在有噪声的情况下，对于极点确定过程1～3个迭代是不够的.为了提高准确度，一般需要多于10个迭代.为了展示迭代过程中相应的逼近误差，在每个极点确定的迭代之后计算了拟合传递函数相比无噪声精确传递函数的误差.图2和图3分别展示了在信噪比(SignaltoNoiseRatio，SNR)为20dB、30dB时，不同方法在不同迭代次数下的均方根(RootMeanSquare，RMS)误差.

表1　迭代过程中的最小均方根误差(例1)

表1展示了在不同SNR的情况下，迭代过程中不同方法可以达到的最精确的结果(即最小的均方根误差).图4和图5分别展示了在不同SNR的情况下，不同方法各自达到最精确结果时的拟合结果对比.

由图2～图5及表1的结果可以看出，BPDN-VF可以得到比VWRVF更加精确的结果(由表1计算可得，结果的精确度平均提高了23.5%)，且收敛性不会受到噪声的影响.另外，VWRVF需要采样频率响应至少8次[7]以获取含噪声的数据采样点的方差，如果这些数据是测量得到的，所需的测量代价可能会很高.而BPDN-VF不需要方差信息，只需测量一次就可以获得精确的拟合结果，因此可以将采样次数从8次减小到1次，减少了至少87.5%.

3.2测例2

第二个测例为频率范围在0～100kHz的频率响应，来源于文献[6]中的FDNE测例.实验使用的一组采样点可以在文献[11]中找到.

得到300个在相应频率范围内均匀分布的精确的频率响应采样点后，在这些采样点上分别施以30dB和20dB的加性复高斯白噪声.和第一个例子相同，在每个极点确定的迭代之后计算了拟合传递函数相比精确传递函数的误差.图6和图7分别展示了在不同SNR的情况下，不同方法的均方根误差随迭代次数的变化情况.图8和图9分别展示了在不同SNR的情况下，不同VF方法的拟合结果对比.表2展示了迭代过程中不同方法可以达到的最精确的结果.

由图6～图9以及表2的结果可以看出，BPDN-VF可以得到比VWRVF更加精确的结果，且收敛性不会受到噪声的影响.由表2可以计算得出，BPDN-VF得到的结果精确度平均比VWRVF提升17.6%.另外，由于BPDN-VF算法不需要获得数据采样点的方差，BPDN-VF算法相比VWRVF方法可以极大降低测量代价.

表2　迭代过程中的最小均方根误差(例2)

综上所述，BPDN-VF算法相比VWRVF算法，可将测例1的结果精确度平均提高23.5%，测例2平均提高17.6%.两个测例的拟合结果的精确度平均提升了20.5%.

4　总　结

本文提出了一种针对有噪声频率响应的改进的高效VF算法——BPDN-VF算法，在VF算法的基础上，应用了BPDN算法从有噪声的频率响应中精确地恢复传递函数.实验结果表明本文提出的方法与基于方差加权的VWRVF算法相比，在大大减小测量次数的基础上(至少87.5%)可以从有噪声的频率响应中得到更加精确的拟合结果(精确度平均提升了20.5%).

[1]GUSTAVSEN B， SEMLYEN A. Rational approximation of frequency domain responses by vector fitting [J].IEEETransactionsonPowerDelivery， 1999，14(3)： 1052-1061.

[2]MORCHED A， GUSTAVSEN B， TARTIBI M. A universal model for accurate calculation of electromagnetic transients on overhead lines and underground cables [J].IEEETransactionsonPowerDelivery， 1999，14(3)： 1032-1038.

[3]LI E P， LIU E X， LI L W，etal. A coupled efficient and systematic full-wave time-domain macromodeling and circuit simulation method for signal integrity analysis of high-speed interconnects [J].IEEETransactionsonAdvancedPackaging， 2004，27(1)： 213-223.

[4]ANTONINI G. SPICE equivalent circuits of frequency-domain responses [J].IEEETransactionsonElectromagneticCompatibility， 2003，45(3)： 502-512.

[5]OKHMATOVSKI V， CANGELLARIS A C. Evaluation of layered media Green’s functions via rational function fitting [J].IEEEMicrowaveandWirelessComponentsLetters， 2004，14(1)： 22-24.

[6]GUSTAVSEN B. Improving the pole relocating properties of vector fitting [J].IEEETransactionsonPowerDelivery， 2006，21(3)： 1587-1592.

[7]FERRANTI F， ROLAIN Y， KNOCKAERT L，etal. Variance weighted vector fitting for noisy frequency responses [J].IEEEMicrowaveandWirelessComponentsLetters， 2010，20(4)： 187-189.

[8]CHEN S S， DONOHO D L， SAUNDERS M A. Atomic decomposition by basis pursuit [J].SIAMJournalonScientificComputing， 1998，20(1)： 33-61.

[9]BECKER S R， CANDS E J， GRANT M C. Templates for convex cone problems with applications to sparse signal recovery [J].MathematicalProgrammingComputation， 2011，3(3)： 165-218.

[10]SARDY S， BRUCE A G， TSENG P. Block coordinate relaxation methods for nonparametric wavelet denoising [J].JournalofComputationalandGraphicalStatistics， 2000，9(2)： 361-379.

[11]The Vector Fitting Web Site. VFIT3.zip[D/OL].(2013-03-20).https：∥www.sintef.no/projectweb/vectfit/downloads/.

BPDN-VF： Basis-Pursuit-Denoising-based Vector Fitting Algorithm

YU Zhelun， YANG Fan， ZENG Xuan

(StateKeyLaboratoryofASIC&Systems，FudanUniversity，Shanghai201203，China)

In this paper， we propose an efficient Basis-Pursuit-Denoising-based Vector Fitting method for noisy frequency responses. On the basis of VF method， we employ the well-known Basis Pursuit Denoising(BPDN) method from the community of compressive sensing to accurately recover the transfer functions from the noisy frequency responses. Compared with the Variance Weighted Relaxed Vector Fitting method， the proposed method requires at least 87.5% fewer measurements and can achieve results with 20.5% error reduction at average from the noisy frequency responses.

basis pursuit denoising； rational approximation； macromodeling； vector fitting(VF)

0427-7104(2016)04-0425-06

2015-09-17

宇哲伦(1991—)，女，硕士研究生；杨帆，男，副教授，通讯联系人，E-mail： yangfan@fudan.edu.cn；曾璇，女，教授，zengxuan@fudan.edu.cn.

TN 79

A