壓縮感知理論簡介

TheIntroductionofCompressedSensing(CS)Theory

西安工程大學理學院李海洋壓縮感知理論簡介TheIntroduction1背景介紹

1.1：傳統(tǒng)采樣理論簡介

1.2：壓縮感知理論的提出2壓縮感知理論主要研究內容

2.1：信號的稀疏表示2.2：觀測矩陣的設計

2.3：信號重構3壓縮感知應用-單像素CS相機1背景介紹1.1傳統(tǒng)采樣理論簡介

信號采樣壓縮傳輸重構Nyquist-Shannon采樣定律JEPG等傳統(tǒng)的信號處理過程1.1傳統(tǒng)采樣理論簡介信號采樣壓縮傳輸重構Ny傳統(tǒng)的基于Nyquist-Shannon采樣定理指導下的信息采樣理論的不足主要表現(xiàn)在以下兩個方面：1、根據Nyquist-Shannon采樣定律，采樣速率需達到信號帶寬的兩倍以上才能精確重構信號。而現(xiàn)實生活中，隨著信息技術的高速發(fā)展，信息量的需求增加，攜帶信息的信號所占帶寬也越來越大，因此對采樣的硬件設備的要求也越來越高。壓縮感知理論介紹課件2、另一方面，在實際應用中，為了降低信號的存儲、處理和傳輸成本，人們又不得不經由壓縮方式減少信號表示的比特數，以此拋棄認為不重要的數據，這種高速采樣再拋棄的過程顯然是對采樣資源的巨大浪費。

2、另一方面，在實際應用中，為了降低信號的存儲、處理和傳輸成

1.2壓縮感知理論的提出

既然傳統(tǒng)方法采樣的多數數據會被拋棄，那么，為什么還要獲取全部數據而不直接獲取需要保留的數據呢？采集很少一部分數據并且期望從這些少量數據中解壓出大量信息，有無這種可能呢？D.Donoho,Candes，T.Tao等人證明了如果信號具有稀疏性的特性，那么就可能存在一種算法能夠從這些少量的數據中還原出原先的信息。

1.2壓縮感知理論的提出

信號壓縮感知傳輸重構信號采樣壓縮信號壓縮傳輸重構信號采樣壓縮2壓縮感知理論主要研究內容

2.1：信號的稀疏表示2.2：觀測矩陣的設計

2.3：信號重構2壓縮感知理論主要研究內容2.1信號的稀疏表示稀疏性的定義：一個實值有限長的N維離散信號，它可以用一個標準正交基的線性組合來表示，其中表示矩陣的轉置，那么有其中，若在基上僅有個非零系數時，稱為信號的稀疏基，是稀疏(K-Sparsity)的。2.1信號的稀疏表示稀疏性的定義如圖是一個稀疏度為3的稀疏變換，,向量基本都是非零值，但將其變換到域時，非零值就只有3個了，數目遠小于原來的非零數目，實現(xiàn)了信號的稀疏表示。如圖是一個稀疏度為3的稀疏變換，,

如何尋找信號的最佳稀疏域呢？這是壓縮感知理論的基礎和前提，也是信號精確重構的保證。對稀疏表示研究主要有兩個方面：（1）基函數字典下的稀疏表示：尋找一個正交基使得信號表示的稀疏系數盡可能的少。比較常用的基有：高斯矩陣、小波基、正（余）弦基、Curvelet基等。Candes和Tao經研究發(fā)現(xiàn)光滑信號的Fourier系數、小波系數、有界變差函數的全變差范數、振蕩信號的Gabor系數及具有不連續(xù)邊緣的圖像信號的Curvelet系數等都具有足夠的稀疏性,可以通過壓縮感知理論恢復信號。如何尋找信號的最佳稀疏域呢？這是壓縮感知理論的（2）超完備庫下的稀疏表示：用超完備的冗余函數庫來取代基函數，稱之為冗余字典，字典中的元素被稱之為原子，目的是從冗余字典中找到具有最佳線性組合的K項原子來逼近表示一個信號，稱作信號的稀疏逼近或高度非線性逼近。一是如何構造這樣一個適合某一類信號的冗余字典；二是在已知冗余字典的前提下如何設計快速有效的分解方法來稀疏地表示某一個信號。（2）超完備庫下的稀疏表示：2.2觀測矩陣的設計觀測器的目的是采樣得到個觀測值，并保證從中能夠重構出原來長度為的信號或者稀疏基下的系數向量。

觀測過程就是利用觀測矩陣的個行向量對稀疏系數向量進行投影，得到個觀測值，即2.2觀測矩陣的設計如果我們假設信號已經是稀疏的，那么上面的方程就可以寫作

如果我們假設信號已經是稀疏的，那么上面的方程就可以寫作觀測矩陣要滿足什么樣的條件呢？從上式中求出是一個線性方程組的求解問題，但由于方程的個數遠遠少于未知數的個數，即，因此，一般說來，該方程組有無窮多個解。但如果具有稀疏性，則有可能求出確定解。Candes、Tao等人提出必須保證觀測矩陣不會把兩個不同的稀疏信號映射到同一個采樣幾何中，即上述線性方程組的稀疏解具有唯一性。

觀測矩陣要滿足什么樣的條件呢？從上式中求出是一

目前，關于測量矩陣的研究主要基于以下兩個方面：１RIP條件：２相干性：壓縮感知理論介紹課件

隨機矩陣、結構隨機矩陣與確定性矩陣.雖然隨機矩陣能產生尺寸接近最優(yōu)的RIP矩陣。

在工程實際中,人們更希望構造一個確定性RIP矩陣。因為確定性矩陣更利于工程設計,此外,從構造解碼算法角度來看,確定性矩陣利于降低內存、設計快速的恢復算法等。然而,現(xiàn)在仍然缺少令人滿意的確定性RIP矩陣構造方法。結構隨機矩陣.與確定性矩陣相比,結構隨機矩陣多了些隨機性,因而可以證明其具有較好的RIP性質,同時,結構隨機矩陣的隨機性較弱,一般僅具有行隨機性。

2.3信號重構

首先介紹范數的概念。向量的p-范數為：

當p=0時得到0-范數，它表示上式中非零項的個數。由于觀測數量，不能直接求解，在信號能稀疏表示的前提下，求解方程組的問題轉化為最小0-范數問題：2.3信號重構

首先介紹范數的概對于0-范數問題的求解是個NP問題，在實際應用中很難獲得問題的可行解。因此，尋求對以上問題的松弛以獲得理想的逼近解，已成為稀疏信號重構的重要手段。一種自然的想法是，用下面的模型來代替，我們稱之為p-范數優(yōu)化問題（0<p<=1）：或者：求解該最優(yōu)化問題，得到稀疏域的系數，然后反變換即可以得到時域信號。壓縮感知理論介紹課件壓縮感知理論介紹課件目前出現(xiàn)的重構算法主要有：

1）第一類貪婪算法：這類算法是通過每次迭代時選擇一個局部最優(yōu)解來逐步逼近原始信號，典型的貪婪算法--MP算法，貪婪算法是針對組合優(yōu)化提出,目前已發(fā)展了多種變形，例如，OMP,OOMP,CosMP等。該類重建算法速度快,然而需要的測量數據多且精度低。2）第二類凸優(yōu)化算法：即1-范數優(yōu)化問題，這類方法是將非凸問題轉化為凸問題求解找到信號的逼近，如BP算法，梯度投影方法等。該類算法速度慢，然而需要的測量數據少且精度高。目前出現(xiàn)的重構算法主要有：

1）第一類貪婪算法：這類算法是通

但是基于1-范數優(yōu)化問題的信號重構至少存在兩個方面的不足：（1）數據之間還可能存在很大的冗余難以去除；（2）無法區(qū)分稀疏尺度的位置（盡管重構信號在歐式距離上逼近原始信號,但會出現(xiàn)低尺度的能量轉移到高尺度的現(xiàn)象,因而易出現(xiàn)高頻震蕩現(xiàn)象）。３）p-范數優(yōu)化問題。

Xu等人對1/2-范數優(yōu)化問題的正則化問題進行了深入的研究，給出了問題的解析解，并從數值實驗的角度說明了該問題的解具有較1-范數重構更好的稀疏性，且p越小，稀疏性越好。但是基于1-范數優(yōu)化問題的信號重構至少存在兩個方3壓縮感知應用--單像素CS相機

運用壓縮感知原理，RICE大學成功研制了單像素CS相機。傳統(tǒng)百萬像素的相機需要百萬個探測傳感器，而壓縮傳感數碼相機只使用一個探測器來采光，然后跟捕獲后的計算相結合來重構圖像。這種樣機的鏡頭由兩部分組成：一個光電二極管和一個微鏡陣列。該相機直接獲取的是M次隨機線性測量值而不是獲取原始信號的N個像素值，為低像素相機拍攝高質量圖像提供了可能。3壓縮感知應用--單像素CS相機運用壓縮感知“數字微鏡陣列”完成圖像在偽隨機二值模型上的線性投影的光學計算，其反射光由透鏡聚焦到單個光敏二極管上，光敏二極管兩端的電壓值即為一個測量值y，將此投影操作重復M次，即得到測量向量Y，然后用最小全變分算法構建的數字信號處理器重構原始圖像x。數字微鏡器件由數字電壓信號控制微鏡片的機械運動以實現(xiàn)對入射光線的調整，相當于隨機觀測矩陣?！皵底治㈢R陣列”完成圖像在偽隨機二值模型上的線性投影的光學計現(xiàn)為美國StanfordUniversity

人文科學講座教授及統(tǒng)計學教授。他是美國人文與科學學院院士、美國工業(yè)與應用數學學會(SIAM)院士、法國科學院外籍院士及美國國家科學院院士。統(tǒng)計學會會長獎（1994）邵逸夫數學科學獎（2013）現(xiàn)為美國StanfordUniversity人文科EmmanuelCandes是斯坦福大學的數學、統(tǒng)計學，電子工程榮譽教授，同時也是應用計算數學領域的教授。EmmanuelCandes教授曾獲數項國際獎項，包括國家科學基金會最高個人獎項。

ICM2014被邀請做1小時報告。EmmanuelCandes是斯坦福大學的數學、統(tǒng)計學，

謝謝大家！謝謝大家！壓縮感知理論簡介

TheIntroductionofCompressedSensing(CS)Theory

西安工程大學理學院李海洋壓縮感知理論簡介TheIntroduction1背景介紹

1.1：傳統(tǒng)采樣理論簡介

1.2：壓縮感知理論的提出2壓縮感知理論主要研究內容

2.1：信號的稀疏表示2.2：觀測矩陣的設計

2.3：信號重構3壓縮感知應用-單像素CS相機1背景介紹1.1傳統(tǒng)采樣理論簡介

信號采樣壓縮傳輸重構Nyquist-Shannon采樣定律JEPG等傳統(tǒng)的信號處理過程1.1傳統(tǒng)采樣理論簡介信號采樣壓縮傳輸重構Ny傳統(tǒng)的基于Nyquist-Shannon采樣定理指導下的信息采樣理論的不足主要表現(xiàn)在以下兩個方面：1、根據Nyquist-Shannon采樣定律，采樣速率需達到信號帶寬的兩倍以上才能精確重構信號。而現(xiàn)實生活中，隨著信息技術的高速發(fā)展，信息量的需求增加，攜帶信息的信號所占帶寬也越來越大，因此對采樣的硬件設備的要求也越來越高。壓縮感知理論介紹課件2、另一方面，在實際應用中，為了降低信號的存儲、處理和傳輸成本，人們又不得不經由壓縮方式減少信號表示的比特數，以此拋棄認為不重要的數據，這種高速采樣再拋棄的過程顯然是對采樣資源的巨大浪費。

2、另一方面，在實際應用中，為了降低信號的存儲、處理和傳輸成

1.2壓縮感知理論的提出

既然傳統(tǒng)方法采樣的多數數據會被拋棄，那么，為什么還要獲取全部數據而不直接獲取需要保留的數據呢？采集很少一部分數據并且期望從這些少量數據中解壓出大量信息，有無這種可能呢？D.Donoho,Candes，T.Tao等人證明了如果信號具有稀疏性的特性，那么就可能存在一種算法能夠從這些少量的數據中還原出原先的信息。

1.2壓縮感知理論的提出

信號壓縮感知傳輸重構信號采樣壓縮信號壓縮傳輸重構信號采樣壓縮2壓縮感知理論主要研究內容

2.1：信號的稀疏表示2.2：觀測矩陣的設計

2.3：信號重構2壓縮感知理論主要研究內容2.1信號的稀疏表示稀疏性的定義：一個實值有限長的N維離散信號，它可以用一個標準正交基的線性組合來表示，其中表示矩陣的轉置，那么有其中，若在基上僅有個非零系數時，稱為信號的稀疏基，是稀疏(K-Sparsity)的。2.1信號的稀疏表示稀疏性的定義如圖是一個稀疏度為3的稀疏變換，,向量基本都是非零值，但將其變換到域時，非零值就只有3個了，數目遠小于原來的非零數目，實現(xiàn)了信號的稀疏表示。如圖是一個稀疏度為3的稀疏變換，,

如何尋找信號的最佳稀疏域呢？這是壓縮感知理論的基礎和前提，也是信號精確重構的保證。對稀疏表示研究主要有兩個方面：（1）基函數字典下的稀疏表示：尋找一個正交基使得信號表示的稀疏系數盡可能的少。比較常用的基有：高斯矩陣、小波基、正（余）弦基、Curvelet基等。Candes和Tao經研究發(fā)現(xiàn)光滑信號的Fourier系數、小波系數、有界變差函數的全變差范數、振蕩信號的Gabor系數及具有不連續(xù)邊緣的圖像信號的Curvelet系數等都具有足夠的稀疏性,可以通過壓縮感知理論恢復信號。如何尋找信號的最佳稀疏域呢？這是壓縮感知理論的（2）超完備庫下的稀疏表示：用超完備的冗余函數庫來取代基函數，稱之為冗余字典，字典中的元素被稱之為原子，目的是從冗余字典中找到具有最佳線性組合的K項原子來逼近表示一個信號，稱作信號的稀疏逼近或高度非線性逼近。一是如何構造這樣一個適合某一類信號的冗余字典；二是在已知冗余字典的前提下如何設計快速有效的分解方法來稀疏地表示某一個信號。（2）超完備庫下的稀疏表示：2.2觀測矩陣的設計觀測器的目的是采樣得到個觀測值，并保證從中能夠重構出原來長度為的信號或者稀疏基下的系數向量。

觀測過程就是利用觀測矩陣的個行向量對稀疏系數向量進行投影，得到個觀測值，即2.2觀測矩陣的設計如果我們假設信號已經是稀疏的，那么上面的方程就可以寫作

如果我們假設信號已經是稀疏的，那么上面的方程就可以寫作觀測矩陣要滿足什么樣的條件呢？從上式中求出是一個線性方程組的求解問題，但由于方程的個數遠遠少于未知數的個數，即，因此，一般說來，該方程組有無窮多個解。但如果具有稀疏性，則有可能求出確定解。Candes、Tao等人提出必須保證觀測矩陣不會把兩個不同的稀疏信號映射到同一個采樣幾何中，即上述線性方程組的稀疏解具有唯一性。

觀測矩陣要滿足什么樣的條件呢？從上式中求出是一

目前，關于測量矩陣的研究主要基于以下兩個方面：１RIP條件：２相干性：壓縮感知理論介紹課件

隨機矩陣、結構隨機矩陣與確定性矩陣.雖然隨機矩陣能產生尺寸接近最優(yōu)的RIP矩陣。

在工程實際中,人們更希望構造一個確定性RIP矩陣。因為確定性矩陣更利于工程設計,此外,從構造解碼算法角度來看,確定性矩陣利于降低內存、設計快速的恢復算法等。然而,現(xiàn)在仍然缺少令人滿意的確定性RIP矩陣構造方法。結構隨機矩陣.與確定性矩陣相比,結構隨機矩陣多了些隨機性,因而可以證明其具有較好的RIP性質,同時,結構隨機矩陣的隨機性較弱,一般僅具有行隨機性。

2.3信號重構

首先介紹范數的概念。向量的p-范數為：

當p=0時得到0-范數，它表示上式中非零項的個數。由于觀測數量，不能直接求解，在信號能稀疏表示的前提下，求解方程組的問題轉化為最小0-范數問題：2.3信號重構

首先介紹范數的概對于0-范數問題的求解是個NP問題，在實際應用中很難獲得問題的可行解。因此，尋求對以上問題的松弛以獲得理想的逼近解，已成為稀疏信號重構的重要手段。一種自然的想法是，用下面的模型來代替，我們稱之為p-范數優(yōu)化問題（0<p<=1）：或者：求解該最優(yōu)化問題，得到稀疏域的系數，然后反變換即可以得到時域信號。壓縮感知理論介紹課件壓縮感知理論介紹課件目前出現(xiàn)的重構算法主要有：

1）第一類貪婪算法：這類算法是通過每次迭代時選擇一個局部最優(yōu)解來逐步逼近原始信號，典型的貪婪算法--MP算法，貪婪算法是針對組合優(yōu)化提出,目前已發(fā)展了多種變形，例如，OMP,OOMP,CosMP等。該類重建算法速度快,然而需要的測量數據多且精度低。2）第二類凸優(yōu)化算法：即1-范數優(yōu)化問題，這類方法是將非凸問題轉化為凸問題求解找到信號的逼近，如BP算法，梯度投影方法等。該類算法速度慢，然而需要的測量數據少且精度高。目前出現(xiàn)的重構算法主要有：

1）第一類貪婪算法：這類算法是通

但是基于1-范數優(yōu)化問題的信號重構至少存在兩個方面的不足：（1）數據之間還可能存在很大的冗余難以去除；（2）無法區(qū)分稀疏尺度的位置（盡管重構信號在歐式距離上逼近原始信號,但會出現(xiàn)低尺度的能量轉移到高尺度的現(xiàn)象,因而易出現(xiàn)高頻震蕩現(xiàn)象）。３）p-范數優(yōu)化問題。

Xu等人對1/2-