稀疏表示與稀疏分解

1、稀疏表示與稀疏分解第1頁(yè)，共16頁(yè)。1.稀疏表示介紹 稀疏表示，它意欲用盡可能少的非0系數(shù)表示信號(hào)的主要信息，從而簡(jiǎn)化信號(hào)處理問(wèn)題的求解過(guò)程。 稀疏表示模型可如表達(dá)式(1)所示，其中yRn為待處理信號(hào)，DR(nm)為字典，xRm為稀疏系數(shù)， |x|_0m。|x|_0為x的稀疏度，它表示x中非0稀疏的個(gè)數(shù)。 y=Dx subject to min|x|_0 (1) nmm1n1第2頁(yè)，共16頁(yè)。幾個(gè)專業(yè)名詞解析: 原子：原子 即為字典的列向量。 完備字典與過(guò)完備字典： 如果字典D中的原子恰能夠張成n維的歐式空間，則字典D是完備的。 如果mn，字典D是冗余的，同時(shí)保證還能張成n維的歐式空間，則大字

2、典D是過(guò)完備的。 我們一般用的字典都是過(guò)完備的，因?yàn)樵谶^(guò)完備的字典下分解稀疏系數(shù)不唯一，這也恰恰為圖像的自適應(yīng)處理提供的可能，我們可以根據(jù)自己處理的要求選擇最合適的最稀疏的系數(shù)。第3頁(yè)，共16頁(yè)。 其實(shí)求解過(guò)完備的稀疏表示模型等價(jià)于尋求欠定系統(tǒng)的最稀疏解問(wèn)題。 DR(nm)且mn時(shí)，如何求解 y=Dx即如下 我們已經(jīng)知道在過(guò)完備字典的條件下稀疏系數(shù)是不唯一的，但是否我們可以求出最稀疏解呢？ 第4頁(yè)，共16頁(yè)。Elad和Bruckstein在2004年對(duì)下述定理進(jìn)行了證明： 定理1：設(shè)D為一個(gè)相干系數(shù)是的原子庫(kù)，D=gi，i=1.M。如果一個(gè)N維的信號(hào)s可以表示為： 并且 1/,那么上式就是信號(hào)

3、s在D中最稀疏的表示。 注釋：定理1中的非相干原子庫(kù)D指的是指相干系數(shù)小于某一常數(shù)的原子庫(kù)，相關(guān)系數(shù)定義如下： 相關(guān)系數(shù)的大小與原子的相關(guān)性呈正比。若=1，即表明原子庫(kù)中至少有兩個(gè)原子相同，當(dāng)比較小時(shí)，即表明原子間的相關(guān)性不高即可稱此原字庫(kù)為非相干原字庫(kù)。第5頁(yè)，共16頁(yè)。 面對(duì)稀疏表示模型，有三個(gè)關(guān)鍵問(wèn)題需要解決，如下:1.如何有效獲取圖像在字典中下最稀疏的分解系數(shù)?2.如何設(shè)計(jì)與構(gòu)建有效的圖像稀疏表示字典?3.如何將圖像稀疏表示模型應(yīng)用于具體的圖像處理反問(wèn)題中? 今天我主要講的是求解稀疏系數(shù)問(wèn)題。第6頁(yè)，共16頁(yè)。2.稀疏分解算法 獲取信號(hào)在過(guò)完備字典下的最優(yōu)稀疏表示或稀疏逼近的過(guò)程叫做信

4、號(hào)的稀疏分解，這是稀疏表示能否在實(shí)際圖像處理中應(yīng)用的基本問(wèn)題。但是由于L0范數(shù)的非凸性，在過(guò)完備字典之下求最。主要采用的逼近算法1.凸松弛法 基追蹤（BP）, 基追蹤去噪算法（BPDNBPDN） ,平滑L0范數(shù)（SL0）等等。 2.貪婪法 匹配追蹤（MP） ,正交匹配追蹤（OMP）,弱匹配追蹤等等。第7頁(yè)，共16頁(yè)。2.1凸松弛法 凸松弛算法的核心思想就是用凸的或者是更容易處理的稀疏度量函數(shù)代替（1）中非凸的L0范數(shù) ，通過(guò)轉(zhuǎn)換成凸規(guī)劃或非線性規(guī)劃問(wèn)題來(lái)逼近原先的組合優(yōu)化問(wèn)題，變換后的模型則可采用諸多現(xiàn)有的高效算法進(jìn)行求解，降低了問(wèn)題的復(fù)雜度。 我在這里主要介紹的是基追蹤算法（BP）與基追蹤去

5、噪算法（BPDN）。這兩個(gè)算法的基礎(chǔ)是用L1范數(shù)替代L0范數(shù)即將 subject to y=Dx 轉(zhuǎn)化為 subject to |y-Dx|_2 x0minx1min第8頁(yè)，共16頁(yè)。為什么L1范數(shù)與L0范數(shù)效果會(huì)等價(jià)? Elad和Bruckstein在2004年對(duì)下述定理進(jìn)行了證明： 定理2：如果信號(hào)s在原子庫(kù)中存在一個(gè)系數(shù)表示，而且滿足下式: 則此分解的L1范數(shù)最小化問(wèn)題有唯一的解，即為L(zhǎng)0范數(shù)最小化的解。 1.如果滿足定理1中的條件，則L0范數(shù)的問(wèn)題將有唯一最稀疏解; 2.如果進(jìn)一步的滿足定理2的條件，則L0范數(shù)的優(yōu)化問(wèn)題與L1范數(shù)的優(yōu)化問(wèn)題等同，即對(duì)求解稀疏系數(shù)的最小L0范數(shù)問(wèn)題就轉(zhuǎn)化

6、成為了最小L1范數(shù)問(wèn)題。第9頁(yè)，共16頁(yè)。基追蹤：我們將L1范數(shù)替換L0范數(shù)之后，稀疏表示模型： min|x|_1 subject to y=Dx 就變成了一個(gè)常見的線性規(guī)劃問(wèn)題，我們可以用單純性算法或內(nèi)點(diǎn)法來(lái)求解. 基追蹤去噪：我們可以把上式的模型加以變形為： min（x） |y-Dx|_2+i|x| _1 這個(gè)稱為L(zhǎng)1范數(shù)最小二乘規(guī)劃問(wèn)題，我們可以用梯度下降或梯度投影法進(jìn)行快速的求解。 凸松弛算法的有效性依賴于過(guò)完備字典自身是否存在快速的變換與重建算法，例如對(duì)于正交基字典算法具有較高的效率，然而對(duì)于一般的過(guò)完備字典，凸松弛算法仍具有非常高的運(yùn)算復(fù)雜度。 第10頁(yè)，共16頁(yè)。2.1貪婪法 我

7、們知道稀疏解x包括非0系數(shù)的位置索引和幅值兩個(gè)信息，貪婪法的主體思路是先確定x中非0元素的位置索引，然后用最小二乘求解對(duì)應(yīng)的幅值。 與凸松弛算法相比，貪婪法具有比較低的復(fù)雜度。 我們這里主要介紹的算法是匹配追蹤算法（MP）與正交匹配追蹤算法(OMP)。因?yàn)檫@兩個(gè)算法是復(fù)雜貪婪算法的基礎(chǔ)。第11頁(yè)，共16頁(yè)。2.1.1匹配追蹤法 MP算法的基本思路是在每一次的迭代過(guò)程中，從過(guò)完備字典D中選擇與信號(hào)最為匹配的原子來(lái)構(gòu)建稀疏逼近，并且求出信號(hào)表示殘差。之后繼續(xù)選擇與信號(hào)殘差最為匹配的原子，再經(jīng)過(guò)一定次數(shù)的迭代，信號(hào)就可以由多個(gè)原子線性的表示。 x為信號(hào)， 為用于稀疏分解的過(guò)完備字典的原子（即列向量）

8、， 為r的集合。原子都做了歸一化處理 =1。第12頁(yè)，共16頁(yè)。 首先從過(guò)完備庫(kù)中選出與待分解信號(hào)x最為匹配的原子 ，何為最為匹配就是信號(hào)在原子 上的投影最大時(shí)： 信號(hào)可以分解為在最佳原子上的分量和殘余信號(hào)兩部分，即為： 其中R1x為殘余信號(hào)， 初始值R0=x。 由投影的原理可知 與R1x是正交的，故可得：由上式可知要使殘差R1最小，則投影值 要求最大。對(duì)最佳匹配后的殘余信號(hào)可以不斷進(jìn)行上面同樣的分解過(guò)程，即 其中 滿足 要求。第13頁(yè)，共16頁(yè)。 由此經(jīng)過(guò)n次迭代之后信號(hào)被分解為： Rnx表示為信號(hào)分解為n個(gè)原子的線性組合時(shí)信號(hào)的殘差。由于我們使用每步都取最優(yōu)原子，故可知?dú)埐钍菚?huì)迅速下降的，

9、當(dāng)n達(dá)到無(wú)窮是，殘差即無(wú)限接近于0.我們可以根據(jù)自己的要求設(shè)置n的值來(lái)使信號(hào)稀疏，n也可以稱為信號(hào)的稀疏度。 但是由于信號(hào)在已經(jīng)選擇的原子上面的投影一般都不會(huì)正交，所以每次迭代的結(jié)果都不是最優(yōu)的。故我們要求達(dá)到攝像的收斂條件，可能需要過(guò)多的迭代次數(shù)，計(jì)算復(fù)雜度比較大。所以我們思考如何改進(jìn)算法可以有效減少?gòu)?fù)雜度，正交匹配追蹤應(yīng)運(yùn)而生了。第14頁(yè)，共16頁(yè)。 正交匹配追蹤算法與匹配追蹤算法的唯一的區(qū)別在于我們?cè)谶f歸的對(duì)于所選擇原子集合進(jìn)行了正交化處理，為什么要這么做？因?yàn)檫@樣我們可以保證每次結(jié)果都是最優(yōu)的，從而可以有效的減少了迭代次數(shù)，提高了算法效率。 即在每次選擇的原子 用Rram-Schmid

10、t正交化處理： 其中Up為上一次的原子正交結(jié)果，初始Up= 。 需要注意信號(hào)現(xiàn)在在原子正交化的Uk上投影而非原來(lái)的原子上投影了。其余步驟與匹配追蹤一樣的。2.1.2正交匹配追蹤第15頁(yè)，共16頁(yè)。 BP與MP的算法有效的理論條件與精確重構(gòu)條件定理 我們知道MP與BP算法使用了不同的策略求解模型,我們求解稀疏系數(shù)與字典D的選擇密不可分，前面我們引用定理我么知道了L1范數(shù)最稀疏表示形式時(shí)，字典相干參數(shù)有大小限制。那么我們用BP和MP算法一樣都能夠精確重構(gòu)原信號(hào)（也就是求出最稀疏解）時(shí)的條件是什么呢？ Tropp在2004年提出的精確重構(gòu)條件(ERC)揭示了信號(hào)的稀疏性與字典的相干參數(shù)的關(guān)系。 定理（ERC） 給定信號(hào)y，字典D