壓縮感知-----介紹

1、2022-6-261壓縮感知概述壓縮感知概述Introduction to Compressive Sensing22022-6-26目錄目錄一、背景與現(xiàn)狀一、背景與現(xiàn)狀 理論產(chǎn)生背景 研究現(xiàn)狀二、壓縮感知理論介紹二、壓縮感知理論介紹 壓縮感知的基本思想 壓縮感知的數(shù)學(xué)模型 壓縮感知要解決的問題三、應(yīng)用與展望三、應(yīng)用與展望 壓縮感知的初步應(yīng)用 壓縮感知研究的公開問題 壓縮感知的總結(jié)與展望 2022-6-263 一、背景現(xiàn)狀一、背景現(xiàn)狀42022-6-261.1 理論產(chǎn)生背景理論產(chǎn)生背景1、背景現(xiàn)狀、背景現(xiàn)狀 一方面， 在奈奎斯特( Nyquist) 采樣定理為基礎(chǔ)的傳統(tǒng)數(shù)字信號(hào)處理框架下，若要

2、從采樣得到的離散信號(hào)中無失真地恢復(fù)模擬信號(hào)，采樣速率必須至少是信號(hào)帶寬的兩倍。然而，隨著當(dāng)前信息需求量的日益增加，信號(hào)帶寬越來越寬，在信息獲取中對(duì)采樣速率和處理速度等提出越來越高的要求，因而對(duì)寬帶信號(hào)處理的困難在日益加劇。例如高分辨率地理資源觀測(cè)， 其巨量數(shù)據(jù)傳輸和存儲(chǔ)就是一個(gè)艱難的工作。52022-6-261.1 理論產(chǎn)生背景理論產(chǎn)生背景1、背景現(xiàn)狀、背景現(xiàn)狀原始圖像采樣數(shù)據(jù)采樣壓縮數(shù)據(jù)傳輸解壓縮數(shù)據(jù)傳輸恢復(fù)圖像通過顯示器顯示圖像 另一方面， 在實(shí)際應(yīng)用中, 為了降低存儲(chǔ)、處理和傳輸?shù)某杀? 人們常采用壓縮方式以較少的比特?cái)?shù)表示信號(hào), 大量的非重要的數(shù)據(jù)被拋棄。這種高速采樣再壓縮的過程浪費(fèi)了

3、大量的采樣資源。 62022-6-261.1 理論產(chǎn)生背景理論產(chǎn)生背景1、背景現(xiàn)狀、背景現(xiàn)狀大部分冗余信息在采集后被丟棄采樣時(shí)造成很大的資源浪費(fèi)能否直接采集不被丟棄的信息？72022-6-261.1理論產(chǎn)生背景理論產(chǎn)生背景1、背景現(xiàn)狀、背景現(xiàn)狀被感知對(duì)象重建信號(hào)壓縮感知名詞解釋：壓縮感知直接感知壓縮后的信息基本方法：信號(hào)在某一個(gè)正交空間具有稀疏性（即可壓縮性），就能以較低的頻率（遠(yuǎn)低于奈奎斯特采樣頻率）采樣該信號(hào)，并可能以高概率重建該信號(hào)。82022-6-261.2 研究現(xiàn)狀研究現(xiàn)狀1、背景現(xiàn)狀、背景現(xiàn)狀2006Robust Uncertainty Principles：Exact Signa

4、l Reconstruction fromHighly Incomplete Frequency InformationTerence Tao、Emmanuel Cands2006Compressed SensingDavid Donoho2007Compressive SensingRichard Baraniuk上述文章奠定了壓縮感知的理論基礎(chǔ)。國(guó)內(nèi)也將其翻譯成壓縮傳感或壓縮采樣。92022-6-261.2 研究現(xiàn)狀研究現(xiàn)狀1、背景現(xiàn)狀、背景現(xiàn)狀u理論一經(jīng)提出，就在信息論、信號(hào)處理、圖像處理等領(lǐng)域受到高度關(guān)注。u在美國(guó)、英國(guó)、德國(guó)、法國(guó)、瑞士、以色列等許多國(guó)家的知名大學(xué)(如麻省理工學(xué)院、斯

5、坦福大學(xué)、普林斯頓大學(xué)、萊斯大學(xué)、杜克大學(xué)、慕尼黑工業(yè)大學(xué)、愛丁堡大學(xué)等等)成立了專門的課題組對(duì)CS進(jìn)行研究。u此外，萊斯大學(xué)還建立了專門的CompressiveSensing網(wǎng)站，及時(shí)報(bào)道和更新該方向的最新研究成果。102022-6-261.2 研究現(xiàn)狀研究現(xiàn)狀1、背景現(xiàn)狀、背景現(xiàn)狀u西安電子科技大學(xué)石光明教授在電子學(xué)報(bào)發(fā)表綜述文章，系統(tǒng)地闡述了壓縮傳感的理論框架以及其中涉及到的關(guān)鍵技術(shù)問題。燕山大學(xué)練秋生教授的課題組針對(duì)壓縮感知的稀疏重建算法進(jìn)行了系統(tǒng)深入的研究，提出一系列高質(zhì)量的圖像重建算法。中科院電子所的方廣有研究員等，探索了壓縮感知理論在探地雷達(dá)三維成像中的應(yīng)用。u除此之外，還有很多

6、國(guó)內(nèi)學(xué)者在壓縮感知方面做了重要的工作，如清華大學(xué)、天津大學(xué)、國(guó)防科技大學(xué)、廈門大學(xué)、湖南大學(xué)、西南交通大學(xué)、南京郵電大學(xué)、華南理工大學(xué)、北京理工大學(xué)、北京交通大學(xué)等等單位，在此不一一列舉。2022-6-2611 二、壓縮感知理論介紹二、壓縮感知理論介紹122022-6-262.1 壓縮感知的基本思想壓縮感知的基本思想2、壓縮感知理論介紹、壓縮感知理論介紹 壓縮感知理論與傳統(tǒng)奈奎斯特采樣定理不同， 它指出，只要信號(hào)是可壓縮的或在某個(gè)變換域是稀疏的， 那么就可以用一個(gè)與變換基不相關(guān)的觀測(cè)矩陣將變換所得高維信號(hào)投影到一個(gè)低維空間上，然后通過求解一個(gè)優(yōu)化問題就可以從這些少量的投影中以高概率重構(gòu)出原信號(hào)

7、，可以證明這樣的投影包含了重構(gòu)信號(hào)的足夠信息。在該理論框架下，采樣速率不決定于信號(hào)的帶寬， 而決定于信息在信號(hào)中的結(jié)構(gòu)和內(nèi)容。132022-6-262.2 壓縮感知的數(shù)學(xué)模型壓縮感知的數(shù)學(xué)模型2、壓縮感知理論介紹、壓縮感知理論介紹 若將N維實(shí)信號(hào) 在某組正交基 下進(jìn)行展開，即： 1NRx Nii1Niiix1xxTiii ,其中，展開系數(shù)寫成矩陣形式可以得到：（2）（1）x142022-6-262.2 壓縮感知的數(shù)學(xué)模型壓縮感知的數(shù)學(xué)模型2、壓縮感知理論介紹、壓縮感知理論介紹這里NNR),.,(321為正交基字典矩陣，滿足ITT，展開系數(shù)向量為TN),.,(21假設(shè)系數(shù)向量是K稀疏的，即其中非

8、零系數(shù)的個(gè)數(shù)KN，那么采用另一個(gè)與正交基不相關(guān)的矩陣：MN（MN）（這里的每一行可以看作是一個(gè)傳感器，它與系數(shù)相乘，獲取了信號(hào)的部分信息），對(duì)信號(hào)執(zhí)行一個(gè)壓縮觀測(cè)：xy（3）152022-6-262.2 壓縮感知的數(shù)學(xué)模型壓縮感知的數(shù)學(xué)模型2、壓縮感知理論介紹、壓縮感知理論介紹就可以得到M個(gè)線性觀測(cè)（或投影）MRy，這些少量線性投影中則包含了重構(gòu)信號(hào)X的足夠信息，如下圖所示：162022-6-262.2 壓縮感知的數(shù)學(xué)模型壓縮感知的數(shù)學(xué)模型2、壓縮感知理論介紹、壓縮感知理論介紹 從y中恢復(fù)x是一個(gè)解線性方程組的問題，但從方程（3）上看，這似乎是不可能的，因?yàn)檫@是一個(gè)未知數(shù)個(gè)數(shù)大于方程個(gè)數(shù)的病態(tài)

9、方程，存在無窮多個(gè)解。但是，將式（2）帶入式（3），記CS信息算子 可以得到： CSACSAy（4） 雖然從y中恢復(fù) 也是一個(gè)病態(tài)問題，但是因?yàn)橄禂?shù) 是稀疏的，這樣未知數(shù)的個(gè)數(shù)就大大減少，使得信號(hào)重構(gòu)成為可能。那么在什么情況下式（4）的解是存在的呢？172022-6-262.2 壓縮感知的數(shù)學(xué)模型壓縮感知的數(shù)學(xué)模型2、壓縮感知理論介紹、壓縮感知理論介紹 可以證明：只要矩陣 中任意2K列都是線性獨(dú)立的，那么至少存在一個(gè)K-稀疏的系數(shù)向量滿足 。換言之，在滿足上述要求的情況下，通過解一個(gè)非線性優(yōu)化問題就能從觀測(cè)y、觀測(cè)矩陣 和字典矩陣 中近乎完美的重建信號(hào)x。信號(hào)壓縮感知的過程如下圖所示： CSA

10、CSAy 182022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 從上述數(shù)學(xué)模型可知, 壓縮感知理論的實(shí)現(xiàn)包含三個(gè)關(guān)鍵要素：稀疏性、非相關(guān)觀測(cè)、非線性優(yōu)化重建，其中信號(hào)的稀疏性是壓縮感知的必備條件, 非相關(guān)觀測(cè)是壓縮感知的關(guān)鍵, 非線性優(yōu)化是壓縮感知重建信號(hào)的手段。 要解決的問題有以下三方面： 1、信號(hào)的稀疏表示 2、觀測(cè)矩陣的設(shè)計(jì) 3、信號(hào)重構(gòu)算法的設(shè)計(jì)192022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 1、信號(hào)的稀疏表示 稀疏表示是信息優(yōu)化建模的終極目標(biāo), 也是信息處理中一個(gè)古老

11、而又嶄新的課題, 利用稀疏性可以解決信號(hào)處理中許多復(fù)雜的問題, 各種數(shù)學(xué)分析和信號(hào)處理的理論為字典的構(gòu)建提供了許多良好的工具,如下圖所示。稀疏表示的研究興起于二十世紀(jì)九十年代,在本世紀(jì)初得到蓬勃發(fā)展, 壓縮感知的提出更是為其提供了工程應(yīng)用的土壤, 極大地豐富了該領(lǐng)域的研究成果。202022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 1、信號(hào)的稀疏表示 212022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 1、信號(hào)的稀疏表示 研究現(xiàn)狀：（1）多種變換域分析方法為稀疏表示提供了可能。（2）

12、許多信號(hào)，諸如自然圖像，本身就存在著變換域稀疏性。（3）信號(hào)在冗余字典下的稀疏表示 目前信號(hào)在冗余字典下的稀疏表示的研究集中在兩個(gè)方面: (a)如何構(gòu)造一個(gè)適合某一類信號(hào)的冗余字典; (b)如何設(shè)計(jì)快速有效的稀疏分解算法. 222022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 2、觀測(cè)矩陣的設(shè)計(jì) 目前, 對(duì)觀測(cè)矩陣的研究是壓縮感知理論的一個(gè)重要方面。在該理論中， 對(duì)觀測(cè)矩陣的約束是比較寬松的， Donoho在中給出了觀測(cè)矩陣所必需具備的三個(gè)條件， 并指出大部分一致分布的隨機(jī)矩陣都具備這三個(gè)條件, 均可作為觀測(cè)矩陣， 如：部分Fourier

13、集、部分Hadamard集、一致分布的隨機(jī)投影(uniform Random Projection)集等，這與對(duì)有限等距性質(zhì)進(jìn)行研究得出的結(jié)論相一致。但是， 使用上述各種觀測(cè)矩陣進(jìn)行觀測(cè)后, 都僅僅能保證以很高的概率去恢復(fù)信號(hào)， 而不能保證百分之百地精確重構(gòu)信號(hào)。 對(duì)于任何穩(wěn)定的重構(gòu)算法是否存在一個(gè)真實(shí)的確定性的觀測(cè)矩陣仍是一個(gè)有待研究的問題。232022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 3、信號(hào)重構(gòu)算法的設(shè)計(jì) 目前為止出現(xiàn)的重構(gòu)算法都可以歸入以下3大類： （1）貪婪追蹤算法：這類方法是通過每次迭代時(shí)選擇一個(gè)局部最優(yōu)解 來逐步逼近

14、原始信號(hào)，這類算法包括MP（Matching Pursuit,匹配 追蹤）算法，OMP（Orthogonal Matching Pursuit, 正交匹配 追蹤)算法，分段OMP算法和正則化OMP算法。 （2）凸松弛法: 這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號(hào) 的逼近, 如BP算法, 內(nèi)點(diǎn)法， 梯度投影方法和迭代閾值法。 （3）組合算法：這類方法要求信號(hào)的采樣支持通過分組測(cè)試快速重建， 如傅立葉采樣， 鏈?zhǔn)阶粉櫤虷HS(HeavgHitters onSteroids)追蹤等。242022-6-262.3 壓縮感知要解決的問題壓縮感知要解決的問題2、壓縮感知理論介紹、壓縮感知理論介紹 3

15、、信號(hào)重構(gòu)算法的設(shè)計(jì) 可以看出， 每種算法都有其固有的缺點(diǎn)。凸松弛法重構(gòu)信號(hào)所需的觀測(cè)次數(shù)最少， 但往往計(jì)算負(fù)擔(dān)很重。貪婪追蹤算法在運(yùn)行時(shí)間和采樣效率上都位于另兩類算法之間。 重構(gòu)算法和所需的觀測(cè)次數(shù)密切相關(guān)。當(dāng)前， 壓縮感知理論的信號(hào)重構(gòu)問題的研究主要集中在如何構(gòu)造穩(wěn)定的、計(jì)算復(fù)雜度較低的、對(duì)觀測(cè)數(shù)量要求較少的重構(gòu)算法來精確地恢復(fù)原信號(hào)。2022-6-2625 三、應(yīng)用與展望三、應(yīng)用與展望262022-6-263.1 壓縮感知的初步應(yīng)用壓縮感知的初步應(yīng)用3、應(yīng)用與展望、應(yīng)用與展望 直接信息采樣特性使得壓縮感知理論具有巨大的吸引力和應(yīng)用前景， 隨之出現(xiàn)的是相關(guān)的理論完善和實(shí)踐成果。應(yīng)用研究已經(jīng)

16、涉及到眾多領(lǐng)域，如： CS雷達(dá)、DCS(DistributedCompressedSensing)理論、無線傳感網(wǎng)絡(luò)、圖像采集設(shè)備的開發(fā)、醫(yī)學(xué)圖像處理、生物傳感、Analog 2 to 2 Information、光譜分析、超譜圖像處理等。 1、在成像方面, 壓縮感知理論的出現(xiàn)激起了人們研究新型傳感器的 熱情, 壓縮感知采樣對(duì)昂貴的成像器件的設(shè)計(jì)產(chǎn)生重大影響。 2、在地震勘探成像和核磁共振成像中, 對(duì)目標(biāo)信號(hào)將有望采用少量 的隨機(jī)觀測(cè)次數(shù)就能獲得高精度重構(gòu)。272022-6-263.1 壓縮感知的初步應(yīng)用壓縮感知的初步應(yīng)用3、應(yīng)用與展望、應(yīng)用與展望 3、取代傳統(tǒng)數(shù)碼相機(jī)拍照時(shí)采集大量像素的一種

17、新型單像素CS相機(jī) 已經(jīng)得到論證。 4、美國(guó)Rice 大學(xué)也已經(jīng)研制出單像素相機(jī)。 5、在寬帶無線頻率信號(hào)分析中, 由于目前A/D轉(zhuǎn)換器技術(shù)的限制, 可以 用遠(yuǎn)低于奈奎斯特采樣頻率的速率采集信號(hào)。 6、在X射線和生物醫(yī)學(xué)中, 可以通過采集遠(yuǎn)少于未知像素點(diǎn)數(shù)的觀測(cè)樣 本來獲取感興趣的圖像信息。 7、基因表達(dá)研究也開始使用壓縮感知理論, 試圖從少量的觀測(cè)樣本中, 例如幾十種來推斷成千上萬種基因的表達(dá)。282022-6-263.2 壓縮感知研究的公開問題（摘自壓縮感知研究的公開問題（摘自09年文獻(xiàn)）年文獻(xiàn)）3、應(yīng)用與展望、應(yīng)用與展望1、p2范數(shù)優(yōu)化問題 壓縮感知理論在圖像壓縮編碼等方面也應(yīng)該有很廣泛

18、的前景，但由于信號(hào)的恢復(fù)方法是建立在p2范數(shù)意義下，數(shù)據(jù)之間還有很大的冗余性沒有去除， 相比傳統(tǒng)的小波變換編碼，壓縮感知理論應(yīng)用于圖像壓縮的效果還不理想， p2范數(shù)的優(yōu)化是提高基于壓縮感知理論的壓縮算法效果的必經(jīng)之路。 p2范數(shù)的優(yōu)化方法是一個(gè)公開問題(open problem)，對(duì)它的研究將推動(dòng)壓縮感知理論在壓縮方面的應(yīng)用，具有很深遠(yuǎn)的意義。292022-6-263.2 壓縮感知研究的公開問題（摘自壓縮感知研究的公開問題（摘自09年文獻(xiàn)）年文獻(xiàn)）3、應(yīng)用與展望、應(yīng)用與展望2、含噪信號(hào)的恢復(fù)算法 在實(shí)際工程應(yīng)用中, 待處理信號(hào)一般都不同程度地受到各種噪聲的污染。含噪信號(hào)不是嚴(yán)格的稀疏信號(hào), 但

19、是仍屬于可壓縮信號(hào)。 現(xiàn)有的壓縮感知理論中,恢復(fù)信號(hào)的最基本依據(jù)是信號(hào)在某個(gè)變換空間的分解系數(shù)是稀疏的, 而噪聲的存在則破壞了信號(hào)在空間中的稀疏性。在使用優(yōu)化方法恢復(fù)信號(hào)時(shí), 如果對(duì)含噪信號(hào)采用單一的稀疏性約束原則, 則無法有效恢復(fù)原始稀疏信號(hào)。這時(shí), 壓縮感知理論仍然可以采用其它有效的恢復(fù)信號(hào)的方法, 主要的不同之處在于恢復(fù)過程所使用的優(yōu)化目標(biāo)函數(shù)的形式不同, 參數(shù)的設(shè)置不同. 不同的優(yōu)化目標(biāo)函數(shù)使得信號(hào)的恢復(fù)效果也不盡相同.302022-6-263.2 壓縮感知研究的公開問題（摘自壓縮感知研究的公開問題（摘自09年文獻(xiàn)）年文獻(xiàn)）3、應(yīng)用與展望、應(yīng)用與展望3、觀測(cè)矩陣與恢復(fù)性能關(guān)系 觀測(cè)矩陣

20、與稀疏變換基的不相干特性是壓縮感知理論具有良好性能的基礎(chǔ)。由于隨機(jī)高斯分布的觀測(cè)矩陣具有與其它固定基都不相關(guān)的特性而被廣泛采用。但在實(shí)際的應(yīng)用中, 這種觀測(cè)矩陣存在存儲(chǔ)矩陣元素容量巨大、計(jì)算復(fù)雜度高的缺點(diǎn)。 觀測(cè)矩陣的隨機(jī)不相關(guān)特性是正確恢復(fù)信號(hào)的一個(gè)充分條件, 觀測(cè)矩陣和信號(hào)的高度不相干是有效恢復(fù)信號(hào)的保證。但是, 現(xiàn)在仍然無法確定隨機(jī)不相關(guān)特性是否是最優(yōu)恢復(fù)信號(hào)的必要條件, 這仍是一個(gè)公開問題。另外, 如何衡量觀測(cè)矩陣的不相干特性, 以及它們與恢復(fù)性能之間的關(guān)系也是一個(gè)尚未解決的問題。312022-6-263.2 壓縮感知研究的公開問題（摘自壓縮感知研究的公開問題（摘自09年文獻(xiàn)）年文獻(xiàn)）

21、3、應(yīng)用與展望、應(yīng)用與展望4、分布式壓縮感知理論(Distributed Compressed Sensing, DCS) 目前， 針對(duì)單個(gè)信號(hào)的壓縮感知的研究和應(yīng)用已經(jīng)開展得比較深入, 但是對(duì)分布式信號(hào)的處理仍然研究得不夠。 例如， 對(duì)于一個(gè)包含大量傳感器節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)，每個(gè)傳感器都會(huì)采集大量的數(shù)據(jù)， 這些數(shù)據(jù)將會(huì)傳輸?shù)揭粋€(gè)控制中心， 也會(huì)在各個(gè)節(jié)點(diǎn)之間傳輸。 顯然， 在這種分布式傳感器網(wǎng)絡(luò)中， 數(shù)據(jù)傳輸對(duì)功耗和帶寬的需求非常大， 那么， 如何對(duì)分布式信號(hào)進(jìn)行壓縮以減少通信壓力成為非常緊迫的需求。 322022-6-263.3 壓縮感知研究的總結(jié)與展望壓縮感知研究的總結(jié)與展望3、應(yīng)用與展望、應(yīng)用與展望 壓縮感知理論利用了信號(hào)的稀疏特性, 將原來基于奈奎斯特采樣定理的信號(hào)采樣過程轉(zhuǎn)化為基于優(yōu)化計(jì)算恢復(fù)信號(hào)的觀測(cè)過程。 也就是利用長(zhǎng)時(shí)間積分換取采樣頻率的降低, 省去了高速采樣過程中獲得大批冗余數(shù)據(jù)然后再舍去大部分無用數(shù)據(jù)的中間過程,