【摘 要】壓縮感知CS理論突破了原有信息處理方式，引起了眾多領(lǐng)域的關(guān)注。本文介紹壓縮感知基本原理并指出其關(guān)鍵技術(shù)；分析信號(hào)稀疏表示的基本原理，歸類和總結(jié)常用信號(hào)稀疏表示方法；闡述感知矩陣的采樣過程，提出設(shè)計(jì)感知矩陣需滿足的條件并歸納現(xiàn)有感知矩陣及其特點(diǎn)；分析信號(hào)重構(gòu)原理并對(duì)現(xiàn)有重構(gòu)算法分類介紹。

【關(guān)鍵詞】壓縮感知 信號(hào)稀疏 感知矩陣 重構(gòu)算法

一、基本原理

壓縮感知[CS（Compressive Sensing）：若信號(hào)在某個(gè)變換域具有稀疏表示，使用感知矩陣（與變換域不相關(guān)且維數(shù)比信號(hào)維數(shù)低很多）將信號(hào)投影到一個(gè)低維空間上即得到觀測(cè)值（包含了足夠的用于重構(gòu)信號(hào)的采樣值），最后通過求解最優(yōu)化問題從觀測(cè)值中高概率重構(gòu)出原始信號(hào)。由此可知，壓縮感知理論主要包含信號(hào)的稀疏表示、感知（觀測(cè)）矩陣的設(shè)計(jì)、重構(gòu)算法設(shè)計(jì)三個(gè)部分。信號(hào)的稀疏表示是信號(hào)可壓縮感知的先決條件，感知矩陣是獲取信號(hào)結(jié)構(gòu)化表示的手段，重構(gòu)算法是實(shí)現(xiàn)信號(hào)重構(gòu)的保證。信號(hào)壓縮感知處理流程如圖1。

二、信號(hào)的稀疏表示

通常所說的“稀疏”是指信號(hào)可以用一個(gè)僅有少量非零元素的向量來(lái)等價(jià)表示，即信號(hào)經(jīng)變換域稀疏變換后只有少數(shù)元素不為零。假設(shè)信號(hào)（即長(zhǎng)度為N），S能夠用一組冗余基的線性組合來(lái)表示：

或（1）

上式中，，Φ是的正交矩陣，是S在變換域Φ的變換向量，故S和是同一信號(hào)的兩種表示形式。若中有且僅有K（）個(gè)非零元素，或者中的元素呈指數(shù)級(jí)遞減趨近0，僅僅具有K個(gè)大系數(shù)，其他系數(shù)都趨近于0，則稱信號(hào)S是K-稀疏的，Φ是S的稀疏基。實(shí)際應(yīng)用中大多數(shù)信號(hào)都不是嚴(yán)格稀疏的，但可壓縮為具有K個(gè)大系數(shù)的等價(jià)向量。信號(hào)S在Φ域的稀疏表示如圖2。目前常用信號(hào)稀疏表示方法有正交變換、多尺度幾何分析及字典學(xué)習(xí)。

（一）正交變換

正交變換具有同構(gòu)性，在變換域和信號(hào)域信號(hào)維數(shù)相同，分析結(jié)果不會(huì)產(chǎn)生冗余信息；而且它的逆與共軛相等，計(jì)算方便。常用正交變換有傅立葉變換、加窗傅立葉變換和小波變換。其共同特點(diǎn)是：對(duì)于給定信號(hào)，唯一，但若信號(hào)的特性與基函數(shù)不完全匹配，則不一定能夠獲得。

傅立葉變換采用正弦波作為變換的基本元素，可以有效地稀疏平滑信號(hào)，能夠反映出信號(hào)在整個(gè)時(shí)域的全部頻譜成分，但不具備時(shí)間局域化能力，不能反映出非平穩(wěn)信號(hào)在局部區(qū)域的頻域特性。其變種離散傅立葉變換、離散余弦變換等曾被廣泛應(yīng)用于圖像、視頻壓縮。加窗傅立葉變換，采用窗函數(shù)（高斯函數(shù)）對(duì)信號(hào)加窗后再進(jìn)行傅立葉變換，具有時(shí)域和頻域局部化特性，但對(duì)任何頻率時(shí)頻窗口的形狀大小都一致。在此基礎(chǔ)上發(fā)展起來(lái)的小波變換，時(shí)頻窗口大小可根據(jù)頻率變化而變化，增加了時(shí)頻局部化能力，但小波變換稀疏表示二維或更高維信號(hào)時(shí)性能不佳。

（二）多尺度幾何分析

多尺度幾何分析MGA[2]更滿足人類視覺感知特性[87]，能夠用更少的系數(shù)稀疏表示二維或高維信號(hào)。迄今為止主要方法有：Ridgelet變換、MonoscaleRidgele變換、Curvelet變換、Bandelet變換、Contourlet變換。脊波變換可以最優(yōu)化表達(dá)具有直線狀奇異性的多變量函數(shù)，不能有效表達(dá)具有曲線奇異性的多變量函數(shù)將局部化思想融入其中提出的單尺度脊波變換，能有效表達(dá)具有直線狀或曲線奇異性的多變量函數(shù)。單尺度脊波變換的基函數(shù)寬度可變但長(zhǎng)度固定，曲波變換在此基礎(chǔ)上使得長(zhǎng)度也可變，從而具有各向奇異的特點(diǎn)。Bandelet變換是一種可跟蹤圖像幾何正則方向的自適應(yīng)圖像表示方法，在壓縮和去噪方面具有一定的優(yōu)勢(shì)。輪廓波變換時(shí)一種多分辨率、局域性、方向性的圖像表示方法，是一種真正符合視覺特性的圖像二維表示方法。

（三）字典學(xué)習(xí)

上面兩種方法的變換域是需要預(yù)先指定且固定不變的，但實(shí)際研究中面臨的信號(hào)多種多樣，甚至同一信號(hào)具有不同類型的內(nèi)容，這需要變換域隨信號(hào)改變而改變從而得到好的稀疏表示。字典學(xué)習(xí)就是從數(shù)據(jù)中學(xué)習(xí)信號(hào)的最優(yōu)稀疏表示，使字典中原子的尺度和方向特性盡可能接近信號(hào)，它不需要預(yù)先指定變換域，通過學(xué)習(xí)得到的自適應(yīng)字典能夠最優(yōu)的稀疏表示信號(hào)。目前廣泛應(yīng)用的字典學(xué)習(xí)方法有：基于期望最大化的最優(yōu)方向法（Methode of Optimal Directions，MOD），基于期望-條件-最大化的通過K次奇異值分解的K-SVD（K Singular Value Decomposition），基于迭代最小二乘法的字典學(xué)習(xí)算法、基于遞歸最小二乘法的字典學(xué)習(xí)方法。

該類方法的研究雖然已經(jīng)取得一些成果，但在感知矩陣應(yīng)該滿足的條件、字典的評(píng)價(jià)方法等方面還欠缺相關(guān)理論研究。

三、感知矩陣采樣過程及設(shè)計(jì)

壓縮感知的觀測(cè)采樣過程是一個(gè)線性測(cè)量過程，假設(shè)信號(hào)是稀疏的，直接使用感知矩陣對(duì)S進(jìn)行觀測(cè)可得到長(zhǎng)度為M的觀測(cè)值Y（）：（2）

若不是稀疏的，則先在變換域?qū)進(jìn)行稀疏變換得到，再進(jìn)行觀測(cè)得到觀測(cè)值，由式（1）和（2）可得：

（3）

其中，CS的觀測(cè)采樣過程如圖3。

為了滿足使用少量觀測(cè)值重構(gòu)出高精度的圖像，在設(shè)計(jì)感知矩陣時(shí)需要滿足條件：（1）有限等距性（Restricted IsometryProperty，RIP）（2）非相干性（Incoherence）。RIP保證感知矩陣不會(huì)把兩個(gè)不同的K-稀疏信號(hào)映射到同一個(gè)集合中，但判斷一個(gè)矩陣是否滿足RIP非常困難，Candes等發(fā)現(xiàn)只要保證感知矩陣和變換域不相干，則在很大概率上滿足RIP性質(zhì)。通常所說的不相干就是指感知矩陣中的任意不能用變換域中的線性表示出來(lái)，或者需要非常多的系數(shù)才能表示出來(lái)。

研究表明，很多矩陣都可以作為CS中的感知矩陣，主要分成三大類。隨機(jī)測(cè)量矩陣類結(jié)構(gòu)化隨機(jī)測(cè)量矩陣類以及由Ronald A.DeVore提出的多項(xiàng)式確定性測(cè)量矩陣，使用它對(duì)圖像進(jìn)行壓縮感知，重建效果劣于哈達(dá)瑪測(cè)量矩陣，優(yōu)于高斯隨機(jī)測(cè)量矩陣，是目前較新的研究方向。

四、重構(gòu)算法圖

CS重構(gòu)指的是用觀測(cè)向量Y根據(jù)一定的算法還原出原始信號(hào)S。CS理論通過求解式（3）的逆問題先求出信號(hào)的稀疏表示，再通過式（1）求解出S，其本質(zhì)是求解最小范數(shù)問題，表示中非零元素個(gè)數(shù)，這是一個(gè)NP-hard問題，不易求解。研究證明當(dāng)感知矩陣滿足RIP時(shí)，可以用最小范數(shù)等價(jià)表示。

目前的重構(gòu)算法可分成三大類：

（一）貪婪算法

貪婪算法采用某種準(zhǔn)則在每次迭代時(shí)從冗余字典中選取一個(gè)或幾個(gè)與觀測(cè)值余量最大相關(guān)的原子，最終尋找一組與觀測(cè)值匹配的最稀疏的原子組合，從而實(shí)現(xiàn)信號(hào)重構(gòu)。最經(jīng)典的就是匹配追蹤算法，由于它不是一個(gè)正交投影，在已選原子組成的子空間上信號(hào)的擴(kuò)展性不是最好的。為了改進(jìn)此缺點(diǎn)，學(xué)者們?cè)诖嘶A(chǔ)上又提出了正交匹配追蹤算法，正則正交匹配追蹤算法，壓縮采樣匹配追蹤算法，分段追蹤算法，子空間追蹤算法等。學(xué)者Blumensath和Davies還結(jié)合方向優(yōu)化，選取合適的原子后不使用最小二乘法求解，而是選擇合適的方向和步長(zhǎng)來(lái)搜索最優(yōu)解，據(jù)此提出三種可選方向追蹤算法：梯度追蹤算法，共軛梯度追蹤算法和近似共軛梯度追蹤算法。后來(lái)他們優(yōu)化原子選擇準(zhǔn)則，提出分段弱閾值共軛梯度追蹤算法。上面的算法大多需要事先知道信號(hào)的稀疏度K，最近提出的稀疏自適應(yīng)匹配追蹤算法可在未知稀疏度K的情況下通過交替估計(jì)信號(hào)的稀疏度和尋找信號(hào)的實(shí)際原子集合來(lái)實(shí)現(xiàn)信號(hào)的重構(gòu)。該類算法重構(gòu)速度快，但是需要的測(cè)量數(shù)據(jù)多且重構(gòu)精度偏低。

（二）凸優(yōu)化算法

凸優(yōu)化算法是基于最小范數(shù)問題重構(gòu)信號(hào)，使用基追蹤BP的優(yōu)化原則求解。BP算法在每次迭代時(shí)從過完備原子庫(kù)（即感知矩陣）中尋找最佳的匹配原子。常用的凸優(yōu)算法有內(nèi)點(diǎn)算法IM，在兩個(gè)凸平面上進(jìn)行交替投影實(shí)現(xiàn)重構(gòu)的凸集投影算法POCS，迭代收縮算法IST，為解決模糊圖像復(fù)原而提出的兩步迭代收縮算法TwIST，將不帶約束的問題轉(zhuǎn)化為邊界約束的二次問題再執(zhí)行梯度投影迭代實(shí)現(xiàn)重構(gòu)的用于稀疏重建的梯度追蹤算法GPSR，引入Bregman迭代并將有條件約束轉(zhuǎn)化成無(wú)條件約束的固定點(diǎn)連續(xù)算法FPC，在FPC基礎(chǔ)上提出的線性Bregman迭代算法LBI以及分裂Bregman算法。

該類算法具有較強(qiáng)的稀疏重建保證，在感知矩陣滿足一定條件時(shí)重構(gòu)精度高，所需測(cè)量數(shù)據(jù)少，但是算法計(jì)算復(fù)雜度高，不太適合于大尺度信號(hào)重構(gòu)。

（三） 組合算法

組合算法將信號(hào)高度結(jié)構(gòu)化采樣，通過分組測(cè)試快速重構(gòu)，如稀疏傅立葉表示法、鏈?zhǔn)阶粉櫡āHSP法以及稀疏貝葉斯算法，該類算法效率位于前兩類之間。

五、結(jié)束語(yǔ)

CS理論是信號(hào)處理領(lǐng)域的一次巨大變革，它受到國(guó)內(nèi)外諸多領(lǐng)域的極大重視，它在信號(hào)處理、語(yǔ)音/圖像處理、醫(yī)學(xué)成像、模式識(shí)別、天文、光學(xué)/雷達(dá)成像以及無(wú)線通信等領(lǐng)域顯現(xiàn)出巨大的潛力也讓人嘆為觀止。

經(jīng)過近幾年的研究，CS理論得到了快速發(fā)展，也有一些成功應(yīng)用的案例，如在成像系統(tǒng)和高速信號(hào)采樣領(lǐng)域的應(yīng)用，但將CS理論推向?qū)嵱没詻]有實(shí)質(zhì)性突破，因此需要對(duì)CS基本理論進(jìn)行更深層次研究，逐步將其實(shí)用化。