基追蹤（basis pursuit）算法是一種用來求解未知參量L1范數(shù)最小化的等式約束問題的算法。

　　基追蹤是通常在信號(hào)處理中使用的一種對(duì)已知系數(shù)稀疏化的手段。將優(yōu)化問題中的L0范數(shù)轉(zhuǎn)化為L1范數(shù)的求解就是基追蹤的基本思想。

　　比如我原先有一個(gè)優(yōu)化問題：

　　min ||x||_0（就是L0范數(shù)的最小值）subject to y=Ax。

　　這個(gè)||x||_0，就是表示x中有多少個(gè)非零元素；那么我們要求min ||x||_0，就是想知道含有最多0元素的那個(gè)解x是什么。

　　但是呢，L0范數(shù)有非凸性，不怎么好求解，這時(shí)我們就轉(zhuǎn)而求解L1范數(shù)的優(yōu)化問題。

　　那么，基追蹤算法就是轉(zhuǎn)而求解

　　min||x||_1（就是L1范數(shù)的最小值）subject to||y-Ax||_2=0（2范數(shù)）

　　這個(gè)||x||_1，就是x的絕對(duì)值；那么我們要求min||x||_1，就是求絕對(duì)值最小的那個(gè)解x是什么。

　　更通俗一點(diǎn)來講，比如我要求一個(gè)線性方程組

　　Ax=b

　　x就是我們要求的未知量。這個(gè)A矩陣不是個(gè)方陣，是個(gè)欠定矩陣，那么就導(dǎo)致這個(gè)線性方程組會(huì)有若干組解。那么我們到底要哪組解好呢？

　　如果在一般情況下，可以直接用最小二乘法來獲得一組最小二乘解，就是x=（A‘A）^（-1）A’b。但是我們現(xiàn)在利用基追蹤，就是想要來獲得一組含0元素最多的解。

        提出了一種新的基追蹤求解算法。依據(jù)信號(hào)特性自適應(yīng)地選取字典；通過l1范數(shù)的近似表示，將有約束的極值問題轉(zhuǎn)化為無約束問題，并利用一種新的迭代算法進(jìn)行快速求解；幾類典型信號(hào)實(shí)驗(yàn)結(jié)果驗(yàn)證了本方法具有良好的去噪效果。 關(guān)鍵詞：基追蹤 字典 去噪 基追蹤方法是信號(hào)稀疏表示領(lǐng)域的一種新方法。它尋求從完備的（過完備）函數(shù)（基）集合中得到信號(hào)的最稀疏的表示，即用盡可能少的基精確地表示原信號(hào)，從而獲得信號(hào)的內(nèi)在本質(zhì)特性?；粉櫡椒ú捎帽硎鞠到y(tǒng)的范數(shù)作為信號(hào)稀疏性的度量，通過最小化l1范數(shù)將信號(hào)稀疏表示問題定義為一類有約束的極值問題，進(jìn)而轉(zhuǎn)化為線性規(guī)劃問題進(jìn)行求解。 目前，基追蹤方法在一維信號(hào)處理領(lǐng)域有很好的應(yīng)用。

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

       對(duì)于觀測(cè)到的離散信號(hào)s∈H，H為Hilbert空間，給定H中的字典φ={φγ，γ∈Γ}，其中Γ為指標(biāo)集，φγ為H中的基函數(shù)，也稱為原子?；粉櫡椒▽⑿盘?hào)稀疏表示問題定義為以下有結(jié)束的極值問題，即

　　其中，αγ（γ∈Γ）為表示系數(shù)。如果將字典中的向量表示成矩陣φ的例，系數(shù)表示成一個(gè)列向量，則（1）式可表示成 min||α||1 subject to s=φα （2） 在含噪觀測(cè)的情況下，考慮如下模型： y=s+σz 其中s為真實(shí)信號(hào)，y為觀測(cè)信號(hào)，z為標(biāo)準(zhǔn)高斯白噪聲，σ為噪聲根方差?；粉櫡椒ㄈピ霘w結(jié)為求解以下優(yōu)化問題：

　　以上最優(yōu)化問題致力于最小化信號(hào)重建誤差，同時(shí)使得信號(hào)的表示最稀疏。正則化參數(shù)λ控制著允許誤差與稀疏性之間的平衡。 由（3）式可見，基追蹤方法去噪的核心問題涉及到原子的選取、字典的構(gòu)造、求解算法設(shè)計(jì)等三個(gè)方面。其中，字典的構(gòu)造是基追蹤方法的重要環(huán)節(jié)。為了盡可能精確地表示信號(hào)，字典與信號(hào)應(yīng)用是自適應(yīng)的，或者說字節(jié)是從信號(hào)的學(xué)習(xí)中得到的。通常，基追蹤方法所使用的字典有完備的、過完備的、欠完備的等?？梢愿鶕?jù)信號(hào)的先驗(yàn)信息及實(shí)際需要設(shè)計(jì)字典。一般設(shè)計(jì)的字典是完備或過完備的。對(duì)于簡單信號(hào)去噪，一般只需要構(gòu)造完備的字典。對(duì)于復(fù)合信號(hào)對(duì)噪問題，通常需要構(gòu)造過完備的字典。對(duì)于完備字典，同樣存在信號(hào)的稀疏表示問題，因?yàn)樵肼暱偸翘幪幤娈惖摹１疚乃捎玫淖值渲饕校?（1）Heaviside字典

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

　　Heaviside字典具有上三角形式，結(jié)構(gòu)簡單，善于捕捉分片常數(shù)信號(hào)中的突變特征。 （2）時(shí)間-尺度字典（小波字典） 以Haar小波字典為例： 你小波基：ψ=l［0，1］，母小波基：ψ=1［1/2，1］，1-1［0，1/2］ Haar小波字典中包含小波基的平移和伸縮變換以及小波基的平移變換。 設(shè)ψ=（a，b，v），其中α∈（0，∞）為尺度變量，b∈［0，n］表征位置，v∈{0，1}表征性別。Haar小波字典形式為：

　　包含n個(gè)原子，構(gòu)成一組正交基。當(dāng)然還有其它類型的小波字典，盡管有些小波基沒有類似Haar小波基這樣明確的小波函數(shù)表達(dá)式，但它們的字典都有與Haar小波字典類似的離散結(jié)構(gòu)。比較常用的主要用Daubechies、Coiflet、Symmlet等。小波字典應(yīng)用于表示分片光滑信號(hào)。 （3）Heaviside字典+小波字典 對(duì)于比較復(fù)雜的復(fù)合信號(hào)，單一的字典下無法得到信號(hào)的最稀疏表示，此時(shí)可將幾種字典合成，從而得到過完備的字典。例如Heaviside字典+小波字典。