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

宇哲倫，楊　帆，曾　璇

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

?

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

宇哲倫，楊帆，曾璇

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

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

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

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

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

而松弛向量匹配(Relaxed Vector Fitting， RVF)算法[6]卻可以通過在極點確定步驟引進一個松弛的非平凡的限制來提升VF算法重置極點到更合適位置的能力.相比傳統(tǒng)的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)中的有理逼近就通過多階段的線性最小二乘問題估算出來，也避免了非線性優(yōu)化問題的求解.

為了進一步提高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)轉化為如下的優(yōu)化問題：

(8)

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

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

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

(13)

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

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

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

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

(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