基于互相關(guān)運(yùn)算的信號稀疏分解算法研究

姚建峰 郭旭展

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

關(guān)鍵詞：稀疏分解;MP算法;互相關(guān)運(yùn)算

中圖分類號：G642.0 ? ? 文獻(xiàn)標(biāo)志碼：A ? ? 文章編號：1674-9324（2015）24-0183-02

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

一、信號的表示

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

s在基矢量φ1上的展開系數(shù)是αi=〈s，φi〉。因?yàn)榛哂歇?dú)立性，所以它是唯一的一種展開方式。如果φi⊥φj，i≠j，則基？鬃為空間S的一組正交基。式（1.1）可轉(zhuǎn)化成如下矩陣：

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

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

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

二、MP算法

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

由于g0與R1s正交，因此：

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

用同樣的方法，得到：

經(jīng)過M次迭代后，信號s可以表示為：

其中RMs為M項(xiàng)近似殘差，并且滿足：

三、一種基于互相關(guān)的快速匹配算法

（一）算法思想

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

（二）算法描述

對兩列長為N的數(shù)字信號，其互相關(guān)函數(shù)為：

兩列數(shù)字信號在互相關(guān)運(yùn)算的結(jié)果附近存在著一個(gè)明顯的峰值特征，為了快速求出互相關(guān)運(yùn)算的最大值，可以間隔一定距離進(jìn)行互相關(guān)運(yùn)算，確定最大值出現(xiàn)的區(qū)間，然后再在這個(gè)區(qū)間內(nèi)進(jìn)行相關(guān)運(yùn)算，求出最大值和最大值點(diǎn)所在的位置。

假設(shè)每次間隔m個(gè)點(diǎn)進(jìn)行計(jì)算，式3.1可表達(dá)為：

將得到的+1個(gè)點(diǎn)互相關(guān)運(yùn)算的值進(jìn)行比較，找出最大值（此最大值可能不是實(shí)際的最大值）。根據(jù)峰值特性，最大值點(diǎn)應(yīng)在區(qū)間[m-1，m+1]上。如果N比較大，改進(jìn)后互相關(guān)運(yùn)算的計(jì)算量是原互相關(guān)運(yùn)算的計(jì)算量的1/m。改進(jìn)后互相關(guān)流程如圖1。

四、實(shí)驗(yàn)結(jié)果與仿真

利用Matlab進(jìn)行算法仿真，取不同長度的信號和步進(jìn)點(diǎn)數(shù)進(jìn)行互相關(guān)運(yùn)算，求得的最大值與MP算法求得的內(nèi)積最大值的誤差，算法速度與MP算法速度的比值。從實(shí)驗(yàn)結(jié)果可以看出，當(dāng)步進(jìn)點(diǎn)數(shù)為2、4時(shí)，誤差很小，當(dāng)步進(jìn)點(diǎn)數(shù)大于或等于6時(shí)，誤差開始變大。因此，在實(shí)際運(yùn)用中，步進(jìn)點(diǎn)數(shù)不能太大，即使步進(jìn)點(diǎn)數(shù)為1，互相關(guān)算法比MP算法的速度要快。

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

參考文獻(xiàn)：

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

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

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