OMP算法對稀疏信號準(zhǔn)確重構(gòu)的一個充分條件

莫長鑫，畢 寧

(1.復(fù)旦大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，上海 200433; 2.中山大學(xué) 數(shù)學(xué)學(xué)院，廣東 廣州 510275)

客觀世界中存在著大量的所謂稀疏(或可稀疏化)信號,比如： 腦信號[1]、fMRI信號[2]等.因此，對稀疏(或可稀疏化)信號的表示長期以來都是信號分析領(lǐng)域研究的熱點.2006年,Donoho[3],Candes等[4]引入壓縮感知(Compressed Sensing, CS)概念,對稀疏信號給出了嚴(yán)格的數(shù)學(xué)定義,并引起數(shù)學(xué)界的廣泛重視.CS作為一種新的采樣理論，它能以遠(yuǎn)低于Nyquist采樣頻率對信號進(jìn)行采樣.隨著科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)的樣本越來越龐大，如何高效地處理這些數(shù)據(jù)并從中獲取關(guān)鍵信息以及最大限度的節(jié)約存儲和傳輸?shù)某杀境蔀榱艘淮箅y題.CS理論的出現(xiàn)為解決這個難題提供了一個好的方法并得到了不少好的結(jié)果，應(yīng)用甚是廣泛.

在CS中，我們經(jīng)?？紤]以下模型：

y=Ax+n，

(1)

y=Ax，

(2)

此時我們稱其為不帶噪聲的情形.式(1)的模型稱為帶噪聲的情形.

在CS中,我們的目標(biāo)之一是希望在知道觀測矩陣A和觀測信號y的前提下來重構(gòu)稀疏信號x,那么A滿足什么樣的條件我們才能對稀疏信號x準(zhǔn)確地重構(gòu)呢？到目前為止,CS中用于觀測矩陣的條件有零空間性質(zhì)(Null Space Property, NSP)[5],相干性(Coherence)[6-8]等,而最常用的性質(zhì)是由Candes等給出的受限等距性質(zhì)(Restricted Isometry Property, RIP)[9-10].下面我們給出RIP的定義.

定義1[10]設(shè)A是一個m×N的矩陣,1≤k≤N是一個給定的整數(shù).假設(shè)存在一個常數(shù)δ∈(0,1)使得

(3)

對所有k-稀疏向量x∈RN均成立，則我們稱矩陣A滿足k階受限等距性質(zhì).

現(xiàn)在有很多種重構(gòu)信號x的算法,比如說貪婪算法[11-13]、迭代硬閾值算法[14]、加權(quán)迭代算法[15]等,在這些算法中正交匹配追蹤(Orthogonal Matching Pursuit, OMP)算法[16]是用的最廣泛的貪婪算法之一.OMP算法的本質(zhì)思想是選擇A的列,使得在每次迭代中所選擇的列與當(dāng)前的冗余向量相關(guān)程度最大，然后從測量向量中減去相關(guān)部分并反復(fù)迭代,直到迭代次數(shù)達(dá)到稀疏度k后迭代強制停止.

首先我們給出幾個重要的引理.

引理1[18]令向量u,v∈RN，并且|supp(u)|≤s以及|supp(v)|≤t.若有supp(u)∩supp(v)=?，則

(4)

引理2假設(shè)觀測矩陣A∈Rm×N滿足k-階RIP條件并且δk<1，x∈RN的支撐集為Ω，即supp(x)=Ω，并且|Ω|=k,則我們有

(5)

以及

(6)

證 一方面，利用RIP條件及Cauchy-Schwarz不等式，我們有

(7)

另一方面，又因為

(8)

對所有的i?Ω都成立，結(jié)合引理1，則式(6)得證.

由式(5)和(6)可以得到本文中的一個重要引理.

(9)

則我們有

(10)

證 要使得式(10)成立，則由式(5)和(6)可知，必須要有下式成立：

經(jīng)過化簡我們可得

根據(jù)式(9)的假設(shè)，引理得證.

在給出主要定理之前，我們先給出OMP算法的核心步驟：

輸入： 觀測矩陣A,向量y,稀疏度k

輸出： 重構(gòu)的信號x*

初始值： 殘差r0=y,索引集Λ0=?,x0=0,t=1

Whilet≤k

步驟1 初始定義r0=y,Ω0=?;

步驟4 如果rt=0，則停止并輸出;如果rt≠0，令t=t+1，回到步驟2,繼續(xù)迭代;

end While

(11)

即

這樣有Ω1?Ω，并且

即有

故有Ωt+1=Ωt∪{kt+1}?Ω.又由于

從而不難得到

即有〈rt,Aei〉=0,?i∈Ωt.這意味著kt+1?Ωt，即OMP算法在每一步迭代中都在Ω中選取不同的指標(biāo).綜上所述，則至多k步就可將k-稀疏向量x準(zhǔn)確重構(gòu).

文獻(xiàn)[19]對帶噪聲的情形做了研究.下面我們給出文獻(xiàn)[19]的相應(yīng)結(jié)果和與本文結(jié)果相比較的一個例子，在給出例子之前我們先給出文獻(xiàn)[19]中的相關(guān)結(jié)果.

(12)

下面我們對定理1中的結(jié)果和定理2中的結(jié)果做出比較.根據(jù)注1，我們可以知道，定理1中的RIC的條件要比定理2中的弱一些.對式(12)作出變形，我們可以得到

下面我們通過一個例子探討M1和M2的關(guān)系.

例1對于觀測矩陣A，假設(shè)其滿足RIP并且RIC滿足定理2中的要求(則RIC一定滿足定理1中的要求)，假設(shè)向量x的稀疏度為4，即k=4，根據(jù)定理2中RIC條件可知有

若要使得M1>M2，則只需

注2由例1可知，定理1和定理2相比，不僅定理1中的RIC滿足的條件要比定理2中的弱一些，而且有例子可以表明定理1中對噪聲強度的要求也要比定理2中的弱一些.