超寬頻信號的快速匹配追蹤演算法
摘要：壓縮感知理論可應用到脈衝超寬頻通信中，以降低採樣速率。超寬頻信號常常採用多徑分集字典來稀疏表示，使得壓縮採樣匹配追蹤（CoSaMP）、廣義正交匹配追蹤（GOMP）等經典的重構演算法經常出現原子誤選的情況，導致信號重構誤差增大。因此，在GOMP的基礎上，提出了一種新的重構演算法。該演算法在每次迭代中可選取多個原子以加快迭代收斂速度，並且通過限制被選中原子之間的序號差來避免原子誤選。模擬實驗表明，該演算法不僅可以保證重構精度，而且具有更低的計算複雜度。
0 引言
傳統採樣定理要求採樣頻率是信號帶寬的2倍以上，從而保證採樣所得信號不失真。因此，在處理超寬頻信號時，就會面臨許多困難。壓縮感知（Compressive Sensing，CS）[1]是一種新的稀疏信號採樣和重建理論。該理論中，信號採樣和壓縮能同時完成，使得系統能夠低於奈奎斯特採樣頻率採樣，降低了系統的數據採樣和儲存成本，適合應用於超寬頻通信系統。
Jose[2]是最早研究壓縮感知應用於超寬頻的學者之一。文獻[2]中提到了兩種超寬頻稀疏信號的表示方式，一種用時域稀疏字典來表示，即單位矩陣，一種用多徑分集字典來表示，能夠更加稀疏地表示超寬頻信號，因此被更多採用。但是，多徑分集字典由超寬頻脈衝波形位移產生，相鄰原子之間的相關性較高，在使用匹配追蹤演算法時，會對原子的正確選擇造成一定干擾。壓縮採樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）[3]演算法、稀疏度自適應匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）[4]演算法和正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）[5]演算法，每次迭代都會選取多個原子，使得選取相鄰原子的可能性加大而產生誤選。廣義正交匹配追蹤（Generalized Orthogonal Matching Pursuit，GOMP）[6]每次迭代選擇L 個原子，L 被稱為迭代步長。L 越大，GOMP發生原子誤選的可能性越高。正交匹配追蹤（Orthogonal Matching Pursuit，OMP）演算法[7]由於每次迭代只選擇一個原子，所以重構精度沒有明顯降低。但是，OMP的迭代次數過多，需要大量計算時間，所以L 在一定範圍內時，GOMP更加適合應用於超寬頻通信。
本文在GOMP演算法的基礎上，針對超寬頻信號稀疏表示的特點做出改進，儘可能避免一定區間範圍內同時選擇多個原子。模擬實驗表明，本文演算法能夠在運算時間接近GOMP的情況下，獲得更高的重構精度。而相對於OMP而言，本文演算法能在保證重構精度的同時，有效節省運算時間。
1 壓縮感知理論
壓縮感知理論指出：假設信號在nxn 維的稀疏字典下可以被稀疏表示，稀疏度k＜n ，通過mxn 維的測量矩陣隨機採樣後得到m(k＜m＜n) 維的觀測向量y 為：
其中稱作感測矩陣，向量a 是信號x 在稀疏字典下的稀疏表示。由於m＜n ，通過觀測向量y 和測量矩陣無法直接求信號x ，所以將其轉化成如下最優化問題：
其中，表示a 的l0 範數。式（2）中的優化問題是一個NP-Hard問題，通常在感測矩陣滿足約束等距性質（Restricted Isometry Property，RIP）[8]的條件下，將式（2）中l0 範數優化問題轉化為如式（3）所示的l1 範數優化問題：
通過相關重構演算法，如OMP演算法、基追蹤（Basis Pursuit，BP）演算法[9]和迭代硬閾值（Iterative Hard Thresholding，IHT）演算法[10]等，就可以利用已知的觀測向量y 和感測矩陣求得稀疏表示向量a ，再進而求出信號x 。
2 超寬頻信號的快速匹配追蹤演算法
2.1 演算法分析
首先介紹多徑分集字典。脈衝超寬頻信號經過多條不同時延和衰落的路徑到達接收機，接收信號就由這些分量組合而成。稀疏字典的設計應該儘可能考慮和利用被稀疏表示信號的結構與特徵。所以，文獻[2]提出了一種稀疏表示基，即：
其中，p(t) 表示超寬頻發射脈衝波形，表示理論上的採樣時間間隔。若N 表示一次觀測的總採樣點數，則一次觀測的總時長為。接收信號在此稀疏字典下可表示為：
其中，K 既代表信號多徑的數目，也代表信號x 的稀疏度， 為各個多徑分量的幅值。超寬頻信號佔用的帶寬極寬，具有高多徑解析度，可認為多徑分量重疊的概率很小，且只有一小部分的多徑分量幅值較大。因此，超寬頻信號在該稀疏字典下可以被稀疏表示，且相對於時域稀疏字典，這種表示方法的結果更加稀疏。
目前，關於壓縮感知應用於超寬頻的研究中，大多數採用了多徑分集字典作為稀疏矩陣。因為多徑分集字典相比於時域稀疏字典，更能充分利用脈衝超寬頻信號的稀疏性。使用時域稀疏字典時，無論採用何種重構演算法，重構精度都比較低。因此，實際應用中採用時域稀疏字典是不可行的。
然而，在使用多徑分集字典時，CoSaMP、SAMP、ROMP均出現了較大誤差，原因是多徑分集字典的相鄰原子相關性很高，匹配追蹤類演算法採用內積的絕對值大小作為原子篩選的標準。正確原子相鄰的位置的內積絕對值往往也較大，若一次迭代中選擇很多原子，那麼在匹配追蹤的原子篩選過程中容易選擇正確原子的相鄰原子，從而產生誤選。
文章第3節的圖1可以看出，隨著GOMP迭代步長的增大，重構精度明顯下降。但是，當字典為單位矩陣時，迭代步長的增大並不會造成重構精度明顯下降[6]。由此可以證明，多徑分集字典對迭代步長較大的匹配追蹤演算法會有一定影響，問題的根本原因是正確原子的相鄰原子與殘差的內積值較大，致使其容易在同一次迭代中被選中。解決這一問題的辦法是在匹配原子的過程中盡量避免同一次迭代選中相鄰原子。基於這樣的目的，本文提出了一種演算法，使得同一次迭代所選原子保持一定距離。若只選擇正確的原子，再經過正交化處理，那麼下一次迭代中殘差與其相鄰原子的內積值會明顯減小，從而可以有效降低誤選的可能性。
此外，本文演算法將GOMP的迭代停止條件改為或者滿足t＞K ，其中t 代表迭代次數的序號，rt 代表第t 次迭代後的殘差，K 是允許的最大迭代次數，為常數。也就是說，當殘差的相對變化率小於一定數值時，認為匹配追蹤已經完成。該條件增強了演算法的自適應性，在信號稀疏度不明確的條件下也能使用該演算法。
2.2 演算法步驟
GOMP的計算複雜度比OMP低，在步長L 不大時，其重構精度甚至略微優於OMP，所以顯然更適合應用在超寬頻的高速通信中。本文在GOMP的基礎上，針對演算法的不足作出改進，使得在演算法複雜度沒有明顯提高的前提下提高重構精度，使演算法更具有應用價值。
下面是本文提出演算法的具體步驟：
輸入：感知矩陣，觀測向量y ，每次迭代選取的原子個數L ，最大迭代次數K ；
（1）初始化：殘差r0=y ，已選原子索引集合，已選原子集合，迭代次數t=1 ；
（2）計算， 表示中各原子（列向量）的序號和u 中各元素的序號；
（3）按照向量u 各元素的值從大到小依次選擇對應序號的原子。在此過程中，若某原子與任意已被選中原子的序號之差的絕對值小於S ，則該原子被捨棄，直到L 個原子被選中，再進行下一步；
（4）將這L 個原子對應的序號構成集合J ，代表第j 個原子；
（5）利用最小二乘法計算被選原子對應的係數；
（6）更新殘差 ；
（7）t=t+1 ，如果或者滿足t＞K ，則進行下一步；否則返回第2步繼續迭代；
（8）根據被選原子的係數at 和稀疏矩陣，可以得到原始信號；
輸出：原始信號x 。
3 模擬與分析
本文通過模擬實驗驗證演算法的性能。選取原始信號為IEEE802.15.3a CM1模型下1024x1 的脈衝超寬頻多徑信號，測量矩陣為Mx1024 的高斯隨機矩陣，M 為觀測點數，本文演算法中 S的取值為3，取值為0.1。參照文獻[2]中的評價標準：若重構誤差小於原始信號能量的1%，即，則認為信號被成功重構。本文採用信號重構成功的概率作為重構精度的衡量指標。模擬環境為Intel i5-5200U CPU，8G RAM，Windows 10 64位操作系統，採用Matlab 2016b模擬。
圖1和圖2分別表示迭代步長L 從1變化到15過程中，GOMP演算法和本文演算法運行時間和重構精度的對比，其中稀疏字典都採用多徑分集稀疏字典。由圖1和圖2可得以下結論：（1）本文演算法與GOMP演算法的計算複雜度相近，迭代次數是影響整體計算複雜度的最主要因素。相比OMP演算法（即GOMP演算法L=1 時），GOMP和本文演算法在計算複雜度上有明顯優勢。（2）當隨機採樣點數為256時，本文演算法在迭代步長L=4 時成功重構信號的概率最大，GOMP演算法在L=3 時成功重構的概率最大。相比於OMP演算法和GOMP演算法，本文演算法在重構精度和計算複雜度兩個方面都有一定優勢。（3）當迭代步長過大時，GOMP和本文演算法的重構精度都會下降，但顯然本文演算法受到的影響更小，所以同等精度要求下，本文演算法可以選擇更大的迭代步長。
表1為觀測點數M 不同的情況下，不同重構演算法成功重構原始信號的概率。分別檢測OMP演算法、GOMP演算法（L=3 、L=6 ）以及本文演算法（L=3 、L=6 ）在稀疏字典為多徑分集字典的情況下成功重構的概率。各種情況均重複10 000次，最後得到如表1所示的統計結果。從表1的數據中可以看出，當要求重構成功概率為1時，OMP和本文演算法（L=3 ）所需的觀測點數M 最少，但本文演算法運行時間約是OMP的1/3。GOMP需要的觀測點數最多，不利於降低採樣率，也增加了重構所需的時間，說明本文演算法相比OMP和GOMP具有更佳的性能。在實際應用中，可以根據需求選擇合適的步長，從而在滿足採樣率和重構精度要求的前提下節省演算法的運行時間。
4 結語
本文介紹了用於稀疏表示超寬頻信號的多徑分集字典，分析了CoSaMP、GOMP等演算法出現原子誤選的原因，並針對OMP和GOMP兩種演算法在超寬頻應用中的不足作出改進，限制被選原子之間的序號差，減少原子誤選的發生，彌補多徑分集字典的不足，從而選擇更大的迭代步長。模擬實驗證明，該演算法在運行時間和重構精度兩個方面都獲得了一定改善。
參考文獻：
[1] Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2012,52(04):1289-1306.
[2] Paredes J L,Arce G R,Wang Z.Ultra-Wideband Compressed Sensing:Channel Estimation[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(03):383-395.
[3] Needell D,Tropp J A.CoSaMP:Iterative Signal Recovery from Incomplete and Inaccurate Samples[J].Applied & Computational Harmonic Analysis,2008,26(03):301-321.
[4] Do T T,Lu G,Nguyen N,et al.Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing[C].Signals,Systems and Computers,2009:581-587.
[5] Needell D,Vershynin R.Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit[J].Foundations of Computational Mathematics,2009,9(03):317-334.
[6] Jian W,Kwon S,Shim B.Generalized Orthogonal Matching Pursuit[J].IEEE Transactions on Signal Processing,2012,60(12):6202-6216.
[7] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal Matching Pursuit:Recursive Function Approximation with Applications to Wavelet Decomposition[C].Signals,Systems and Computers,2002:40-44.
[8]Donoho D L,Huo X.Uncertainty Principles and Ideal Atomic Decomposition[J].IEEE Transactions on Information Theory,2002,47(07):2845-2862.
[9] Chen S S,Donoho D L,Saunders M A.Atomic Decomposition by Basis Pursuit[J].Siam Review,2001,43(01):129-159.
[10] Donoho D L,Tsaig Y,Drori I,et al.Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory,2012,58(02):1094-1121.
作者簡介：
沈子鈺，杭州電子科技大學 通信工程學院碩士，主要研究方向為壓縮感知；
褚杭柯，杭州電子科技大學 通信工程學院碩士，主要研究方向為無線通信；
唐川雁，杭州電子科技大學 通信工程學院碩士，主要研究方向為信號處理。
（本文選自《通信技術》2018年第五期）
原創聲明 >>>
本微信公眾號刊載的原創文章，歡迎個人轉發。未經授權，其他媒體、微信公眾號和網站不得轉載。
