主要參考資料為Michael Elad的PPT和From Mars to Hollywood with a stop at the hospital課程中p064開始的幾個(gè)Video。
基本概念
從對(duì)壓縮感知的初步了解，可以認(rèn)識(shí)到，很多信號(hào)是可以稀疏表達(dá)的，至少在某個(gè)基下面具有這樣的性質(zhì)。這就是稀疏表達(dá)的出發(fā)點(diǎn)，一個(gè)信號(hào)可以看做幾個(gè)主要基信號(hào)（也就是字典）的線性組合。如果從信號(hào)的稀疏性出發(fā)，事實(shí)上給了我們關(guān)于信號(hào)的一個(gè)先驗(yàn)知識(shí)，這一點(diǎn)將用來(lái)約束我們對(duì)問(wèn)題的描述。
對(duì)于我們的信號(hào)x，我們可以將其看做字典D和一個(gè)向量a的積。其中信號(hào)x有N個(gè)element，a為K個(gè)維度，D則是NxK維度。因?yàn)?em>a中只有少數(shù)幾個(gè)點(diǎn)不為零（圖中的紅點(diǎn)），D乘以a就相當(dāng)于，從D中選取對(duì)應(yīng)的那幾個(gè)列向量進(jìn)行線性組合，從而得到X。所以D中的每一列都叫做atom，相當(dāng)于字典里的詞條。
稀疏表達(dá)的一個(gè)作用就是找出信號(hào)中最重要的元素，而忽略其他不必要的噪聲。比如一張含有噪聲的圖像，因?yàn)樵肼暿菬o(wú)法很好的fit到字典的atom中的，所以利用稀疏表達(dá)進(jìn)行圖像重建以后就可以有效的去除這些噪聲。
求解算法
下面的算法作為了解即可，并不需要掌握其實(shí)現(xiàn)過(guò)程，因?yàn)椴还苁荕ATLAB還是Python都提供了這些工具包。
Basis Pursuit（BP）算法
我們的目標(biāo)是找到字典D和a，并且a非常的稀疏，并且根據(jù)稀疏表達(dá)復(fù)原的信號(hào)應(yīng)該和原始信號(hào)盡量的接近。如果用數(shù)學(xué)公式表示出來(lái)的話，如下圖左上所示。正如我們?cè)趬嚎s感知一文中指出，解L0太復(fù)雜了，所以這里采用了L1進(jìn)行近似（下圖右上所示）。對(duì)于BP算法，了解到這里就OK了。
Matching Pursuit（MP）算法
Matching Pursuit（MP）算法提供了另外一種解決方案。
- 找到字典中最重要的atom，也就是最接近信號(hào)的atom。
- 找到字典中第二個(gè)atom，使第一個(gè)，第二個(gè)atom組合的結(jié)果更加接近信號(hào)。
- 當(dāng)組合的error小到一定程度的時(shí)候，停止。
（Orthogonal MP）OMP算法，則是MP算法的一種變體。它在更新的時(shí)候允許a的系數(shù)進(jìn)行改變。
