宇哲倫，楊　帆，曾　璇

(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點實驗室，上海 201203)

?

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

宇哲倫，楊帆，曾璇

(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點實驗室，上海 201203)

提出了一種針對有噪聲頻率響應(yīng)的基追蹤去噪的高效向量匹配(BPDN-VF)算法，該算法在向量匹配(VF)算法的基礎(chǔ)上，利用壓縮感知領(lǐng)域的基追蹤去噪(Basis Pursuit Denoising， BPDN)方法，可以有效地從有噪聲的頻率響應(yīng)中精確恢復(fù)傳遞函數(shù).與基于方差加權(quán)的向量匹配算法相比，提出的方法不僅可以減小至少87.5%的采樣次數(shù)，還可以將從有噪聲的頻率響應(yīng)中得到的擬合結(jié)果的誤差平均減少20.5%.

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

在系統(tǒng)理論研究中，常常會用一個有理的極點-零點函數(shù)來擬合線性時不變系統(tǒng)的頻域響應(yīng).由于這個擬合過程是非線性的，確定這樣的擬合函數(shù)是個難題.為了去除非線性，該擬合函數(shù)的分母需要固定在某些選取合適的多項式上.這樣做會降低擬合過程的質(zhì)量，甚至得不到精確的擬合解.

向量匹配(Vector Fitting， VF)算法[1]是一種從測量或仿真的頻域數(shù)據(jù)中擬合有理傳遞函數(shù)模型的高效算法.從一組初始極點開始，VF逐步迭代地把這些極點放在更合適的位置.由于它的魯棒和高效的表達(dá)形式，該算法已經(jīng)在眾多領(lǐng)域得到了廣泛應(yīng)用，如電源系統(tǒng)的瞬態(tài)分析[2]、微波系統(tǒng)建模[3-4]以及格林函數(shù)的表示[5]等.VF算法的收斂性和精確度在大多數(shù)應(yīng)用中已被證明是非常優(yōu)秀的.然而，在某些場合，如待擬合的頻率響應(yīng)被噪聲污染的情況下，VF算法的精確度和收斂性會受到明顯影響.

而松弛向量匹配(Relaxed Vector Fitting， RVF)算法[6]卻可以通過在極點確定步驟引進(jìn)一個松弛的非平凡的限制來提升VF算法重置極點到更合適位置的能力.相比傳統(tǒng)的VF算法，RVF算法在有噪聲的頻率響應(yīng)情況下可以得到更好的收斂性和精確度，但是仍有進(jìn)一步提升的空間.近年來，基于方差加權(quán)的松弛向量匹配(Variance Weighted Relaxed Vector Fitting， VWRVF)算法[7]應(yīng)用了最小二乘加權(quán)的函數(shù)來減小頻率響應(yīng)中的噪聲帶來的影響，所用的加權(quán)函數(shù)是噪聲數(shù)據(jù)的方差，可以進(jìn)一步提升RVF算法的收斂性和精確度.該算法需要抽樣檢測頻率響應(yīng)很多次來獲取含噪聲數(shù)據(jù)的方差，如果這些頻率響應(yīng)是測量得到的數(shù)據(jù)，需要重復(fù)測量很多次才能獲得方差，因此代價很高.

本文借鑒了壓縮感知領(lǐng)域的基追蹤去噪(Basis Pursuit Denoising， BPDN)算法[8]的思想以從含噪聲的頻率響應(yīng)中精確地恢復(fù)傳遞函數(shù).在提出的新算法中，保持VF算法的基本思想不變，但應(yīng)用BPDN算法來求解包含噪聲的最小二乘問題.這種新算法被稱為基追蹤去噪的向量匹配(Basis-Pursuit-Denoising-based Vector Fitting， BPDN-VF)算法.實驗結(jié)果表明BPDN-VF算法可以從含噪聲的頻率響應(yīng)中以更高的收斂性得到更加精確的擬合結(jié)果.同時，相比VWRVF算法，該算法不需要重復(fù)采樣頻率響應(yīng)來獲得噪聲數(shù)據(jù)的方差，極大降低了計算代價.

1　背景介紹

VF算法，RVF算法和VWRVF算法的共同目標(biāo)是通過一個有理函數(shù)f(s)來擬合頻域的響應(yīng)H(s)：

(1)

其中：s是拉普拉斯變量，{pn}和{rn}分別代表極點和殘量，d和e是可選項的系數(shù).通常，這一擬合問題是個非線性最小二乘(Least-Square， LS)問題.

(2)

其中

(3)

這里{an}是一組初始極點.在RVF算法[6]中，常數(shù)1被替換成松弛變量h來進(jìn)一步提升VF算法重置極點到更合適位置的能力.為了避免式(2)的平凡解，RVF算法在最小二乘問題中附加了一行

(4)

它強制σ(s)的實部在給定的頻率采樣點上的和等于非零值，而不需要固定式(3)中任何自由變量.

由于f(s)的極點就是σ(s)的零點，因此求解式(2)之后，f(s)的極點{pn}(或σ(s)的零點)可以通過解一個簡單的特征值問題得到[1].在求得新的極點后，可以用新的極點{pn}代替舊的極點{an}，重新求解式(2)，并再次求解特征值問題獲得新的極點，重復(fù)上述過程直到極點收斂.在無噪聲的情況下，這個極點重置的過程會在1～3個迭代內(nèi)收斂.

一旦極點{pn}確定了，f(s)的殘量{rn}(以及項d和項e)就可以通過求解式(1)得到，這時式(1)可以看作另一個線性的最小二乘問題(此時，極點已知).因此式(1)中的有理逼近就通過多階段的線性最小二乘問題估算出來，也避免了非線性優(yōu)化問題的求解.

為了進(jìn)一步提高RVF算法的收斂性和精確度，VWRVF算法[7]在最小二乘問題式(1)和式(2)中引入了加權(quán)函數(shù)

(5)

其中包含了含噪聲采樣點的方差信息，方差{v(sm)}是在重復(fù)測量(至少8次[7])的基礎(chǔ)上從含噪聲的數(shù)據(jù)中得到.方差{v(sm)}可以代表數(shù)據(jù)采樣點的質(zhì)量.通過引入方差作為加權(quán)函數(shù)，根據(jù)數(shù)據(jù)采樣點的質(zhì)量進(jìn)行加權(quán)，因而減小了噪聲的影響.

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

2.1信號和噪聲模型

考慮數(shù)據(jù)采樣點是在一組離散頻率上測量得到的，在現(xiàn)實應(yīng)用中，測量的數(shù)據(jù)會不可避免地受到噪聲的影響.假設(shè)在sm處測量得到的數(shù)據(jù)采樣點是以下形式：

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

(6)

其中：H(sm)是測量得到的響應(yīng)；z(sm)是測量數(shù)據(jù)采樣點時未知的復(fù)高斯白噪聲；Hc(sm)是未受噪聲影響的精確的信號.

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

我們借鑒了壓縮感知領(lǐng)域的BPDN算法的思想來減小傳遞函數(shù)逼近問題中的噪聲的影響.考慮以下問題：

b=Ax+z，

(7)

BPDN算法從A的列中提取出一個子集來表示b，其目標(biāo)為最小化提取出的列的數(shù)量(或等價地，最小化向量x中的非零項的個數(shù)).x因此從含噪聲的數(shù)據(jù)b中得以重建.BPDN算法將式(7)轉(zhuǎn)化為如下的優(yōu)化問題：

(8)

其中λ是松弛參數(shù)，平衡了逼近過程中的誤差和表示的稀疏性.

式(8)是個典型的凸優(yōu)化問題，可以利用許多經(jīng)典算法和軟件[9]解決.式(8)可以等價為如下的二次規(guī)劃問題[8]：

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

(9)

其中Φ=(A，-A)，y=b，c=λ.這個問題可以用塊協(xié)調(diào)松弛(Block-Coordinate-Relaxation， BCR)算法[10]來求解.

在提出的算法中，BPDN算法應(yīng)用在解決VF的最小二乘問題上.對于極點確定問題式(2)，相應(yīng)的矩陣A可以表示為

(10)

相應(yīng)的未知向量x和向量b表示為

(11)

(12)

極點確定問題和傳統(tǒng)問題式(7)略有不同，是由于在矩陣A的元素中存在含噪聲的項f(si)，而傳統(tǒng)問題式(7)中的矩陣A的元素是確定性的.取A的包含噪聲項f(si)的一列舉例：

(13)

利用BPDN迭代求解式(2)后，可以確定出去除噪聲干擾的極點.極點確定后，殘量可以通過求解式(1)得到，此時由于極點已知，該問題仍然為包含噪聲項的線性最小二乘問題.這個最小二乘問題類似傳統(tǒng)問題式(7)，仍然可以用BPDN求解.

因此，可將BPDN-VF算法步驟描述如下：

(1) 根據(jù)頻率數(shù)據(jù)樣本，賦值一組初始極點{an}，構(gòu)造式(2)的待解方程.

(2) 利用BPDN求解式(2)，得到系數(shù){rn}(以及可能的d和e).通過求解特征值問題，計算極點{pn}.用{pn}代替{an}，重復(fù)此步驟，直到{pn}收斂或達(dá)到規(guī)定的最大迭代次數(shù).

(3) 根據(jù)求得的極點{pn}，利用BPDN求解式(1)，得到殘量{rn}(以及項d和項e).

通過以上步驟，可以得到擬合的有理函數(shù)模型f(s).

3　實驗結(jié)果及分析

為了驗證新提出方法的高效性，分別使用BPDN-VF算法和基于方差加權(quán)的VWRVF算法[7]來逼近兩個包含噪聲的頻率響應(yīng)的測例.兩個測例均選自參考文獻(xiàn)中的經(jīng)典測例，通過對比原頻率響應(yīng)與利用不同VF算法擬合后頻率響應(yīng)的誤差，可以看出不同VF算法在有噪聲情況下的精確度和收斂性.

3.1測例1

第一個測例為18階的頻率范圍在0～100kHz的頻率響應(yīng)，來源于文獻(xiàn)[1]中的非平滑測例.實驗假設(shè)的極點、殘量、常數(shù)項和比例項可以在文獻(xiàn)[1]中找到.

在根據(jù)測例的極點分析傳遞函數(shù)的頻率范圍之后，取100個在相應(yīng)頻率范圍內(nèi)均勻分布的采樣點.這些采樣點會分別受到30dB和20dB復(fù)高斯白噪聲的污染.在有噪聲的情況下，對于極點確定過程1～3個迭代是不夠的.為了提高準(zhǔn)確度，一般需要多于10個迭代.為了展示迭代過程中相應(yīng)的逼近誤差，在每個極點確定的迭代之后計算了擬合傳遞函數(shù)相比無噪聲精確傳遞函數(shù)的誤差.圖2和圖3分別展示了在信噪比(SignaltoNoiseRatio，SNR)為20dB、30dB時，不同方法在不同迭代次數(shù)下的均方根(RootMeanSquare，RMS)誤差.

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

表1展示了在不同SNR的情況下，迭代過程中不同方法可以達(dá)到的最精確的結(jié)果(即最小的均方根誤差).圖4和圖5分別展示了在不同SNR的情況下，不同方法各自達(dá)到最精確結(jié)果時的擬合結(jié)果對比.

由圖2～圖5及表1的結(jié)果可以看出，BPDN-VF可以得到比VWRVF更加精確的結(jié)果(由表1計算可得，結(jié)果的精確度平均提高了23.5%)，且收斂性不會受到噪聲的影響.另外，VWRVF需要采樣頻率響應(yīng)至少8次[7]以獲取含噪聲的數(shù)據(jù)采樣點的方差，如果這些數(shù)據(jù)是測量得到的，所需的測量代價可能會很高.而BPDN-VF不需要方差信息，只需測量一次就可以獲得精確的擬合結(jié)果，因此可以將采樣次數(shù)從8次減小到1次，減少了至少87.5%.

3.2測例2

第二個測例為頻率范圍在0～100kHz的頻率響應(yīng)，來源于文獻(xiàn)[6]中的FDNE測例.實驗使用的一組采樣點可以在文獻(xiàn)[11]中找到.

得到300個在相應(yīng)頻率范圍內(nèi)均勻分布的精確的頻率響應(yīng)采樣點后，在這些采樣點上分別施以30dB和20dB的加性復(fù)高斯白噪聲.和第一個例子相同，在每個極點確定的迭代之后計算了擬合傳遞函數(shù)相比精確傳遞函數(shù)的誤差.圖6和圖7分別展示了在不同SNR的情況下，不同方法的均方根誤差隨迭代次數(shù)的變化情況.圖8和圖9分別展示了在不同SNR的情況下，不同VF方法的擬合結(jié)果對比.表2展示了迭代過程中不同方法可以達(dá)到的最精確的結(jié)果.

由圖6～圖9以及表2的結(jié)果可以看出，BPDN-VF可以得到比VWRVF更加精確的結(jié)果，且收斂性不會受到噪聲的影響.由表2可以計算得出，BPDN-VF得到的結(jié)果精確度平均比VWRVF提升17.6%.另外，由于BPDN-VF算法不需要獲得數(shù)據(jù)采樣點的方差，BPDN-VF算法相比VWRVF方法可以極大降低測量代價.

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

綜上所述，BPDN-VF算法相比VWRVF算法，可將測例1的結(jié)果精確度平均提高23.5%，測例2平均提高17.6%.兩個測例的擬合結(jié)果的精確度平均提升了20.5%.

4　總　結(jié)

本文提出了一種針對有噪聲頻率響應(yīng)的改進(jìn)的高效VF算法——BPDN-VF算法，在VF算法的基礎(chǔ)上，應(yīng)用了BPDN算法從有噪聲的頻率響應(yīng)中精確地恢復(fù)傳遞函數(shù).實驗結(jié)果表明本文提出的方法與基于方差加權(quán)的VWRVF算法相比，在大大減小測量次數(shù)的基礎(chǔ)上(至少87.5%)可以從有噪聲的頻率響應(yīng)中得到更加精確的擬合結(jié)果(精確度平均提升了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，F(xiàn)udanUniversity，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—)，女，碩士研究生；楊帆，男，副教授，通訊聯(lián)系人，E-mail： yangfan@fudan.edu.cn；曾璇，女，教授，zengxuan@fudan.edu.cn.

TN 79

A