基于Newton 迭代算法的低復雜度信號檢測算法

劉剛，婁增進，林勤華，郭漪

（西安電子科技大學綜合業務網國家重點實驗室，陜西 西安 710071）

0 引言

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

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

本文在太赫茲場景下，提出了基于Newton 迭代的低復雜度信號檢測算法。通過改進迭代初值、加入步長因子、加入調節因子等操作，降低了算法的計算復雜度，加快了算法的收斂速度，保證了算法的穩定性。算法可工作在θ≠0 和θ=0 這2 種模式。當θ≠0 時，經歷3 次迭代即可達到MMSE 算法性能；當θ=0 時，需要4 次迭代才能達到MMSE算法性能，但是復雜度大大降低，尤其適于處理數據量大、實時性要求不高的場景。

1 理論基礎

1.1 系統模型

假設MIMO 系統包含N個接收天線、K個發射天線，N?K，系統模型如圖1 所示。

圖1 MIMO 系統模型

MIMO 系統接收信號可以表示為

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

對接收信號進行MMSE 檢測，可得

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

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

1.2 迭代算法基本思想

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

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

1.3 Newton 迭代算法

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

當滿足||I-AX0||＜1時，實現收斂。因為Newton迭代算法為二次收斂，所以它的計算復雜度僅取決于迭代次數。文獻[16]指出，Newton 迭代算法k次迭代的結果與基于Neumann 級數展開的算法中2k-1 次迭代的結果相同。因此，在相同的系統配置下，Newton 迭代算法要比其他的迭代算法具有更快的收斂速度。

2 低復雜度MIMO 檢測算法

本文基于Newton 迭代算法進行MIMO 檢測。通過改進初始矩陣來降低算法復雜度，提高了算法收斂速度；通過加入步長因子，大幅度提高了算法收斂速度，之后又通過加入調節因子保證了算法的穩定性和可靠性。基于Newton 迭代算法的低復雜度信號檢測（調節因子θ≠0）如算法1 所示。

算法1基于Newton 迭代算法的低復雜度信號檢測（調節因子θ≠0）

特別地，當調節因子θ=0 時，可對迭代公式進一步簡化，通過避免MMSE 矩陣計算進一步降低算法復雜度。基于Newton 迭代算法的低復雜度信號檢測（調節因子θ=0）如算法2 所示。

算法2基于Newton 迭代算法的低復雜度信號檢測（調節因子θ=0）

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

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

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

此時有

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

2.1 初始矩陣X0

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

其中，D是由A的主對角線元素構成的矩陣；-L是A的嚴格上三角部分；而H-L是-L共軛轉置后得到的，也就是A的嚴格下三角部分。

在迭代算法中，常用的矩陣求逆初值主要有2種，一種是Jacobi 算法的初始值X0=D-1，另一種是Richardson 算法的初始值X0=αI。當MIMO 系統發送和接收天線的數量都變為無窮大時，根據隨機矩陣理論，MMSE 檢測算法濾波矩陣的最大和最小特征值將保持穩定并各自收斂到

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

結合Jacobi 迭代檢測算法的迭代矩陣

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

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

由此可以計算JB的譜半徑為

同時，對于Richardson 算法來說，其所對應的迭代矩陣的形式為

最優松弛參數的值通常設置為

由式(18)和式(19)，并結合式(13)，可以將準最優松弛參數寫成

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

對式(17)和式(21)進行對比分析可得

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

由于Newton 迭代算法和其他迭代算法是正相關的，在迭代算法中，當初始矩陣為X0=αI時，比X0=D-1時收斂速度更快；相應地，在Newton迭代算法中，以X0=αI作為初始迭代矩陣也可以實現比以X0=D-1作為初始迭代矩陣時更快的收斂速度。因此，本文選取X0=αI作為改進算法的初值。

2.2 步長因子η

為了提升算法收斂速度，在初值改進基礎上，將步長因子η加入Newton 迭代公式中，從而得到

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

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

令對角矩陣表示為

則誤差矩陣為

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

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

這樣一來，對于ek的收斂性討論就可以轉變成針對Λk的研究。

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

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

2.3 調節因子θ

根據凸優化理論，如果步長過大，可能會錯過極值點，導致式(29)不成立。為了使算法更加穩定，在式(34)中加入調節因子θ，即

其中，θ與ξi,k的分布密切相關。

圖2 給出了X0=αI時不同θ值對步長的影響。從圖2 中可以看出，迭代初始階段，θ越大，步長越大，尤其當θ接近1.0 時，很容易出現不收斂的情況。綜上，這里設置θ=0.8，既保證了算法的穩定性，又加速了算法收斂。

圖2 X0=αI 時不同θ 值對步長的影響

3 算法復雜度分析

3.1 初始化部分計算復雜度

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

表1 本文算法與Newton 迭代算法初始化部分計算復雜度比較

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

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

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

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

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

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

3.2 迭代過程計算復雜度

表2 為本文算法與Newton 迭代算法迭代過程復雜度比較。

表2 本文算法與Newton 迭代算法迭代過程復雜度比較

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

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

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

3.3 算法整體過程復雜度

本文算法（算法1 和算法2）、Newton 迭代算法、基于Neumann 級數展開的算法、文獻[14]算法的總復雜度比較如表3 所示。

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

本文以32×256 MIMO 系統為例，本文算法（算法1 和算法2）以及Newton 迭代算法所需要的初始化部分的計算復雜度分別為257K、259K、256K2+257K。為了逼近MMSE 算法性能，三者迭代次數依次設為3次、4 次、4 次，迭代過程中的計算復雜度依次為 1798K2+1795K、7 936NK、3840K2+3840K，故總的計算復雜度依次為1795K2+2 052K、8195K、4 096K2+4 097K。基于Neumann級數展開的算法至少需要7次迭代才能接近MMSE 算法的性能，但此時計算復雜度就已經達到了 5K3+256K2+256K，復雜度達到了O(K3)的級別。文獻[14]算法需要8 次迭代才能接近MMSE 算法性能，所需計算復雜度為2 048K。可以看出，算法2 相比算法1 以及Newton 迭代算法，在復雜度上降低了一個數量級，只有O(K)級別，與文獻[14]算法屬于同一個數量級。算法1 因為初值的改進以及收斂速度的提升，相比Newton 迭代算法復雜度降低很多，但因為加入了步長因子，無法像算法2 那樣將濾波矩陣A進行分解，并充分利用不同迭代次數間的遞推規律求解第k次迭代的結果，相比算法2 仍具有較高的復雜度，但卻有更快的收斂速度。故本文算法可分別用于不同需求的場景。

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

4 仿真分析

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

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

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

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

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

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

圖5 本文算法（算法1 和算法2）、文獻[14]算法、Newton 迭代算法、MMSE 檢測算法在天線規模為64×1 024 時的誤比特率性能曲線

圖6 給出了本文算法（算法1 和算法2）、文獻[14]算法、基于Neumann 級數展開的算法、MMSE檢測算法在天線規模為32×256 時的誤比特率性能曲線。從圖6 可以看出，本文算法的收斂速度優于基于Neumann 級數展開的算法以及文獻[14]算法；在相同迭代次數下，本文算法誤碼率曲線遠優于基于Neumann 級數展開的算法以及文獻[14]算法；在算法復雜度方面，本文算法遠低于基于Neumann 級數展開的算法。

圖6 本文算法（算法1 和算法2）、文獻[14]算法、基于Neumann 級數展開的算法、MMSE 檢測算法在天線規模為32×256 時的誤比特率性能曲線

圖7 給出了本文算法（算法1 和算法2）、文獻[14]算法、基于Neumann 級數展開的算法、MMSE檢測算法在天線規模為64×1 024 時的誤比特率性能曲線。從圖7 可以看出，本文算法仍保持了較好的檢測性能。

圖7 本文算法（算法1 和算法2）、文獻[14]算法、基于Neumann 級數展開的算法、MMSE 檢測算法在天線規模為64×1 024 時的誤比特率性能曲線

5 結束語

為了解決6G 太赫茲頻段下超大規模MIMO 系統信號檢測復雜度高、收斂速度慢等問題，本文基于Newton 迭代算法，提出了一種低復雜度的信號檢測算法。該算法通過改進初始迭代矩陣，加入迭代步長因子，加快了算法收斂速度；通過加入調節因子，提高了算法可靠性與穩定性。對于數據量大、實時性要求不高的場景，可令調節因子θ=0，避免了迭代過程濾波矩陣A的計算，進一步降低了計算復雜度，達到了O(K) 級別。仿真結果表明，相比目前廣泛應用的Newton 迭代算法和基于Neumann 級數展開的算法，本文算法擁有更快的收斂速度、更好的檢測性能和更低的算法復雜度；相比文獻[14]算法，本文算法擁有更快的收斂速度。