現(xiàn)代信號處理教程（第三版）課件 第15 章 壓縮感知的基礎(chǔ)理論-1

第五篇壓縮感知（CS）第15章壓縮感知的基礎(chǔ)理論第16章模擬/信息轉(zhuǎn)換及CS的應(yīng)用

第15章壓縮感知的基礎(chǔ)理論15.1壓縮感知的基本概念15.2預(yù)備知識15.3信號的稀疏表示15.4測量矩陣需要滿足的性質(zhì)15.5可壓縮信號的恢復(fù)15.6噪聲情況下的信號恢復(fù)15.7測量矩陣的構(gòu)造15.8稀疏信號恢復(fù)算法我們已迅速進(jìn)入了數(shù)字化的信息時代：數(shù)字通訊數(shù)字控制數(shù)字化儀表數(shù)字家電數(shù)字化醫(yī)療儀器數(shù)字測量數(shù)字“圖書館”理論基礎(chǔ)：數(shù)字信號處理（DSP）手機(jī)MP3、MP4數(shù)碼相機(jī)錄音筆U盤掌上電腦15.1壓縮感知的基本概念

然而，物理世界的信息（信號和圖像）是時間和空間的連續(xù)函數(shù)（模擬）。DSP能處理的是數(shù)字信號。將模擬信號和模擬圖像轉(zhuǎn)變?yōu)閿?shù)字化的形式需要抽樣，即模/數(shù)（A/D）轉(zhuǎn)換。在數(shù)字信號處理中，經(jīng)典的抽樣定理，即Shannon抽樣定理被譽(yù)為A/D轉(zhuǎn)換的金標(biāo)準(zhǔn)。DSPA/D打開了由模擬世界進(jìn)入數(shù)字世界的大門！

Shannon抽樣定理：

設(shè)

是有限帶寬的，抽樣頻率

至少要是其最高頻率

的兩倍，才能由抽樣后的離散信號

精確地恢復(fù)（或重建）出

。如何重建？1.D/A；2.重建公式：

在實(shí)現(xiàn)信號和圖像的A/D轉(zhuǎn)換時，經(jīng)典抽樣定理限定的抽樣頻率過高，以致數(shù)字化后的數(shù)據(jù)量太大。如現(xiàn)代通信中，抽樣頻率可高達(dá)GHz；專業(yè)數(shù)碼相機(jī)，幾千萬像素！4個小時的會議錄音的數(shù)據(jù)量就是5Gbit。這給采集、存儲、傳輸和處理帶來了極大的負(fù)擔(dān)！解決數(shù)據(jù)量大的問題，目前最通用的方法是數(shù)據(jù)壓縮。采集－壓縮過程有如下三個不足：（1）數(shù)據(jù)的長度

可能是非常大的；（2）變換后的小系數(shù)雖被舍棄，但要算出來；（3）大系數(shù)的位置也必須編碼，這增加了運(yùn)算

和存儲的負(fù)擔(dān)。JPEGMPEGMP3ZIP對模擬信號抽樣，真的需要嗎？

絕大部分物理信號有一個基本特點(diǎn)，即它們基本上是稀疏的（時域，特別是頻域），或可壓縮的，從而使得在低于Nyquist率下抽樣變?yōu)榭赡?。調(diào)幅信號頻譜是稀疏的通信中的多帶信號也都是稀疏的

我們能否直接“感知”信號

中重要的成分而對其采集、對不重要的成分不采集呢？這似乎是一個不切實(shí)際的想法，但它確實(shí)是壓縮感知想要解決的問題。問題的關(guān)鍵是，如何由原來的關(guān)注最高頻率轉(zhuǎn)變?yōu)殛P(guān)注信號的“稀疏性”。DonohoD.L.認(rèn)為經(jīng)典的抽樣定理是“錯誤”的，當(dāng)然，它不是真正的錯誤，而是“心理”上的錯誤，即它促使人們在本來不用那么多數(shù)據(jù)的場合仍然想著要采集非常大量的數(shù)據(jù)。CS為新的信號抽樣策略提供了理論基礎(chǔ)，它用遠(yuǎn)小于Nyquist率的抽樣頻率對信號抽樣，然后利用算法來對原信號進(jìn)行準(zhǔn)確，或近似恢復(fù)。這等效于將對信號的抽樣和壓縮合并為一步實(shí)現(xiàn)。CS能工作的基礎(chǔ)是信號中存在的稀疏性。壓縮感知壓縮傳感compressivesensingcompressedsensingcompressivesampling（壓縮抽樣）sparserecovery（稀疏恢復(fù)）”。CS定義15.1.1

如果向量

最多只有

個非零元素，

則稱

是

稀疏的。所有

稀疏信號

的集合記為

，即

維

Euclidean空間等效：都表示

中非零元素的個數(shù)。顯然，越小，中非零元素越少，越稀疏待“抽樣”（重建）信號；未知，可能是模擬，可能是數(shù)字CS問題的描述：令：測量（已知）信號；它總是數(shù)字的。測量矩陣，長方陣目的：由測量重建出；測量“系統(tǒng)”，目的是由測量重建出；

欠定方程，未知數(shù)的個數(shù)大于方程的個數(shù)，因此有無窮多解。但如限制是稀疏的，則方程以大概率有唯一解。為唯一地求解

，必須對方程施加約束條件：目標(biāo)函數(shù)解的名稱subjectto令：最小平方解偽逆，基于范數(shù)最優(yōu)解

最小

范數(shù)解等效于最小平方解，它測量的是信號的能量，著眼于信號整體的平方誤差最小，因此，得到的解不具有稀疏性，無法用于稀疏信號的恢復(fù)。關(guān)于這一點(diǎn)，我們也可以這樣來理解：由于

使用了

的所有列向量，因此，它以平均的方式包含了

的“整體”信息，這一結(jié)果傾向于平滑每一個列向量給出的貢獻(xiàn)，因此得到的

不再是稀疏信號。

顯然，一個合理的、自然的選擇是利用范數(shù)。含意：在所有滿足線性方程組

的解中，選擇非零元素最少的一個作為我們需要恢復(fù)的

。

問題：

是稀疏的，但是，這個非零元素的位置是不知道的，有

個可能的分布，因此可有個滿足不定方程。

因此，基于范數(shù)的求解是幾乎不可能的，NP－Hard問題，組合最優(yōu)化問題。NP：Non-DeterministicPolynomial（非確定多項(xiàng)式）為解決NP－Hard問題，人們提出了兩個方法：一、基追蹤（basispursuit，BP）

算法用取代：CS中的重要內(nèi)容。二、貪婪（greedyalgorithms）算法

－正交匹配追蹤：直接求，但不是

優(yōu)化算法，而是迭代算法。對實(shí)際問題，在時域，或空域很少是稀疏的，但他們在時、空域具有相關(guān)性，因此經(jīng)常需要考慮變換域的壓縮感知：目的：由測量重建出；由做反變換得正交變換測量矩陣主要取決于

對信號的感知分兩種情況，一是信號在時域（或空域）是稀疏的，那么對信號的測量也在時域（或空域）進(jìn)行；二是信號在變換域是稀疏的，那么測量在變換域進(jìn)行?？傊珻S測量的是稀疏信號。且

被

看作已知的，而稀疏信號是靠優(yōu)化算法求解出來的?！熬幋a器（encoder）”又稱“解碼器（decoder）”又稱表示映射CS的文獻(xiàn)中記為問題可簡潔地表為CS中的一些核心問題：什么條件下：？問題；什么條件下：？問題；什么條件下：？和等效問題；所有上述問題的回答，都取決于測量矩陣所具有的性質(zhì)。

CS的一些特點(diǎn)：（1）由于

，因此CS對信號的測量是將信號的

采集和壓縮結(jié)合在了一個步驟，避免了經(jīng)典抽樣需

要先采集、后壓縮的分步實(shí)現(xiàn)?；蛘哒f，測量的數(shù)

據(jù)

只正比于壓縮后數(shù)據(jù)的長度，它遠(yuǎn)小于原數(shù)

據(jù)的長度；（2）測量值

不是信號

本身，而是高維（

）信號

到低維（

）的投影，或者說，

的每一個值

都是

的所有值的組合；（3）測量是非自適應(yīng)的，即測量矩陣

不隨

而變化；（4）如果信號在傳感器端的采集是昂貴的，費(fèi)時的，

危險的，或不可能的，而在接收端的計(jì)算（即恢

復(fù)）是低廉和容易實(shí)現(xiàn)的，那么CS是特別有應(yīng)

用價值的。模擬/信息轉(zhuǎn)換的應(yīng)用。（5）用低維的

來代替（或恢復(fù)）高維的

，這在

數(shù)字信號和數(shù)字圖像的壓縮、識別、稀疏表示及

重建等領(lǐng)域都有著廣泛的應(yīng)用。CS理論依賴于三個要求：（1）信號

，或其在變換域是稀疏的;（2）測量矩陣

要滿足一定的性質(zhì)；（3）高效的恢復(fù)算法。CS理論的主要內(nèi)容：（1）信號的稀疏表示；（2）為保證唯一地由

恢復(fù)

稀疏信號

，？（3）測量矩陣

要滿足的性質(zhì)及其設(shè)計(jì)；（4）信號恢復(fù)的算法；（5）如何得到？A/I問題；（6）CS的應(yīng)用。說明：CS希望解決對模擬信號以低抽樣率抽樣，并已取得了可喜的成果。但目前主流的CS的理論框架還主要針對離散信號。其原因：一是有利于應(yīng)用經(jīng)典的數(shù)學(xué)理論（矩陣和向量）；二是CS理論越發(fā)展和越完善，AIC距離實(shí)際應(yīng)用也越近；三是在實(shí)際應(yīng)用中我們也可以“直接”得到離散信號，如數(shù)碼相機(jī)和CT圖像。由于CS的理論框架目前主要是針對離散信號的，因此，除了模擬/信息轉(zhuǎn)換這一最重要的應(yīng)用領(lǐng)域以外，CS在針對數(shù)字信號和數(shù)字圖像的領(lǐng)域也已經(jīng)并正在獲得廣泛的應(yīng)用，如醫(yī)學(xué)成像、計(jì)算生物學(xué)、地球物理、人工智能、機(jī)器學(xué)習(xí)等。[Can06a]Candès.E.J.,Romberg.JandTao.T.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation.IEEETrans.Inform.Theory,52(2):489–509,2006.[Don06]Donoho.D.L.Compressedsensing.IEEETrans.Inform.Theory,52(4):1289–1306,2006.兩篇重要論文：被認(rèn)為是CS的起源－2006DavidLDonoho教授：1957年生，現(xiàn)為斯坦福大學(xué)統(tǒng)計(jì)學(xué)系教授，2013年邵逸夫數(shù)學(xué)科學(xué)獎獲得者。EmmanuelJ.Candès教授：1970年生，現(xiàn)為斯坦福大學(xué)數(shù)學(xué)、統(tǒng)計(jì)學(xué)、電工程學(xué)教授。TerenceTao（陶哲軒）教授：1975生。華裔澳籍?dāng)?shù)學(xué)家，UCLA教授。15.2預(yù)備知識

矩陣的零空間

矩陣的

向量的范數(shù)

凸優(yōu)化與線性規(guī)劃15.2.1矩陣的零空間（nullspace，NSP）NSP來自于線性方程組解的結(jié)構(gòu)，考慮如下的線性方程組：該方程組的解有如下情況：（1）如果，滿秩，有唯一解；（2）如果，滿秩，齊次方程組只

有零解，即；

（3）如果，齊次方程組有基礎(chǔ)解系，。

是線性無關(guān)的，且的所有其它解都可由其

線性組合來得到。

可看作一個空間的基，該空間就是矩陣

的零空間，記為

。（4）若，令，若

則有解；假定

是它的一個特解，

是

的一個元素，則

也是方程組的

解，當(dāng)

取遍

中的所有元素時，我們就

得到方程組

的所有解。

注意：空間中的任一元素都使得，

因此，中的元素又稱為矩陣的“化

零向量”。我們通常認(rèn)為是行滿秩的，因

此，的維數(shù)為。又稱核空間：定義15.2.1：已知矩陣

，其零空間定義為已知矩陣

，其值域定義為顯然例已知矩陣求的零空間維數(shù)和值域的維數(shù)，并討論方程組

的解的形式。詳細(xì)內(nèi)容見教材

由15.1節(jié)的討論可知，

，由得到。如果，基本的要求是

，

反之亦然。即我們要求映射和恢復(fù)是一對一的，這即是壓縮感知中的唯一性問題。否則，我們將無法從重建出。令，如果，則化零向量，即線性方程組求解

矩陣零空間，目的：用到壓縮感知

若保證映射和恢復(fù)的唯一性，

的零空間一定要具有一定的性質(zhì)。下面給出的是最基本的一個。定義15.2.2矩陣

被稱為具有

階零空間性質(zhì)（nullspaceproperty，NSP），如果式中表示空間，因?yàn)椋纱嗽撌降暮x是

的零空間中不包含

稀疏的向量。它又可表為即

的零空間和

稀疏向量的集合沒有交集之所以說定義15.2.2是矩陣零空間性質(zhì)中最基本的一個，是因?yàn)樵趬嚎s感知中還要考慮“半稀疏（semi-sparse）信號的壓縮問題。所謂半稀疏信號，是指對

，它有個元素的絕對值起到主導(dǎo)作用（即較大）。但其它個元素并非全部為零，而是有很小的值。這一類信號又稱可壓縮信號，它也可以看作稀疏信號被噪聲污染后形成的。因此，對這一類信號的恢復(fù)問題，零空間性質(zhì)的要求要嚴(yán)一些。粗略地說，在的零空間中除了要不包含稀疏及稀疏的向量外，還要不包含極易壓縮的向量。定義15.2.3即是針對這一類信號的恢復(fù)問題而提出的。定義15.2.3矩陣

被稱為具有常數(shù)

的

階零空間性質(zhì)，如果對

的任意化零向量

和任意滿足

的下標(biāo)集合都成立。符號說明：下標(biāo)集合

的補(bǔ)向量和在由指定的位置上的元素相同，而其余的元素（由

指定）是零；同理，矩陣

是矩陣

的子矩陣，其列是由

指定的

的列。

例如：如果，仍存在常數(shù)

使上述定義成立，則說具有階NSP性質(zhì)。另外，NSP的定義不唯一，如說明：CS是近十年來新發(fā)展的學(xué)科領(lǐng)域，因此一些定義和定理在文獻(xiàn)中的描述還沒有統(tǒng)一。

NSP實(shí)際上是對矩陣

的零空間中向量的元素的分布提出了要求，即它的非零元素不能集中分布在一個小的子集中。

結(jié)論：滿足

階零空間性質(zhì)的向量

的非零元素的個數(shù)應(yīng)大于

，而且不小于。等效說，如果

滿足零空間性質(zhì)，那么，在其零空間

中唯一的

稀疏向量應(yīng)是

。矩陣的NSP在CS中有著重要的應(yīng)用

由式（15.2.3）的

階零空間性質(zhì)可以想到，因?yàn)?/p>

，那么

的列向量中一定有若干列是線性相關(guān)的。為了避免

的情況出現(xiàn)，除了要求其零空間中不包含

稀疏及

稀疏的向量外，還要對其線性相關(guān)的列數(shù)給以控制。這就是下面要討論的矩陣

。

矩陣的

又稱為矩陣的

稀疏度

。15.2.2矩陣的

定義15.2.4

矩陣

的

是其最小的

線性相關(guān)的列數(shù)，記為

。上界和下界含意：在矩陣

所有的列中，最少可以找出多少列

使其滿足線性相關(guān)性。這里之所以考慮“最

小”，是因?yàn)橄蛄吭蕉嘣饺菀诐M足線性相關(guān)。矩陣的秩和spark都用來描述矩陣的基本特征，但二者有明顯的不同。矩陣的秩是其最大線性無關(guān)的列數(shù)，而spark是其最小線性相關(guān)的列數(shù)，一個是“最大”，一個是“最小”，一個是“線性無關(guān)”，一個是“線性相關(guān)”。另外，對

矩陣，求出其秩的方法是通過初等變換將其轉(zhuǎn)換為一個階梯矩陣，其不等于零的行就是它的秩，這是一個“順序”的計(jì)算的過程，計(jì)算復(fù)雜性為

。而求解其spark是一個組合過程，計(jì)算復(fù)雜性為

。由式（15.2.6）可知，若

的

越大，那么其

也越大，這就是說，

的線性無關(guān)的列數(shù)就越多。這樣，將映射為，保留的

的信息越多，結(jié)果是越有利于由

準(zhǔn)確重建

。因此矩陣的

是描述矩陣的一個重要參數(shù)。在后面的討論中，它和NSP一樣都要反復(fù)用到。15.2.3向量的范數(shù)時，“真范數(shù)”真范數(shù)滿足左邊四個性質(zhì)

時的范數(shù)有其用處，但不再滿足上述四個關(guān)系，因此，

這時的范數(shù)稱為“準(zhǔn)范數(shù)quasinorm）”，應(yīng)用最多的是

時的范數(shù)

：包含了非零元素個數(shù)的三個表達(dá)方式表示的“勢（cardinality）”范數(shù)的單位球（unitball）:

的單位球是和坐標(biāo)軸重合的十字架（不包括原點(diǎn)）

的單位球是菱形，其頂點(diǎn)在坐標(biāo)軸上

的單位球是一個圓，圓心在原點(diǎn)

時的單位球是內(nèi)凹的

時的單位球是外凸的向量范數(shù)單位球的形態(tài)：有什么用處？假定：，稀疏。含意？假定得到的一個近似，考查，在下，近似性能

應(yīng)位于二維平面的直線上那種情況近似好？再考慮：，含意？

范數(shù)可給出全局最優(yōu)解，

但給不出稀疏解；

范數(shù)能給出稀疏解；

的解的幾何分布：

是個超平面的交集，

維數(shù)為，記為轉(zhuǎn)化零空間（translatednull～）仿射空間（affine～）二者有相同的

，

不同的。前者最稀疏！

范數(shù)球的位置：

范數(shù)可以提升信號的稀疏性，其求解又等效于凸優(yōu)化問題。在CS起到了非常重要的作用。15.2.4凸優(yōu)化與線性規(guī)劃線性規(guī)劃問題的數(shù)學(xué)描述：目標(biāo)函數(shù)約束條件:變量滿足右式的稱為“可行點(diǎn)”，其集合稱為“可行域”。

并非所有的連續(xù)可微函數(shù)都有最優(yōu)解，即使有，也不一定唯一。然而，如果上式的目標(biāo)函數(shù)是凸函數(shù)，而且可行域也是凸集，則上式的優(yōu)化問題的任何最優(yōu)解必然是全局最優(yōu)解。另外，對于凸集上的凸函數(shù)的最優(yōu)化，存在唯一的全局最優(yōu)解。因此，凸集與凸函數(shù)在最優(yōu)化的理論中有著重要的作用。一個可行點(diǎn)若滿足則稱

為上面優(yōu)化問題的全局最優(yōu)解定義15.2.5設(shè)

為

中的一個集合，如果對

內(nèi)的任意兩點(diǎn)

，聯(lián)結(jié)它們之間的線段仍然屬于

，則稱

為一個凸集。即凸集非凸集

凸優(yōu)化的最優(yōu)解應(yīng)該位于凸集的頂點(diǎn)。由于可行域非空的線性規(guī)劃就是一個凸規(guī)劃，因此可得出有關(guān)線性規(guī)劃最優(yōu)解的結(jié)論，即（1）如果線性規(guī)劃問題有最優(yōu)解，那么最優(yōu)解在可行域的頂點(diǎn)中確定；（2）如果可行域有界、且可行域只有有限個頂點(diǎn)，則最優(yōu)解存在，并且只需在這有限個頂點(diǎn)中確定。

線性規(guī)劃問題的求解有著很長的歷史，經(jīng)典的方法是由Dantzig.G.B在1947年提出的單純形法（simplexmethod）和由Karmarkar于1984年提出的內(nèi)點(diǎn)法（interiorpointmethod）。15.3信號的稀疏表示稀疏表示：用高效的算法在保持信號信息不變的情況下最大可能的降低信號的維數(shù)，這是對信號建立最佳稀疏模型問題。文獻(xiàn)認(rèn)為信號的稀疏模型是“奧卡姆剃刀（Occam'sRazor）”問題的又一個例子，即面對一個信號的多種表達(dá)方式，最簡單的一種即是最好的選擇。15.3.1稀疏信號及可壓縮信號

我們希望信號越稀疏越好，這有利于信號的壓縮、存儲、特征提取及應(yīng)用。

維向量（信號）如果只有個非零元素，則稱是稀疏的，記做記為非線性模型中的子空間非線性空間：

個子空間的并集

如果信號不是稀疏的，但如果可以由一個稀疏信號很好的近似，則稱該信號是可壓縮的。

范數(shù)下的最佳

稀疏近似誤差為顯然，若取了的個最大元素，而其余元素為零，則，稱為的“最佳項(xiàng)近似”。定義15.3.1

將正交變換系數(shù)排序：

，

，如果系數(shù)滿足

，則稱是可壓縮的。15.3.2信號稀疏表示的基本方法信號在時域和空域一般是非稀疏的，但物理信號具有很強(qiáng)的相關(guān)性，因此，在變換域（如頻域）通常是稀疏的。之前，人們習(xí)慣用的是正交變換：：正交矩陣DFT（離散傅里葉變換）DCT（離散余弦變換）DWT（離散小波變換）正交變換的優(yōu)點(diǎn)：去除信號中的相關(guān)性；將信號能量濃縮到少數(shù)系數(shù)上；計(jì)算簡單“優(yōu)雅(elegance）”的變換，JPEG，MPEG，正交變換的不足：當(dāng)信號中包含多種模式時，利用單一的正交基不能很好地“匹配”所要分解的信號，因此也不能有效地實(shí)現(xiàn)信號的稀疏表示。

例如，DFT對諧波信號、均勻平滑的信號非常有效，但是當(dāng)信號中存在有間斷點(diǎn)和尖脈沖時，傅里葉變換的效果就不理想，無法得到好的稀疏表示。說明單獨(dú)的一個正交基不能同時匹配兩種不同類型的信號。再例如，一幅圖像有平滑的區(qū)域，也有劇烈的邊緣。小波變換在表示具有有限斷點(diǎn)的平滑分段連續(xù)信號方面是最優(yōu)的，對具有復(fù)雜紋理結(jié)構(gòu)的圖像也具有很強(qiáng)的優(yōu)勢，但由于圖像的邊緣具有不連續(xù)性，并且是按空間分布的，因此，小波在處理圖像邊緣方面的效果不理想。對含有多種模式的信號，應(yīng)該用多個“基函數(shù)”構(gòu)成一個混合的“基”來自適應(yīng)信號的特征，以匹配信號中的不同模式，并取得最佳的稀疏效果。該混合的“基”稱為“字典（dictionary）”。向量，“原子”變換矩陣，長方陣已知信號

待求稀疏信號未知數(shù)大于已知數(shù)，欠定問題，無窮多解有唯一解，“NP”難，“匹配追蹤”變換矩陣“基追蹤”算法重大進(jìn)展稀疏表達(dá)和壓縮感知類似。一個問題的兩個方面：已知信號

待求稀疏信號