現代信號處理教程（第三版）課件 第15章 壓縮感知的基礎理論

第五篇壓縮感知（CS）第15章壓縮感知的基礎理論第16章模擬/信息轉換及CS的應用

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

然而，物理世界的信息（信號和圖像）是時間和空間的連續函數（模擬）。DSP能處理的是數字信號。將模擬信號和模擬圖像轉變為數字化的形式需要抽樣，即模/數（A/D）轉換。在數字信號處理中，經典的抽樣定理，即Shannon抽樣定理被譽為A/D轉換的金標準。DSPA/D打開了由模擬世界進入數字世界的大門！

Shannon抽樣定理：

設

是有限帶寬的，抽樣頻率

至少要是其最高頻率

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

精確地恢復（或重建）出

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

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

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

和存儲的負擔。JPEGMPEGMP3ZIP對模擬信號抽樣，真的需要嗎？

絕大部分物理信號有一個基本特點，即它們基本上是稀疏的（時域，特別是頻域），或可壓縮的，從而使得在低于Nyquist率下抽樣變為可能。調幅信號頻譜是稀疏的通信中的多帶信號也都是稀疏的

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

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

如果向量

最多只有

個非零元素，

則稱

是

稀疏的。所有

稀疏信號

的集合記為

，即

維

Euclidean空間等效：都表示

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

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

，必須對方程施加約束條件：目標函數解的名稱subjectto令：最小平方解偽逆，基于范數最優解

最小

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

使用了

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

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

不再是稀疏信號。

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

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

。

問題：

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

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

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

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

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

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

對信號的感知分兩種情況，一是信號在時域（或空域）是稀疏的，那么對信號的測量也在時域（或空域）進行；二是信號在變換域是稀疏的，那么測量在變換域進行。總之，CS測量的是稀疏信號。且

被

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

CS的一些特點：（1）由于

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

采集和壓縮結合在了一個步驟，避免了經典抽樣需

要先采集、后壓縮的分步實現。或者說，測量的數

據

只正比于壓縮后數據的長度，它遠小于原數

據的長度；（2）測量值

不是信號

本身，而是高維（

）信號

到低維（

）的投影，或者說，

的每一個值

都是

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

不隨

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

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

復）是低廉和容易實現的，那么CS是特別有應

用價值的。模擬/信息轉換的應用。（5）用低維的

來代替（或恢復）高維的

，這在

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

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

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

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

恢復

稀疏信號

，？（3）測量矩陣

要滿足的性質及其設計；（4）信號恢復的算法；（5）如何得到？A/I問題；（6）CS的應用。說明：CS希望解決對模擬信號以低抽樣率抽樣，并已取得了可喜的成果。但目前主流的CS的理論框架還主要針對離散信號。其原因：一是有利于應用經典的數學理論（矩陣和向量）；二是CS理論越發展和越完善，AIC距離實際應用也越近；三是在實際應用中我們也可以“直接”得到離散信號，如數碼相機和CT圖像。由于CS的理論框架目前主要是針對離散信號的，因此，除了模擬/信息轉換這一最重要的應用領域以外，CS在針對數字信號和數字圖像的領域也已經并正在獲得廣泛的應用，如醫學成像、計算生物學、地球物理、人工智能、機器學習等。[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.兩篇重要論文：被認為是CS的起源－2006DavidLDonoho教授：1957年生，現為斯坦福大學統計學系教授，2013年邵逸夫數學科學獎獲得者。EmmanuelJ.Candès教授：1970年生，現為斯坦福大學數學、統計學、電工程學教授。TerenceTao（陶哲軒）教授：1975生。華裔澳籍數學家，UCLA教授。15.2預備知識

矩陣的零空間

矩陣的

向量的范數

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

有零解，即；

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

是線性無關的，且的所有其它解都可由其

線性組合來得到。

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

的零空間，記為

。（4）若，令，若

則有解；假定

是它的一個特解，

是

的一個元素，則

也是方程組的

解，當

取遍

中的所有元素時，我們就

得到方程組

的所有解。

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

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

零向量”。我們通常認為是行滿秩的，因

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

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

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

的解的形式。詳細內容見教材

由15.1節的討論可知，

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

，

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

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

若保證映射和恢復的唯一性，

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

被稱為具有

階零空間性質（nullspaceproperty，NSP），如果式中表示空間，因為，由此該式的含義是

的零空間中不包含

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

的零空間和

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

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

被稱為具有常數

的

階零空間性質，如果對

的任意化零向量

和任意滿足

的下標集合都成立。符號說明：下標集合

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

指定）是零；同理，矩陣

是矩陣

的子矩陣，其列是由

指定的

的列。

例如：如果，仍存在常數

使上述定義成立，則說具有階NSP性質。另外，NSP的定義不唯一，如說明：CS是近十年來新發展的學科領域，因此一些定義和定理在文獻中的描述還沒有統一。

NSP實際上是對矩陣

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

結論：滿足

階零空間性質的向量

的非零元素的個數應大于

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

滿足零空間性質，那么，在其零空間

中唯一的

稀疏向量應是

。矩陣的NSP在CS中有著重要的應用

由式（15.2.3）的

階零空間性質可以想到，因為

，那么

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

的情況出現，除了要求其零空間中不包含

稀疏及

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

。

矩陣的

又稱為矩陣的

稀疏度

。15.2.2矩陣的

定義15.2.4

矩陣

的

是其最小的

線性相關的列數，記為

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

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

使其滿足線性相關性。這里之所以考慮“最

小”，是因為向量越多越容易滿足線性相關。矩陣的秩和spark都用來描述矩陣的基本特征，但二者有明顯的不同。矩陣的秩是其最大線性無關的列數，而spark是其最小線性相關的列數，一個是“最大”，一個是“最小”，一個是“線性無關”，一個是“線性相關”。另外，對

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

。而求解其spark是一個組合過程，計算復雜性為

。由式（15.2.6）可知，若

的

越大，那么其

也越大，這就是說，

的線性無關的列數就越多。這樣，將映射為，保留的

的信息越多，結果是越有利于由

準確重建

。因此矩陣的

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

時的范數有其用處，但不再滿足上述四個關系，因此，

這時的范數稱為“準范數quasinorm）”，應用最多的是

時的范數

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

的單位球是和坐標軸重合的十字架（不包括原點）

的單位球是菱形，其頂點在坐標軸上

的單位球是一個圓，圓心在原點

時的單位球是內凹的

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

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

范數可給出全局最優解，

但給不出稀疏解；

范數能給出稀疏解；

的解的幾何分布：

是個超平面的交集，

維數為，記為轉化零空間（translatednull～）仿射空間（affine～）二者有相同的

，

不同的。前者最稀疏！

范數球的位置：

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

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

為上面優化問題的全局最優解定義15.2.5設

為

中的一個集合，如果對

內的任意兩點

，聯結它們之間的線段仍然屬于

，則稱

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

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

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

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

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

個子空間的并集

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

范數下的最佳

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

將正交變換系數排序：

，

，如果系數滿足

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

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

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

待求稀疏信號

變換矩陣，

待重建高維信號已知信號

測量矩陣，欠定；NP-Hard；長方陣：基追蹤；匹配追蹤壓縮感知

稀疏恢復（sparserecovery）

權威期刊ProceedingsoftheIEEEvol.98，No.6，2010專輯：ApplicationsofSparseRepresentationandCompressiveSensing

把稀疏表示和壓縮感知合在一起進行討論字典應具有的功能定位功能；多分辨率功能；自適應功能；幾何不變性和過完備功能。解析字典Curvelets變換Contourlets變換Bandelets變換學習字典MethodofOptimalDirections；UnionofOrthobases；GeneralizedPCA；K-SVDAlgorithm。如何從

中選最優的

個原子。稀疏表達兩個核心問題如何設計最優字典

；（1）信號的稀疏表示；（2）對

稀疏信號，測量數

的最小值，即

取多少才能保證唯一地由

恢復出

？（3）測量矩陣

應具有的性質及

的設計；

（4）信號恢復的算法（基追蹤，正交匹配追蹤）；（5）如何得到測量

？（6）CS的應用。CS的核心內容

CS的應用：

模擬/信息轉換，A/IC（1）隨機解調（RD）

；（2）調制寬帶轉換器（MWC）；（3）Xampling已提出的方案CS可應用于一切需要由某些線性測量的結果來重建信號和圖像的領域，特別是當完備的測量的獲得是昂貴的，長時間的，困難的，危險的，或者是不可能的場合。如CT，MRICS和A/IC的理論正在發展中！CS的其他應用領域：圖像壓縮；醫學成像；計算生物學；地球物理；超光譜成像（hyperspectralimaging）；壓縮雷達成像；天文學、通信、遙感；計算機工程；表面計量學（surfacemetrology）等稀疏表達在生物醫學工程中的應用醫學圖像圖像壓縮；圖像去噪；圖像識別；圖像修復；圖像編碼；應用最多的：MRI，超聲，CT，面部識別醫學信號盲源分離；腦電中癲癇特征波的檢測；誘發腦電提取；腦電的源定位；心電特征（P，R，T）檢測。

15.4測量矩陣需要滿足的性質

的NSP約束等距性質（RIP）相干性（coherence）（1）是準確稀疏的；（2）測量過程不存在噪聲；本節討論的是：

矩陣的NSP不好應用，spark的求出是一組合問題，也不好應用。此外，在存在噪聲的情況下，由NSP和spark給出的重建往往缺乏魯棒性，為此，人們又提出了一些新的參數：最著名的是矩陣的約束等距性質（restrictedisometryproperty，RIP）及相干性。15.4.1

測量矩陣的約束等距性質定義15.4.1

令整數

對所有的

稀疏信號

，等距常數

是滿足的最小標量，如果，則稱滿足

階的RIP并具有等距常數

。RIP的概念最初由EmmanuelJ.Candès和TerenceTao在文獻[Can06b]中提出，當時稱為均勻不定原理(uniformuncertaintyprinciple，UUP)，后來文獻[Can05]將其重新定義為RIP。（1）定義要求對所有的

都成立，在

維空間中有

個這樣的

。當然，實際待求的只有一個。（2）不嚴謹地說，若

不太接近于1，則稱

RIP

粗略地看，（15.4.1a）式定義的RIP是想保證

和測量的能量沒有太大的差距。現對RIP給出更多的解釋。（3）如果保范變換？但現在

是扁的長方陣，隱含意思是：從

中任取

列所形成的

子矩陣應該接近于正交陣。顯然

越小，該子矩陣接近正交陣的程度越好。因此，當

投影到

的行向量上后，具有RIP性質的

就近似地保護了它的Euclidean范數

（或能量）。上述結論又意味著

稀疏信號不會落在

的零空間。這一點很重要，否則無法恢復該稀疏信號。為強調該子矩陣，RIP又可定義：

（4）：方陣，稱為Gram矩陣。若滿足RIP，

則

正定，對，則該矩陣的特征值

位于之間。（5）RIP定義的另一含意：如果

滿足

階的RIP，

則定義近似保護了任意兩個

稀疏向量之間的距離。如果：

：

是指下標集合的勢

時仍滿足RIP定義的最小常數。

的取值也應該在

之間。這時，我們說

具有

階的RIP性質。類似的，我們還可以定義

，

等。（6）如果

滿足

階的RIP并具有等距常數

，那

么，對任意的

，

，自動地具有

階

的RIP性質并具有等距常數

。（7）如果

“感知”的是變換系數

，那么RIP定義

中的矩陣

應該換為矩陣

。這時，

具有

階的RIP。（8）將RIP的定義和標架的定義相比較，會二者有非常相

似之處。它們都給出了信號

在通過非正交陣

變換前后能量的約束關系。

上面8個解釋說明：測量矩陣

的RIP性質保證了通過變換

前后信號的能量及幾何結構基本保持不變，同時也保護了兩個

稀疏信號在變換前后的距離，從而使得

稀疏信號的準確恢復成為可能，也保證了恢復的穩定性。為了求得稀疏信號的準確恢復，人們希望在盡可能小的測量數目

的情況下，尋求具有較小的等距常數

和較大稀疏度

的測量矩陣

。15.4.2測量矩陣的相干性定義15.4.2測量矩陣

的相干性定義為將的列歸一化越小，中不相關（或獨立）的列越多，中保留的信息越多，越有利于的恢復。因此，在構造時，希望它具有盡量小的相干性。下面的定理給出了的NSP，spark，相干性之間的關系，也給出了測量數

的約束。定理15.4.1如果

滿足

階的RIP并具有等距常數

，則

具有

階零空間

性質，且RIP常數證明見教材，用到兩個引理。定理說明：如果矩陣

滿足

階的RIP，則它也同時滿足

階的NSP。RIP給出了比NSP更為嚴格的條件，可以用來考慮存在噪聲情況下信號的恢復。

引理

假定

，則

稀疏信號三個范數之關系定理15.4.2對

，下面的關系成立

至少有列線性相關滿足spark定義定理15.4.3對任意的

，其相干性和spark

有如下關系該式給出了一個重要的關系，即

的相干性越小，其spark越大，

線性無關的列向量越多，由這些列構成的

的子矩陣越接近于正交。這正是我們所希望的。定理15.4.4記

的相干性為

，假定其每一列的

范數都歸一化為1，則對所有的

，

具有

階RIP并具有等距常數：測量矩陣和正交矩陣之間的互相干性也有著重要的應用，列的范數歸一化后，其定義為：測量兩個矩陣之間的最大相關性15.4.3解唯一性的條件

解唯一性：即

最小，或如何保證

？直觀理解：希望：對兩個不同的：必須有：因為：結論：否則無法恢復：將出現：含意？

該式又可簡單的解釋為：為保證解的唯一性，矩陣

的零空間中必不包含稀疏的向量。解的唯一性，有多種描述方式，如定理15.4.5

對任意的

和

，當且僅當

時，測量系統

有唯一解

。

該定理的一個等效說法是:如果

的任意

列都是線性無關的，那么，任意

稀疏信號

都可以唯一地由

來恢復。由于：的行秩是，由定理，必須有此結論很重要，指出，為恢復出稀疏信號，測量數的長度不能小于。定理15.4.6對任意的

，如保證

，

則下述說法等效：（1）對所有

，存在一

，使得

；

（2）：是正定矩陣；（3）；（4）對任意具有

的下標集合

，矩陣

的秩為

；定理15.4.7對任意的

和，如果

其解

滿足如下關系則測量系統

有唯一解

。對一個給定的感知矩陣

，該式給出了所能感知的信號稀疏水平的上限。定理15.4.8如果

滿足階RIP，且

，則對所有

，有定理15.4.8是直觀的：因為如果

，由RIP的定義，

將有

列線性相關，則存在一

使

。令

，有

，那么

就不是唯一解。15.4.4解唯一性的條件定理15.4.9如果

滿足階RIP，且

，，則對所有

，有對比定理15.4.8和15.4.9可以看出：

保證

保證結論合理：利用

范數來代替

范數是放寬了最優化的條件，當然對測量矩陣的要求要變得嚴一些。要求要求其實：可看作和等效的條件

解的唯一性也可用NSP給出：定理15.4.10給定

，當且僅當滿足

階零空間性質時，任意稀疏向量

都是唯一最小范數解。

實際信號在時域多不是稀疏的，而經正交矩陣變換后多是稀疏的，因此，研究測量矩陣

應具有的性質同樣是重要的。對該問題，用的最多的是互相干

。下面的定理給出了

和測量數

之間的關系以及保證

解唯一性的條件。定理15.4.11假定信號

在正交基

下的變換系數

是

稀疏的，且

是對

的均勻和

隨機測量，如果保證則優化問題以大概率有準確解。顯然，越小，需要的越少。若則以的測量可恢復長度為的。文獻指出:RIP等效于要求

的行向量

不能由

的列向量

線性表出，反之亦然。

隨機矩陣15.4.5和解等效的條件前面已指出：是、等效的條件定理15.4.12令

是一行滿秩矩陣，如

果一個解

存在并滿足則是

和

問題的唯一解。15.4.6測量邊界前面指出，為保證

解唯一性，測量數不能小

。定理15.4.10通過互相干

給出了

和

的關系。

在CS的文獻中

又稱為測量邊界。定理15.4.13若

滿足

階RIP并

，則

更一般關系定理15.4.5～15.4.13給出了

，

唯一、等效條件及和的NSP、spark、RIP和之間的關系。很重要15.4.7關于

解唯一性的進一步說明

由于CS是近十年來新發展起來的領域，理論的發展有一個不斷完善的過程，因此定理15.4.5～15.4.13所描述的內容及NSP的定義在文獻上不盡相同，特別是唯一性的條件的表述，如：文獻[Can05]：文獻[Can06c]：文獻[Can08b]：文獻[Fou09]：[Cai10]：15.4節的公式和結論都較多，現總結如下：（15.4.11b）（15.4.9）需要指出：上面討論的各個定理都是針對

是準確稀疏信號和無測量噪聲情況下的結論，在不是稀疏信號和存在測量噪聲情況下的信號恢復問題是下面兩小節要討論的內容。

15.5可壓縮信號的恢復以上討論，假定，這是理想的信號模型。實際信號多是近似稀疏，或可壓縮的。因此，研究可壓縮信號的CS更有意義。對可壓縮信號近似誤差將中最大個元素按大小排在前面，并賦予，再令其它元素為零。最佳項近似對非準確稀疏的可壓縮信號：，近似程度？特別關心和最佳項近似誤差的關系：重點關心如下關系：（1）.若是稀疏的，則左邊＝0，無誤差恢復；（2）.否則，則左邊的誤差和右邊的最佳項近

似誤差建立了聯系。（A）定理15.5.1令

表示

的任一解碼算

法，如果

和

滿足（A）式，則

滿足

階NSP。反之，如果滿足

階NSP，則（A）式的近似誤差關系成立。因此滿足

階NSP是（A）式成立的充要條件。上述討論的是任一解碼算法，更關心定理15.5.2令

是

解，對

，如果

滿足

階的RIP且

，則下面兩式成立該定理是CS中一個重要和著名的定理，由Candès在08年提出并給出證明。文獻[Bar13]又給出較詳細的證明。

15.6噪聲情況下的信號恢復

矩陣

對

測量時，會存在誤差：可能來于傳感器，或舍入誤差和量化誤差。這時，“感知”模型變成誤差向量記在有噪聲情況下，關心近似程度定義15.6.1令:，,，若則稱編碼－解碼對是C－穩定的。該定義說明一簡單事實，即測量誤差在恢復過程中其影響不會任意大，它將不超過誤差自身的

范數。

定理15.6.1如果:是C－

穩定的，則

對所有的

，下述關系成立RIP和C－穩定的關系定理15.6.2如果

滿足

階的RIP且

，令

及

，再令

是滿足的最優解，則式中近似誤差無噪聲時信號恢復的誤差噪聲引起，正比于噪聲能量的含意：15.7測量矩陣的構造用于：

稀疏信號；

可壓縮信號；

含噪信號準確、近似準確恢復性能描述：NSPsparkRIP，

要滿足定理15.4.5－15.4.13所提要求。小的RIP常數和相干性，大的spark。但這些性能的測量比較困難：滿足RIP？需要考察由于非零元素位置不同而可能有的

個

稀疏信號

是否都滿足RIP定義。研究發現，如果

是隨機矩陣，則以大概率有RIP性質。15.7.1Johnson–L引理和濃縮測量的概念15.7.2隨機測量矩陣（1）高斯測量矩陣每一個元素都是高斯分布，且I.I.D（2）伯努利測量矩陣或者可以用濃縮不等式證明，高斯和伯努利矩陣以大概率具有RIP性質。（3）亞高斯（subgaussian）測量矩陣

：高斯分布

：亞高斯分布

亞高斯種類很多，在一定的條件下，高斯分布、伯努利分布和均勻分布都可以看作是亞高斯分布：（1）（3）零均值，且常數，（2）：亞高斯分布伯努利分布全部由亞高斯隨機變量組成的矩陣成為亞高斯矩陣。定理15.7.2令

是亞高斯隨機矩陣，則

的RIP常數以至少

的概率滿足

，且：常數，只和亞高斯參數

和

有關給出了類似15.4.7節討論過的邊界條件。另外，如果是亞高斯矩陣，不管正交陣如何選擇，還是亞高斯陣。15.7.3部分隨機傅里葉矩陣

雖然隨機測量矩陣都具有RIP性質，且可達到測量下界，但有不足：（1）當需要對測量矩陣提出各種制約時，因為它們是隨機的，能給出的自由度很小，因此制約常無法實現；（2）隨機矩陣的每一個元素都要存儲，因此在硬件實現時困難；（3）缺少矩陣和向量乘的快速算法，限制了恢復算法的速度。DFT矩陣，確定性：

在DFT陣中隨機且均勻選擇

行，構成

的測量矩陣

。顯然，它具有部分隨機性，稱為部分隨機傅里葉矩陣。其一個突出優點是可用FFT來計算矩陣和向量的乘，提高編碼和解碼速度。

似傅里葉隨機矩陣的構成，也可以利用一般的正交矩陣來構成結構隨機矩陣。又稱為一般正交集總。定理15.7.23令

是部分隨機傅里葉矩陣，則

的RIP常數以至少

的概率足

，且，均為常數15.7.4確定性測量矩陣

雖然隨機矩陣可以大概率滿足RIP條件，但由于其存儲量大、缺乏快速算法等不足，特別是通過硬件實現時產生隨機數較為困難，因此人們在工程實際中更希望能使用確定性測量矩陣。文獻報告了該方面的一些進展，但離實際應用還很遠。研究出既能滿足RIP條件，又能接近于最佳的

確定性測量矩陣仍然是一個待解決的問題。15.8稀疏信號恢復算法欠定方程，無窮多解。如限定是稀疏的，則方程以大概率有唯一解。如何求解？基追蹤：問題；貪婪算法（匹配追蹤）：15.8.1基追蹤（basispursuit，BP）

基追蹤實際上不是一個算法，而是一個最優化的原理。其基本思想是找到一個信號的表示，使其表示系數