基于Newton 迭代算法的低復(fù)雜度信號(hào)檢測(cè)算法

劉剛，婁增進(jìn)，林勤華，郭漪

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071）

0 引言

超大規(guī)模多輸入多輸出（MIMO,multiple-input multiple-output）技術(shù)是6G 太赫茲通信系統(tǒng)[1]重要的組成部分，它不僅使通信系統(tǒng)更加可靠，還可以擴(kuò)大通信系統(tǒng)容量。然而6G 系統(tǒng)中[2]，天線陣列中將會(huì)放置上萬(wàn)個(gè)天線單元[3]，從而使MIMO 系統(tǒng)接收端的計(jì)算復(fù)雜度令人難以承受。采用超大型天線陣列的分組和控制技術(shù)，可將天線陣列拆分成多個(gè)組別[4]，減少陣列中天線單元數(shù)目，使傳統(tǒng)MIMO信號(hào)檢測(cè)算法得以應(yīng)用。

大規(guī)模MIMO 技術(shù)能夠充分利用空間資源，大幅提高系統(tǒng)的頻譜利用率與能量效率，而天線數(shù)目的大量增加也使系統(tǒng)的容量得以提高[5]。在大規(guī)模MIMO 信號(hào)檢測(cè)領(lǐng)域已有大量研究成果，這些成果在計(jì)算復(fù)雜度、檢測(cè)性能、算法收斂速度等方面有很大貢獻(xiàn)。Jiang 等[6]提出了一種基于Jacobi的迭代算法；Gao 等[7]提出了一種基于Richardson 算法的檢測(cè)算法。相比最小均方誤差（MMSE,minimum mean square error）算法，這2 種算法的計(jì)算復(fù)雜度較低，但存在收斂速度慢的弊端。Bakulin 等[8]對(duì)線性方程進(jìn)行了變換，避開(kāi)了高維矩陣求逆運(yùn)算，算法復(fù)雜度有所下降，但需要12 次迭代才能取得較好性能。Zhu 等[9]提出了一種基于Neumann 級(jí)數(shù)展開(kāi)的檢測(cè)算法，通過(guò)級(jí)數(shù)展開(kāi)近似矩陣求逆結(jié)果，該算法由于具有較低復(fù)雜度，得到了廣泛的應(yīng)用。但是該算法在展開(kāi)階數(shù)大于或等于3 時(shí)，計(jì)算復(fù)雜度高于矩陣求逆。Bj?rck[10]提出了一種利用松弛因子加速迭代的方法。Gao 等[11]提出了一種最優(yōu)松弛因子的超松弛迭代算法。Zhang 等[12]提出了改進(jìn)對(duì)稱超松弛迭代算法，經(jīng)由數(shù)次迭代后即可得到較好的檢測(cè)性能，但是由于系統(tǒng)收發(fā)端天線數(shù)目對(duì)算法性能影響很大，適用場(chǎng)景受到很大限制。Jin 等[13]提出了一種基于Newton 迭代的信號(hào)檢測(cè)算法，獲得了較快的收斂速度，檢測(cè)精度也較高，但是過(guò)多的矩陣乘法運(yùn)算帶來(lái)較高的計(jì)算復(fù)雜度。Chataut等[14]基于近似消息傳遞（AMP,approximate message passing）算法，提出了一種低復(fù)雜度MIMO 檢測(cè)算法，提高了MIMO 檢測(cè)精度，但是通常需要6～8次迭代才能接近MMSE 算法性能，收斂速度受限。

本文在太赫茲場(chǎng)景下，提出了基于Newton 迭代的低復(fù)雜度信號(hào)檢測(cè)算法。通過(guò)改進(jìn)迭代初值、加入步長(zhǎng)因子、加入調(diào)節(jié)因子等操作，降低了算法的計(jì)算復(fù)雜度，加快了算法的收斂速度，保證了算法的穩(wěn)定性。算法可工作在θ≠0 和θ=0 這2 種模式。當(dāng)θ≠0 時(shí)，經(jīng)歷3 次迭代即可達(dá)到MMSE 算法性能；當(dāng)θ=0 時(shí)，需要4 次迭代才能達(dá)到MMSE算法性能，但是復(fù)雜度大大降低，尤其適于處理數(shù)據(jù)量大、實(shí)時(shí)性要求不高的場(chǎng)景。

1 理論基礎(chǔ)

1.1 系統(tǒng)模型

假設(shè)MIMO 系統(tǒng)包含N個(gè)接收天線、K個(gè)發(fā)射天線，N?K，系統(tǒng)模型如圖1 所示。

圖1 MIMO 系統(tǒng)模型

MIMO 系統(tǒng)接收信號(hào)可以表示為

其中，x=(x1,x2,…,xK)T∈CK×1表示發(fā)射信號(hào)，xk為第k根發(fā)射天線信號(hào)；y=(y1,y2,…,yN)T∈CN×1表示接收信號(hào)，yk為第k根接收天線信號(hào)；H=(h1,h2,…,hK)∈CN×K表示信道衰落矩陣，hi=(h1,i,h2,i,…,hN,i)T∈CN×1，hm,n為第n個(gè)發(fā)射天線與第m個(gè)接收天線之間的衰落信道增益，且服從hm,n～CN(0,1)；n=(n1,n2,…,nN)T∈CN×1表示加性白高斯噪聲，ni的均值為0，方差為。這里假設(shè)信號(hào)經(jīng)歷平坦衰落信道。

對(duì)接收信號(hào)進(jìn)行MMSE 檢測(cè)，可得

若令b=HHy表示匹配濾波器，A=(HHH+σ2Ik)-1表示MMSE 濾波矩陣，則式（2）可以重寫(xiě)為

其中，A-1的計(jì)算復(fù)雜度為O(K3)[15]。

1.2 迭代算法基本思想

迭代算法基本思想是將A分解成A=P+Q的形式[16]，其中P是非奇異的，迭代公式為

其中，B=-P-1Q=IK-P-1A，f=p-1b，k為迭代次數(shù)。當(dāng)滿足=0時(shí)，迭代收斂。假設(shè)初始估計(jì)x(0)=P-1b，則第k次迭代結(jié)果可以表示為

1.3 Newton 迭代算法

令X0是-1A的初始估計(jì)，則第k次Newton 迭代可以寫(xiě)成[17]

當(dāng)滿足||I-AX0||＜1時(shí)，實(shí)現(xiàn)收斂。因?yàn)镹ewton迭代算法為二次收斂，所以它的計(jì)算復(fù)雜度僅取決于迭代次數(shù)。文獻(xiàn)[16]指出，Newton 迭代算法k次迭代的結(jié)果與基于Neumann 級(jí)數(shù)展開(kāi)的算法中2k-1 次迭代的結(jié)果相同。因此，在相同的系統(tǒng)配置下，Newton 迭代算法要比其他的迭代算法具有更快的收斂速度。

2 低復(fù)雜度MIMO 檢測(cè)算法

本文基于Newton 迭代算法進(jìn)行MIMO 檢測(cè)。通過(guò)改進(jìn)初始矩陣來(lái)降低算法復(fù)雜度，提高了算法收斂速度；通過(guò)加入步長(zhǎng)因子，大幅度提高了算法收斂速度，之后又通過(guò)加入調(diào)節(jié)因子保證了算法的穩(wěn)定性和可靠性?；贜ewton 迭代算法的低復(fù)雜度信號(hào)檢測(cè)（調(diào)節(jié)因子θ≠0）如算法1 所示。

算法1基于Newton 迭代算法的低復(fù)雜度信號(hào)檢測(cè)（調(diào)節(jié)因子θ≠0）

特別地，當(dāng)調(diào)節(jié)因子θ=0 時(shí)，可對(duì)迭代公式進(jìn)一步簡(jiǎn)化，通過(guò)避免MMSE 矩陣計(jì)算進(jìn)一步降低算法復(fù)雜度?；贜ewton 迭代算法的低復(fù)雜度信號(hào)檢測(cè)（調(diào)節(jié)因子θ=0）如算法2 所示。

算法2基于Newton 迭代算法的低復(fù)雜度信號(hào)檢測(cè)（調(diào)節(jié)因子θ=0）

算法2 步驟6)中的迭代公式推導(dǎo)如下。

由于初始迭代矩陣X0=αI，基于式(6)，初次迭代可以寫(xiě)成

其中，x(0)=X0b和V=σ2X0都是對(duì)角矩陣。利用經(jīng)典Newton 迭代公式（即式(6)）進(jìn)行下一步迭代。

此時(shí)有

類似地，可以推出n次迭代的結(jié)果（即步驟6)）為

2.1 初始矩陣X0

由于A=HHH+σ2I是厄米特正定矩陣，該矩陣的上三角部分和下三角部分互為共軛對(duì)稱矩陣，因此矩陣A又可寫(xiě)為

其中，D是由A的主對(duì)角線元素構(gòu)成的矩陣；-L是A的嚴(yán)格上三角部分；而H-L是-L共軛轉(zhuǎn)置后得到的，也就是A的嚴(yán)格下三角部分。

在迭代算法中，常用的矩陣求逆初值主要有2種，一種是Jacobi 算法的初始值X0=D-1，另一種是Richardson 算法的初始值X0=αI。當(dāng)MIMO 系統(tǒng)發(fā)送和接收天線的數(shù)量都變?yōu)闊o(wú)窮大時(shí)，根據(jù)隨機(jī)矩陣?yán)碚?，MMSE 檢測(cè)算法濾波矩陣的最大和最小特征值將保持穩(wěn)定并各自收斂到

在這種情況下，信道硬化現(xiàn)象會(huì)變得異常明顯，此時(shí)濾波矩陣的非對(duì)角線元素幾乎可以忽略，即A可以近似為對(duì)角線元素，此時(shí)有D≈A=NI。

結(jié)合Jacobi 迭代檢測(cè)算法的迭代矩陣

可以得到如下形式的Jacobi 算法迭代矩陣

由式(13)和式(15)可以得到JB的特征值為

由此可以計(jì)算JB的譜半徑為

同時(shí)，對(duì)于Richardson 算法來(lái)說(shuō)，其所對(duì)應(yīng)的迭代矩陣的形式為

最優(yōu)松弛參數(shù)的值通常設(shè)置為

由式(18)和式(19)，并結(jié)合式(13)，可以將準(zhǔn)最優(yōu)松弛參數(shù)寫(xiě)成

由此可進(jìn)一步得到Richardson 算法迭代矩陣的譜半徑為

對(duì)式(17)和式(21)進(jìn)行對(duì)比分析可得

迭代算法中迭代矩陣的譜半徑與算法收斂速度負(fù)相關(guān)[10]，因此可得Richardson 算法的收斂速度更快一些。

由于Newton 迭代算法和其他迭代算法是正相關(guān)的，在迭代算法中，當(dāng)初始矩陣為X0=αI時(shí)，比X0=D-1時(shí)收斂速度更快；相應(yīng)地，在Newton迭代算法中，以X0=αI作為初始迭代矩陣也可以實(shí)現(xiàn)比以X0=D-1作為初始迭代矩陣時(shí)更快的收斂速度。因此，本文選取X0=αI作為改進(jìn)算法的初值。

2.2 步長(zhǎng)因子η

為了提升算法收斂速度，在初值改進(jìn)基礎(chǔ)上，將步長(zhǎng)因子η加入Newton 迭代公式中，從而得到

由于濾波矩陣A=HHH+σ2I是對(duì)稱的，因此初始誤差矩陣e0=I-X0A也是對(duì)稱的，通過(guò)遞推也可以進(jìn)一步證明矩陣ek是對(duì)稱矩陣，且對(duì)于k=0,1,2,…,n均成立。所以ek可以經(jīng)由如下變換實(shí)現(xiàn)對(duì)角化

其中，矩陣U為典型酉矩陣，且UT=U-1，Λk∈CN×K為對(duì)角矩陣。

令對(duì)角矩陣表示為

則誤差矩陣為

此處引用引理1[18-19]。

引理1對(duì)于滿足等式UHU=UUH=I和VHV=VVH=I的酉矩陣U和V，給定一個(gè)非奇異矩陣A∈CK×K，可以得到

這樣一來(lái)，對(duì)于ek的收斂性討論就可以轉(zhuǎn)變成針對(duì)Λk的研究。

根據(jù)迭代算法的收斂性，結(jié)合式(31)可知，-1 ＜ξi,0＜ 1,η＞ 0，從而得到步長(zhǎng)因子η應(yīng)滿足

由式(30)可知，當(dāng)矩陣元素ξi,k+1為0 時(shí)，步長(zhǎng)因子達(dá)到最佳值，即

2.3 調(diào)節(jié)因子θ

根據(jù)凸優(yōu)化理論，如果步長(zhǎng)過(guò)大，可能會(huì)錯(cuò)過(guò)極值點(diǎn)，導(dǎo)致式(29)不成立。為了使算法更加穩(wěn)定，在式(34)中加入調(diào)節(jié)因子θ，即

其中，θ與ξi,k的分布密切相關(guān)。

圖2 給出了X0=αI時(shí)不同θ值對(duì)步長(zhǎng)的影響。從圖2 中可以看出，迭代初始階段，θ越大，步長(zhǎng)越大，尤其當(dāng)θ接近1.0 時(shí)，很容易出現(xiàn)不收斂的情況。綜上，這里設(shè)置θ=0.8，既保證了算法的穩(wěn)定性，又加速了算法收斂。

圖2 X0=αI 時(shí)不同θ 值對(duì)步長(zhǎng)的影響

3 算法復(fù)雜度分析

3.1 初始化部分計(jì)算復(fù)雜度

表1 為本文算法與Newton 迭代算法初始化部分計(jì)算復(fù)雜度比較。從表1 可以看出，本文算法（算法1 和算法2）極大降低了初始化部分的計(jì)算復(fù)雜度。

表1 本文算法與Newton 迭代算法初始化部分計(jì)算復(fù)雜度比較

1) 算法1 初始化部分復(fù)雜度

算法1 中，可以很容易地計(jì)算出b=HHy的計(jì)算復(fù)雜度為NK，X0的計(jì)算復(fù)雜度為K，所以算法1 總的計(jì)算復(fù)雜度為NK+K。

2) 算法2 初始化部分的復(fù)雜度

算法2 中，可以很容易地計(jì)算出b=HHy的計(jì)算復(fù)雜度為NK，X0、V、x(0)的計(jì)算復(fù)雜度分別為K，所以算法2 總的計(jì)算復(fù)雜度為NK+3K。

3) Newton 迭代算法初始化部分復(fù)雜度

對(duì)于Newton 迭代算法的初始化部分，涉及獲取D-1和b=HHy的計(jì)算。獲取D-1的計(jì)算復(fù)雜度為NK2+K，加上HHy部分的計(jì)算復(fù)雜度，總計(jì)算復(fù)雜度為NK2+NK+K。

3.2 迭代過(guò)程計(jì)算復(fù)雜度

表2 為本文算法與Newton 迭代算法迭代過(guò)程復(fù)雜度比較。

表2 本文算法與Newton 迭代算法迭代過(guò)程復(fù)雜度比較

從表2 可以看出，在算法1 中，步長(zhǎng)因子加快了收斂速度，但是無(wú)法避免濾波矩陣A的計(jì)算，故相比算法2，算法1 復(fù)雜度更高一些。但是，相比Newton 迭代算法，算法1復(fù)雜度還是有所降低。

與Newton 迭代算法相比，算法1 由于引入了步長(zhǎng)因子η，因此產(chǎn)生了對(duì)角矩陣和矩陣之間乘法與運(yùn)算X kA，復(fù)雜度為K2；矩陣求跡運(yùn)算trace(ek)，復(fù)雜度為K；迭代公式Xk=Xk-1-ηXk-1(AXk-1-I)中引入η，增加了常數(shù)與矩陣的乘法運(yùn)算η(Xk-1(AXk-1-I))，復(fù)雜度為K2，因此，算法1 每次迭代相比Newton 迭代算法增加 2K2+K的運(yùn)算量。

算法 2在迭代過(guò)程中，首先需要計(jì)算X0HHHx(0)和Vx(0)的計(jì)算復(fù)雜度，分別是2NK+K和K。由于(I-X0HHH-V)x(0)是一個(gè)向量，因此，第n次Newton迭代需要(2n+1-1)(NK+K)的計(jì)算復(fù)雜度。

3.3 算法整體過(guò)程復(fù)雜度

本文算法（算法1 和算法2）、Newton 迭代算法、基于Neumann 級(jí)數(shù)展開(kāi)的算法、文獻(xiàn)[14]算法的總復(fù)雜度比較如表3 所示。

表3 本文算法與其他幾種算法的總復(fù)雜度比較

本文以32×256 MIMO 系統(tǒng)為例，本文算法（算法1 和算法2）以及Newton 迭代算法所需要的初始化部分的計(jì)算復(fù)雜度分別為257K、259K、256K2+257K。為了逼近MMSE 算法性能，三者迭代次數(shù)依次設(shè)為3次、4 次、4 次，迭代過(guò)程中的計(jì)算復(fù)雜度依次為 1798K2+1795K、7 936NK、3840K2+3840K，故總的計(jì)算復(fù)雜度依次為1795K2+2 052K、8195K、4 096K2+4 097K?；贜eumann級(jí)數(shù)展開(kāi)的算法至少需要7次迭代才能接近MMSE 算法的性能，但此時(shí)計(jì)算復(fù)雜度就已經(jīng)達(dá)到了 5K3+256K2+256K，復(fù)雜度達(dá)到了O(K3)的級(jí)別。文獻(xiàn)[14]算法需要8 次迭代才能接近MMSE 算法性能，所需計(jì)算復(fù)雜度為2 048K?？梢钥闯觯惴? 相比算法1 以及Newton 迭代算法，在復(fù)雜度上降低了一個(gè)數(shù)量級(jí)，只有O(K)級(jí)別，與文獻(xiàn)[14]算法屬于同一個(gè)數(shù)量級(jí)。算法1 因?yàn)槌踔档母倪M(jìn)以及收斂速度的提升，相比Newton 迭代算法復(fù)雜度降低很多，但因?yàn)榧尤肓瞬介L(zhǎng)因子，無(wú)法像算法2 那樣將濾波矩陣A進(jìn)行分解，并充分利用不同迭代次數(shù)間的遞推規(guī)律求解第k次迭代的結(jié)果，相比算法2 仍具有較高的復(fù)雜度，但卻有更快的收斂速度。故本文算法可分別用于不同需求的場(chǎng)景。

另外，當(dāng)發(fā)送和接收天線數(shù)目為64×1 024 時(shí)，類似地，同樣可以計(jì)算出算法1、算法2 以及Newton迭代算法所需的計(jì)算復(fù)雜度分別為7174K2+8196K、32 771K、1 6 384K2+16 385K。此種情況下，基于Neumann 級(jí)數(shù)展開(kāi)的方法的復(fù)雜度為 5K3+1024K2+1024K，文獻(xiàn)[14]算法的復(fù)雜度為8192K。所得結(jié)論與之前一致。

4 仿真分析

仿真參數(shù)設(shè)置如下：調(diào)制方式為64QAM，信道為快衰落瑞利信道，占用太赫茲頻段。系統(tǒng)利用大型天線陣列分組和控制技術(shù)，將超大規(guī)模天線陣列拆分成若干小組，每一小組天線規(guī)模為32×256。

圖3 首先對(duì)比了初始值為1的Newton 迭代算法與初始值為2的Newton 迭代算法的檢測(cè)誤差。初始值為1 則X0=αΙ，初始值為2 則X0=D-1。由圖3 可知，改進(jìn)初始值不僅可以使計(jì)算復(fù)雜度降低，還可以在一定程度上加快算法的收斂速度。另外，圖3 也對(duì)Newton 迭代算法與算法1 在2 種初始值情況下的收斂速度進(jìn)行了比較。從圖3 中可以明顯地看出，無(wú)論初始值如何選取，加入步長(zhǎng)因子都可以使收斂速度加快。

圖3 Newton 迭代算法與算法1 在2 種初始值的情況下收斂速度的比較

圖4 給出了本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、Newton 迭代算法、MMSE 檢測(cè)算法的誤比特率性能。從圖4 可以看出，文獻(xiàn)[14]算法需要8 次迭代才能逼近MMSE 算法的檢測(cè)性能，而算法1和算法2 分別需要3 次和4 次迭代即可接近MMSE算法。Newton 迭代算法需要4 次迭代即可逼近MMSE 算法，但其計(jì)算復(fù)雜度較高。總之，本文算法（算法1 和算法2）計(jì)算復(fù)雜度均小于Newton迭代算法，尤其是算法2的計(jì)算復(fù)雜度比Newton迭代算法小了一個(gè)數(shù)量級(jí)。

圖4 本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、Newton 迭代算法、MMSE 檢測(cè)算法的誤比特率性能

圖5 給出了本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、Newton 迭代算法、MMSE 檢測(cè)算法在天線規(guī)模為64×1 024 時(shí)的誤比特率性能曲線。從圖5 可以明顯看出，本文算法仍保持優(yōu)越性。

圖5 本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、Newton 迭代算法、MMSE 檢測(cè)算法在天線規(guī)模為64×1 024 時(shí)的誤比特率性能曲線

圖6 給出了本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、基于Neumann 級(jí)數(shù)展開(kāi)的算法、MMSE檢測(cè)算法在天線規(guī)模為32×256 時(shí)的誤比特率性能曲線。從圖6 可以看出，本文算法的收斂速度優(yōu)于基于Neumann 級(jí)數(shù)展開(kāi)的算法以及文獻(xiàn)[14]算法；在相同迭代次數(shù)下，本文算法誤碼率曲線遠(yuǎn)優(yōu)于基于Neumann 級(jí)數(shù)展開(kāi)的算法以及文獻(xiàn)[14]算法；在算法復(fù)雜度方面，本文算法遠(yuǎn)低于基于Neumann 級(jí)數(shù)展開(kāi)的算法。

圖6 本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、基于Neumann 級(jí)數(shù)展開(kāi)的算法、MMSE 檢測(cè)算法在天線規(guī)模為32×256 時(shí)的誤比特率性能曲線

圖7 給出了本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、基于Neumann 級(jí)數(shù)展開(kāi)的算法、MMSE檢測(cè)算法在天線規(guī)模為64×1 024 時(shí)的誤比特率性能曲線。從圖7 可以看出，本文算法仍保持了較好的檢測(cè)性能。

圖7 本文算法（算法1 和算法2）、文獻(xiàn)[14]算法、基于Neumann 級(jí)數(shù)展開(kāi)的算法、MMSE 檢測(cè)算法在天線規(guī)模為64×1 024 時(shí)的誤比特率性能曲線

5 結(jié)束語(yǔ)

為了解決6G 太赫茲頻段下超大規(guī)模MIMO 系統(tǒng)信號(hào)檢測(cè)復(fù)雜度高、收斂速度慢等問(wèn)題，本文基于Newton 迭代算法，提出了一種低復(fù)雜度的信號(hào)檢測(cè)算法。該算法通過(guò)改進(jìn)初始迭代矩陣，加入迭代步長(zhǎng)因子，加快了算法收斂速度；通過(guò)加入調(diào)節(jié)因子，提高了算法可靠性與穩(wěn)定性。對(duì)于數(shù)據(jù)量大、實(shí)時(shí)性要求不高的場(chǎng)景，可令調(diào)節(jié)因子θ=0，避免了迭代過(guò)程濾波矩陣A的計(jì)算，進(jìn)一步降低了計(jì)算復(fù)雜度，達(dá)到了O(K) 級(jí)別。仿真結(jié)果表明，相比目前廣泛應(yīng)用的Newton 迭代算法和基于Neumann 級(jí)數(shù)展開(kāi)的算法，本文算法擁有更快的收斂速度、更好的檢測(cè)性能和更低的算法復(fù)雜度；相比文獻(xiàn)[14]算法，本文算法擁有更快的收斂速度。