摘要：提出了一種新的基追蹤求解算法。依據(jù)信號特性自適應(yīng)地選取字典；通過l1范數(shù)的近似表示，將有約束的極值問題轉(zhuǎn)化為無約束問題，并利用一種新的迭代算法進(jìn)行快速求解；幾類典型信號實驗結(jié)果驗證了本方法具有良好的去噪效果。

        關(guān)鍵詞：基追蹤 字典 去噪

        基追蹤方法是信號稀疏表示領(lǐng)域的一種新方法。它尋求從完備的（過完備）函數(shù)（基）集合中得到信號的最稀疏的表示，即用盡可能少的基精確地表示原信號，從而獲得信號的內(nèi)在本質(zhì)特性�；粉櫡椒ú捎帽硎鞠到y(tǒng)的范數(shù)作為信號稀疏性的度量，通過最小化l1范數(shù)將信號稀疏表示問題定義為一類有約束的極值問題，進(jìn)而轉(zhuǎn)化為線性規(guī)劃問題進(jìn)行求解。

        目前，基追蹤方法在一維信號處理領(lǐng)域有很好的應(yīng)用。以David L.Donoho為代表的斯需求量福大學(xué)統(tǒng)計系工作組利用基追蹤方法在一維實信號去噪和超分辨方面取得取了很多很好的應(yīng)用結(jié)果。盡管使用了一種新的線性規(guī)劃算法——內(nèi)點算法，基追蹤方法由于要在所有的字典向量中極小化一個全局目標(biāo)函數(shù)，其計算量仍然是很大的。正因為求解大尺度線性規(guī)劃問題的困難，目前的基追蹤方法局限于一維的信號去噪和超分辨處理。本文提出一種新的思路來求解上述有約束的極值問題。首先依據(jù)信號特性自適應(yīng)地選取字典；通過l1范數(shù)的近似表示，將有約束的極值問題轉(zhuǎn)化為無約束問題，并利用一種迭代算法進(jìn)行快速求解；最后通過幾類典型信號去噪實驗來驗證本方法的應(yīng)用效果。實驗結(jié)果表明，改進(jìn)的基追蹤方法能夠快速穩(wěn)定實現(xiàn)，。同時具有良好的去噪效果。

1 字典的構(gòu)造

        對于觀測到的離散信號s∈H,H為Hilbert空間，給定H中的字典φ={φγ，γ∈Γ}，其中Γ為指標(biāo)集，φγ為H中的基函數(shù)，也稱為原子�；粉櫡椒▽⑿盘栂∈璞硎締栴}定義為以下有結(jié)束的極值問題，即

其中，αγ（γ∈Γ）為表示系數(shù)。如果將字典中的向量表示成矩陣φ的例，系數(shù)表示成一個列向量，則（1）式可表示成

min||α||1 subject to s=φα (2)

在含噪觀測的情況下，考慮如下模型：

y=s+σz

其中s為真實信號，y為觀測信號，z為標(biāo)準(zhǔn)高斯白噪聲，σ為噪聲根方差�；粉櫡椒ㄈピ霘w結(jié)為求解以下優(yōu)化問題：

        以上最優(yōu)化問題致力于最小化信號重建誤差，同時使得信號的表示最稀疏。正則化參數(shù)λ控制著允許誤差與稀疏性之間的平衡。

        由（3）式可見，基追蹤方法去噪的核心問題涉及到原子的選取、字典的構(gòu)造、求解算法設(shè)計等三個方面。其中，字典的構(gòu)造是基追蹤方法的重要環(huán)節(jié)。為了盡可能精確地表示信號，字典與信號應(yīng)用是自適應(yīng)的，或者說字節(jié)是從信號的學(xué)習(xí)中得到的。通常，基追蹤方法所使用的字典有完備的、過完備的、欠完備的等。可以根據(jù)信號的先驗信息及實際需要設(shè)計字典。一般設(shè)計的字典是完備或過完備的。對于簡單信號去噪，一般只需要構(gòu)造完備的字典。對于復(fù)合信號對噪問題，通常需要構(gòu)造過完備的字典。對于完備字典，同樣存在信號的稀疏表示問題，因為噪聲總是處處奇異的。本文所采用的字典主要有：

（1）Heaviside字典

此字典中原子不是正交的，但是對于任意長度為n的一維離散信號s=(s1s2…sn)都有以下表示：

        Heaviside字典具有上三角形式，結(jié)構(gòu)簡單，善于捕捉分片常數(shù)信號中的突變特征。

（2）時間-尺度字典（小波字典）

以Haar小波字典為例：

你小波基：ψ=l[0,1],母小波基：ψ=1[1/2,1],1-1[0,1/2]

Haar小波字典中包含小波基的