基于互相關運算的信號稀疏分解算法研究

姚建峰 郭旭展

摘要：分析了MP算法實現過程，并針對MP算法計算量大等問題，提出了一種信號稀疏分解的快速算法，它利用一種基于互相關運算的信號稀疏分解算法。該算法用互相關運算來代替MP算法中耗時最多的內積運算，并通過提高互相關運算的速度，提高信號稀疏分解的速度。通過實驗表明，在保證稀疏分解精度的情況下，可以將信號稀疏分解速度提高到MP算法的10倍以上。

關鍵詞：稀疏分解;MP算法;互相關運算

中圖分類號：G642.0 ? ? 文獻標志碼：A ? ? 文章編號：1674-9324（2015）24-0183-02

對信號進行處理時，一般先要對信號進行分解或變換，傳統方法將信號在一組正交基上進行分解。正交基分解的不足之處是信號表示是唯一的，如果待分解信號的特征與正交基不完全相同時，分解后的信號就不能較稀疏地表示出原信號。用稀疏逼近取代原始信號可以降低信號處理的成本，提高壓縮效率。目前，信號稀疏表示主要使用的算法是Mallat等人提出的匹配跟蹤算法（Matching Pursuit，MP算法）。MP算法在計算復雜度和逼近效果方面要優于其他算法，但是MP算法每一步都要計算殘余信號在完備元子庫中每一個原子上的投影，因此計算量非常大。筆者在文中提出一種信號稀疏分解算法，該算法將MP算法中耗時最多的內積運算轉換成一次互相關運算，此外，通過提高互相關運算的速度來提高信號稀疏分解的速度，可以縮短信號分解的時間。

一、信號的表示

一組線性獨立的矢量φ={φ1}1∈T組成基，它能張開整個空間。任意一個在空間中的矢量S，可以通過線性組合來展開。

s在基矢量φ1上的展開系數是αi=〈s，φi〉。因為基具有獨立性，所以它是唯一的一種展開方式。如果φi⊥φj，i≠j，則基？鬃為空間S的一組正交基。式（1.1）可轉化成如下矩陣：

基矢量組成φ∈RM×N矩陣。如果N

信號也是采用一組矢量{ti} ? ?來進行表示的。給定信號f∈RN，通過基矢量{ti} ? ?的線性組合展開。f在基矢量ti上的展開系數是f=∑ ? ?αiti=Tα，αi=〈f，ti〉，T為合成矩陣。目前常用的基有余弦基、傅里葉基和小波基，這些基對應的合成矢量形成完備正交基。采用超完備的冗余基函數代替正交基函數來使表示形式多樣化。此時，基矢量ti組成一個超完備集{ti} ? ?，且N

給定f和D，式（1.3）是一個欠定問題，有無窮多個解α，因此信號的稀疏表示是可行的。

二、MP算法

MP算法通過迭代方式從超完備元子庫中選出與信號或者是殘余信號最匹配的原子，從而將信號表示為這些原子的線性組合，實現信號的稀疏分解。設D={gm}0≤m

由于g0與R1s正交，因此：

為了極小化||R1s||，即讓殘余能量最小化，必須選定原子g0，使|<g0，R0s>|最大化。

用同樣的方法，得到：

經過M次迭代后，信號s可以表示為：

其中RMs為M項近似殘差，并且滿足：

三、一種基于互相關的快速匹配算法

（一）算法思想

在信號稀疏表示中，一般使用Gabor原子庫。一個Gabor原子由尺度因子s、原子頻率v、原子相位w和位移因子u共同決定，且s、v、w三個參數決定原子形狀，u只是決定原子的中心位置。如果對超完備原子庫中的某一個原子gi（參數為si、vi、wi）的選取方法保持不變，信號長度為N，取u=N/2，通過平移就可以得到參數為（參數為si、vi、wi、ui）的原子（ui≠N/2）。為了不影響信號稀疏分解的效果，盡量使ui的值在區間[0，N-1]上。這相當擴大了元子庫中原子的數目。由于ui從0到N-1連續取值，所有的N次內積運算<Rks，gk>都可以轉化成兩個列向量Rks和gk的一次互相關運算。內積運算的過程實際上是找互相關運算最大值的過程。如果提高了互相關運算的速度，就提高了信號稀疏分解的速度。

（二）算法描述

對兩列長為N的數字信號，其互相關函數為：

兩列數字信號在互相關運算的結果附近存在著一個明顯的峰值特征，為了快速求出互相關運算的最大值，可以間隔一定距離進行互相關運算，確定最大值出現的區間，然后再在這個區間內進行相關運算，求出最大值和最大值點所在的位置。

假設每次間隔m個點進行計算，式3.1可表達為：

將得到的+1個點互相關運算的值進行比較，找出最大值（此最大值可能不是實際的最大值）。根據峰值特性，最大值點應在區間[m-1，m+1]上。如果N比較大，改進后互相關運算的計算量是原互相關運算的計算量的1/m。改進后互相關流程如圖1。

四、實驗結果與仿真

利用Matlab進行算法仿真，取不同長度的信號和步進點數進行互相關運算，求得的最大值與MP算法求得的內積最大值的誤差，算法速度與MP算法速度的比值。從實驗結果可以看出，當步進點數為2、4時，誤差很小，當步進點數大于或等于6時，誤差開始變大。因此，在實際運用中，步進點數不能太大，即使步進點數為1，互相關算法比MP算法的速度要快。

本文針對信號稀疏分解中計算量大、分解速度緩慢等問題，提出了一種信號稀疏分解的快速算法。它利用一種互相關的快速運算來代替稀疏分解中計算量巨大的內積運算，提高了運算速度。通過理論仿真和實驗表明，在保證稀疏精度的情況下，可以將信號稀疏分解的速度提高至普通MP算法速度的10倍以上。

參考文獻：

[1]張春梅，尹忠科，肖明霞.基于冗余字典的信號超完備表示與稀疏分解[J].科學通報，2006，（6）：628-633.

[2]何虹麗，嵇銀輝，等.基于差分進化算法的交通圖像稀疏分解[J].電子元器件應用，2011，（3）：35-37.

[3]余付平，馮有前，等.基于稀疏分解的雷達信號抗噪聲干擾方法研究[J].系統工程與電子技術，2011，（8）：1775-1769.