《壓縮感知理論分析綜述》4800字

壓縮感知理論分析綜述目錄TOC\o"1-3"\h\u51壓縮感知理論分析綜述 159951.1壓縮感知概述 1303611.1.1壓縮感知簡(jiǎn)介 1156791.1.2信號(hào)的稀疏度表示 311941.1.3測(cè)量矩陣的設(shè)計(jì) 5175401.1.4壓縮感知重構(gòu)算法 6189661.2壓縮感知貪婪重構(gòu)算法 750431.2.1SAMP算法 8273431.2.2OMP算法 91.1壓縮感知概述2004年，Donoho、Candes以及Romberg等人正式提出了壓縮感知理論，該理論認(rèn)為，如果信號(hào)具有稀疏特性，那么就可以通過(guò)較少的采樣值高概率地恢復(fù)出原始信號(hào)。這一理論的提出彌補(bǔ)了奈奎斯特（Nyquist）采樣定理對(duì)采樣速率要求過(guò)高的不足，為信號(hào)處理研究提供了新的方向。大量的物理實(shí)驗(yàn)表明，實(shí)際的無(wú)線多徑信道普遍呈現(xiàn)出稀疏結(jié)構(gòu)，即信道的多條傳播路徑中的能量往往集中在幾條路徑上。伴隨著稀疏信道概念的普及與壓縮感知理論的逐漸成熟，基于壓縮感知的信道估計(jì)技術(shù)被運(yùn)用在越來(lái)越多的無(wú)線通信系統(tǒng)中。1.1.1壓縮感知簡(jiǎn)介壓縮感知(CS)，又稱壓縮感知、壓縮采樣和稀疏采樣，是一種為欠定線性系統(tǒng)提供稀疏解的技術(shù)。在工程中，CS是利用先驗(yàn)信息的稀疏性或可壓縮性來(lái)獲取和重構(gòu)信號(hào)的過(guò)程。壓縮感知理論是在數(shù)據(jù)采樣的同時(shí)完成壓縮過(guò)程，其數(shù)學(xué)形式是將一個(gè)高維信號(hào)通過(guò)特定的矩陣投射到低維空間。重構(gòu)時(shí)，采用線性或非線性重構(gòu)算法對(duì)原始信號(hào)進(jìn)行重構(gòu)。壓縮感知理論框架主要由信號(hào)的稀疏表示、編碼測(cè)量以及重構(gòu)算法的設(shè)計(jì)這三個(gè)部分組成。其中，信號(hào)的編碼測(cè)量和重構(gòu)是基于信號(hào)的可稀疏性。編碼時(shí)，測(cè)量矩陣的選取應(yīng)滿足有限等距準(zhǔn)則(RestrictedIsometryProperty,RIP),即觀測(cè)矩陣的選取應(yīng)滿足與稀疏基不相關(guān)的原則。壓縮感知采樣原理如1.1所示。圖1.1壓縮感知采樣原理框圖假如某信號(hào)x是長(zhǎng)度為N的一維可壓縮的信號(hào)，其稀疏形式可以表示為式(22)。x=Ψθ其中，中是標(biāo)準(zhǔn)的正交基，θ是K(K<<N)稀疏表示系數(shù)。通過(guò)測(cè)量矩陣Φ∈Ry=ΦθA=ΦΨy=Aθ上式中,A∈R整個(gè)壓縮感知理論的線性測(cè)量過(guò)程可以用圖1.2表示。圖1.2壓縮感知線性測(cè)量過(guò)程對(duì)于信號(hào)重構(gòu)問(wèn)題，就是通過(guò)優(yōu)化算法獲得一個(gè)最稀疏的解θ，然后通過(guò)反演稀疏解獲得原始信號(hào)的估計(jì)值x，其重構(gòu)示意圖如圖1.3所示。圖1.3壓縮感知信號(hào)重構(gòu)過(guò)程1.1.2信號(hào)的稀疏度表示如果信號(hào)只有很少的非零元素，那么這個(gè)信號(hào)就是稀疏的。通常，時(shí)域下的自然信號(hào)都是明顯非稀疏的，不能直接進(jìn)行壓縮感知處理信號(hào)，但是將信號(hào)投影到某些變換域(如空間頻域)時(shí)就是稀疏的，經(jīng)稀疏變換后的信號(hào)即可應(yīng)用壓縮感知處理。信號(hào)的稀疏性還可以理解為:變換系數(shù)中有K個(gè)較大值系數(shù)，其他N-K個(gè)系數(shù)等于或接近于零,則可以認(rèn)為該信號(hào)是K系數(shù)信號(hào)。如一副自然場(chǎng)景圖像,它的像素幾乎都不為零,經(jīng)過(guò)小波變換后,頻域大部分系數(shù)趨近于零,因此，直接處理有限個(gè)非零系數(shù)就可以重構(gòu)整個(gè)圖像的信息。假設(shè)信號(hào)x∈RN×1,則可以用一組基向量x=i=1其中，Θ∈RN×1是標(biāo)準(zhǔn)正交基下信號(hào)的稀疏表示。當(dāng)信號(hào)x在正交基Ψ下稀疏系數(shù)θ只有K(K<<N)非零元素，那么我們就說(shuō)稀疏向量θ可以從測(cè)量值y中重構(gòu)出來(lái),也就是求解一個(gè)有正則約束的線性方程問(wèn)題。相關(guān)理論表明該線性方程可以通過(guò)求解式(30)最優(yōu)l0θ=argmin其中，θ0表示零范數(shù)，即向量中非0元素的數(shù)量。如果直接求解上式則是一個(gè)NP-hard問(wèn)題且求解的數(shù)值不穩(wěn)定。后來(lái)有人證明當(dāng)測(cè)量矩陣滿足RIP條件時(shí)，可以將求解最小l0范數(shù)問(wèn)題可以轉(zhuǎn)化為求解最小θ=argmin對(duì)于含噪聲的信號(hào)y=Aθ+εθ=argmin這類算法稱為L(zhǎng)P(線性規(guī)劃)重構(gòu)算法。對(duì)于任意參數(shù)λ,之前的約束優(yōu)化求解將轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，其等價(jià)形式如式(33)。min1根據(jù)稀疏基Ψ=ψ1.1.3測(cè)量矩陣的設(shè)計(jì)測(cè)量矩陣(也稱觀測(cè)矩陣)是用來(lái)對(duì)N維的稀疏信號(hào)進(jìn)行觀測(cè)得到M(M<<N)維的觀測(cè)向量y,而目標(biāo)信號(hào)x可以利用凸優(yōu)化等方法從該觀測(cè)值y中重構(gòu)出來(lái)。因此，理想的測(cè)量矩陣是能夠?qū)崿F(xiàn)采樣得到M個(gè)觀測(cè)值，并確保能從這M個(gè)值中重構(gòu)出長(zhǎng)度為N的信號(hào)x(或是等價(jià)的稀疏系數(shù)向量值)。為了保證壓縮感知算法中測(cè)量矩陣能夠較準(zhǔn)確重構(gòu)信號(hào)，其需要滿足如下一些的條件:(1)約束等距性原則(RestrictedIsometryProperty,RIP)，該原則定義如下:對(duì)于任意信號(hào)x假設(shè)其稀疏度為K,若存在常數(shù)δk1?δ則矩陣Φ滿足K階RIP原則。觀測(cè)基矩陣Φ與稀疏基矩陣Ψ的乘積矩陣A稱之為測(cè)量矩陣(傳感矩陣)，該矩陣同樣需要滿足RIP原則，即存在常數(shù)δk1?δ但在實(shí)際應(yīng)用中，測(cè)量矩陣是很難滿足這個(gè)條件的,因?yàn)橥ǔＧ闆r下稀疏正交基Ψ是固定的,這樣只能改變測(cè)量矩陣Φ，,由于向量θ∈k，因此驗(yàn)證矩陣的RIP原則非常困難。后來(lái)有研究提出了一個(gè)與RIP原則等價(jià)的條件即:測(cè)量矩陣Φ與正交基(2)不相關(guān)原則，該原則在實(shí)際應(yīng)用中驗(yàn)證相對(duì)較易，測(cè)量矩陣φ與正交基之間的相關(guān)系數(shù)定義如下:μΦ其中，?i∈1,2,...,M和ψj∈1,2,...,N分別表示矩陣測(cè)量矩陣的形式也有很多，經(jīng)過(guò)學(xué)者們的大量研究與總結(jié)，目前常用的測(cè)量矩陣主要分為以下兩大類。(1)隨機(jī)測(cè)量矩陣:主要有隨機(jī)高斯矩陣，隨機(jī)伯努利矩陣等，這類矩陣雖然重構(gòu)能力和適應(yīng)性較好，但是計(jì)算復(fù)雜，大儲(chǔ)存量，硬件難以實(shí)現(xiàn)，而且重構(gòu)效果相對(duì)不穩(wěn)定。經(jīng)發(fā)現(xiàn)隨機(jī)高斯測(cè)量矩陣適用于大部分信號(hào)的壓縮重構(gòu)，因此，在研究重構(gòu)算法實(shí)驗(yàn)中一般用隨機(jī)高斯矩陣作為測(cè)量矩陣。(2)確定性測(cè)量矩陣:主要有循環(huán)測(cè)量矩陣、托普利茨測(cè)量矩陣、多項(xiàng)式測(cè)量矩陣等。這類測(cè)量矩陣計(jì)算復(fù)雜度相對(duì)較低，硬件易于實(shí)現(xiàn)而且信號(hào)重構(gòu)效果較穩(wěn)定，但是大部分確定性測(cè)量矩陣重構(gòu)精度比較低，適應(yīng)性還比較弱。目前，很多科研人員綜合分析這兩種矩陣的優(yōu)劣勢(shì)，提出了一系列偽隨機(jī)確定性測(cè)量矩陣的構(gòu)造方法，如多項(xiàng)式構(gòu)造的測(cè)量矩陣，代數(shù)曲線構(gòu)造的測(cè)量矩陣，混沌序列構(gòu)造的測(cè)量矩陣等。1.1.4壓縮感知重構(gòu)算法信號(hào)經(jīng)過(guò)編碼測(cè)量后，要想重構(gòu)原始信號(hào)必須要進(jìn)一步重構(gòu),該步驟就需用到重構(gòu)算法，也是壓縮感知理論最核心的一步。目前，常用的壓縮感知重構(gòu)算法類型可以分為凸優(yōu)化算法、貪婪算法和組合算法。凸優(yōu)化算法是將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題來(lái)求解的，如基追蹤算法（BP）算法、梯度投影法、內(nèi)點(diǎn)法和迭代閾值法。凸優(yōu)化算法可以保證解的唯一性，但凸優(yōu)化算法比貪婪算法要求更高的計(jì)算復(fù)雜度。信號(hào)組合算法支持群測(cè)試和快速重建，如傅里葉采樣和鏈跟蹤等，但應(yīng)用較少。貪婪算法在每一次迭代中求解一個(gè)局部最優(yōu)解，逐步逼近原始信號(hào)。與其他兩種方法相比，貪婪算法因其運(yùn)行速度快、重構(gòu)效果好、復(fù)雜度低而得到了廣泛的應(yīng)用，如匹配追蹤算法（MP）、正交匹配追蹤算法（OMP）、壓縮采樣匹配追蹤算法（CoSaMP)、稀疏度自適應(yīng)匹配追蹤算法（SAMP）等。圖1.4重用重構(gòu)算法分類最早提出的貪婪算法是正交匹配追蹤(OMP)。OMP只選擇最匹配的原子重構(gòu)信號(hào)，計(jì)算復(fù)雜度較低。正則化正交匹配追蹤算法(ROMP)改變了基于OMP的原子選擇機(jī)制，增加了正則化過(guò)程。子空間追蹤算法(SP)引入了基于OMP和ROMP的回溯來(lái)實(shí)現(xiàn)原子刪除選擇功能。上述算法都要求以稀疏度K作為優(yōu)先級(jí)，這在實(shí)際應(yīng)用中可能是不可用的。為了克服這一缺點(diǎn)，提出了稀疏性自適應(yīng)匹配追蹤(SAMP)算法，該算法在不知道稀疏性的情況下，將恢復(fù)過(guò)程分為固定步長(zhǎng)的幾個(gè)階段進(jìn)行信號(hào)重建。但是，固定的步長(zhǎng)會(huì)導(dǎo)致重建時(shí)間長(zhǎng)或恢復(fù)不準(zhǔn)確。1.2壓縮感知貪婪重構(gòu)算法壓縮感知貪婪算法是通過(guò)選擇合適的原子并經(jīng)過(guò)一系列的逐步遞增的方法實(shí)現(xiàn)信號(hào)矢量的逼近來(lái)重構(gòu)出信號(hào)的。利用貪婪算法重構(gòu)信號(hào)時(shí)，先對(duì)各項(xiàng)參數(shù)進(jìn)行初始化設(shè)置，然后添加原子到支撐集，然后從支撐集中刪除部分原子，更新殘差，若達(dá)到迭代停止條件，則產(chǎn)生重構(gòu)信號(hào)；若未達(dá)到迭代停止條件，則繼續(xù)添加原子，并重復(fù)之后步驟。一般貪婪算法框架如圖1.5所示。圖1.5一般貪婪算法框架1.2.1SAMP算法壓縮感知是近年來(lái)出現(xiàn)的一種新的信號(hào)處理技術(shù)，其出現(xiàn)具有跨時(shí)代的意義。而重構(gòu)算法是壓縮感知的核心理論。重構(gòu)算法能夠在低維樣本數(shù)的情況下準(zhǔn)確地恢復(fù)原始信號(hào)，這對(duì)信號(hào)采樣理論具有重要意義，這意味著它可以突破傳統(tǒng)Nyquist采樣律的局限性。SAMP算法是ThongT.Do在2008年提出的，它不需要稀疏性作為重建的先驗(yàn)信息，這使得它在許多實(shí)際應(yīng)用中很有用，特別是當(dāng)信號(hào)的非零值的數(shù)目未知時(shí)。稀疏自適應(yīng)匹配跟蹤(SAMP)算法是一種自底向上和自頂向下相結(jié)合的方法。顧名思義，SAMP算法無(wú)需已知目標(biāo)信號(hào)的稀疏度信息，通過(guò)自適應(yīng)的思想調(diào)整迭代步長(zhǎng)來(lái)逐漸逼近待重構(gòu)信號(hào)稀疏度,這是該算法最大的優(yōu)勢(shì)也是與其它貪婪迭代算法的不同之處。SAMP算法在迭代過(guò)程分為多個(gè)階段，在每個(gè)階段可能有多次迭代，該階段中信號(hào)的支撐集大小保持不變,過(guò)度到下一個(gè)階段時(shí)支撐集的大小會(huì)因步長(zhǎng)的增加而改變。SAMP算法每個(gè)階段選取支撐集方法跟壓縮采樣匹配追蹤算法類似，也是通過(guò)選取傳感矩陣和殘差的相關(guān)系數(shù)模中最大的一-些值對(duì)應(yīng)的索引值構(gòu)成候選集，然后經(jīng)過(guò)迭代從該候選集中選出指定數(shù)目原子作為支撐集。SAMP算法具體流程如下：輸入:矩陣Φ,信號(hào)為b,步長(zhǎng)為S,終止算法閾值ε.輸出:重構(gòu)信號(hào)x*初始化:r0=b，Λ0=(1)初步選擇.u=absΦ擴(kuò)充支撐集和支撐集對(duì)應(yīng)矩陣.令Λn=Λn?1∪求最小二乘解.令Xn=argmin(4)對(duì)Xn的絕對(duì)值進(jìn)行降序處理，選擇前L個(gè)最大的對(duì)應(yīng)列記為本步迭代的支撐集Λn,對(duì)應(yīng)支撐集原子矩陣為(5)更新殘差.r(6)如果殘差rn2<ε1.2.2OMP算法OMP算法是經(jīng)典的貪婪迭代算法，為了克服匹配追蹤(MatchingPursuit，MP)算法收斂過(guò)慢的缺點(diǎn)，同時(shí)保證重建結(jié)果具有較高的精確度，在迭代過(guò)程中正交化處理已選原子，期望能有效減少迭代次數(shù)，達(dá)到快速收斂的目的。該算法詳細(xì)步驟如下:輸入:矩陣中Φ∈RM×輸出:重構(gòu)信號(hào)x*.初始化:r0=b,(1)找到索引λn.λn(2)擴(kuò)充支撐集和支撐集對(duì)應(yīng)矩陣，令Λn=(3)求最小二乘解、令Xn=argmin(4)更新殘差r(5)n=n+1,當(dāng)n≤k,返回(1)重新迭代.反之結(jié)束算法.上述算法先進(jìn)行初始化，然后計(jì)算恢復(fù)矩陣和當(dāng)前殘差的內(nèi)積，從中選出最大的元素所對(duì)應(yīng)的索引，即相關(guān)性最大的原子，將其放入索引集;