初识压缩感知 compressive sensing
壓縮感知是近年來極為熱門的研究前沿，在若干應用領域中都引起矚目。最近粗淺地看了這方面一些研究，對于Compressive Sensing有了初步理解，在此分享一些資料與精華。本文針對陶哲軒和Emmanuel Candes上次到北京的講座中對壓縮感知的講解進行講解，讓大家能夠對這個新興領域有一個初步概念。
compressive sensing（CS） 又稱 compressived sensing ，compressived sample，大意是在采集信號的時候（模擬到數字），同時完成對信號壓縮之意。中文的翻譯成“壓縮感知”，意思變得至少不太好理解了。
Compressed sensing is a mathematical tool that creates hi-res data sets from lo-res samples. It can be used to resurrect old musical recordings, find enemy radio signals, and generate MRIs much more quickly. Here’s how it would work with a photograph.
/***********************Compressive Sensing研究背景***********************/
（1）CS大約是2000年左右的一篇博士論文中，已經出現了雛形。后來被陶哲軒，C牛（Emmanuel Candes）和D（Donoho）牛，完善理論。這幾位頂尖高手聯手挖出了信號處理領域、機器學習領域，近10年最大的學術大坑。
2004年左右，大牛們聊天，覺得要起一個簡單的名字，因為理論本身是“通過對信號的高度不完備線性測量的高精確的重建”，如果這樣名字不響，不能起到理論推廣作用。所以就成了現在的名字"compressive sensing"。
（2）陶哲軒，是這個世界上最聰明的人，他怎么會關注到CS呢？陶哲軒是這個世界上搞調和分析的頂尖高手之一（當然他別的方面也很厲害）。?壓縮感知的發現是一次意外，話說一天，當時是加州理工學院教授（現在去了斯坦福）的Emmanuel Candès在研究名叫Shepp-Logan Phantom的圖像，這種標準圖像常被計算機科學家和工程師測試圖像算法。Candès檢查的圖像質量非常差，充滿了噪聲，他認為名叫L1-minimization的數學算法能去除掉噪聲條紋，結果算法真的起作用了，突然就覺得好神奇哦，“It was as if you gave me the first three digits of a 10-digit bank account number — and then I was able to guess the next seven,” he says. ?He tried rerunning the experiment on different kinds of phantom images; they resolved perfectly every time.。而且在圖像變干凈的同時，他發現圖像的細節出人意料的完美起來。
某一日Candes去幼兒園接孩子，正好遇上了也在接孩子的陶哲軒，兩人攀談的過程中他提到了自己手頭的困難，于是陶哲軒也開始想這個問題，它們成為兩人合作的壓縮感知領域第一篇論文的基礎。Emmanuel Candès認為壓縮感知（簡寫CS）技術具有廣闊的應用前景，比如MRI，數碼相機。數碼相機鏡頭收集了大量的數據，然后再壓縮，壓縮時丟棄掉90%的數據。如果有CS，如果你的照相機收集了如此多的數據只是為了隨后的刪除，那么為什么不一開始就丟棄那90%的數據，直接去除冗余信息不僅可以節省電池電量，還能節省空間。
/***********************大牛介紹***********************/
陶哲軒：澳籍華人數學家，童年時期即天資過人，目前主要研究調和分析、偏微分方程、組合數學、解析數論和表示論。24歲起，他在加利福尼亞大學洛杉磯分校擔任教授。他現在為該校終身數學教授。
Emmanuel Candes?（C牛）是斯坦福大學的數學、統計學，電子工程榮譽教授，同時也是應用計算數學領域的教授。他的?研究領域主要是在這種數學協調分析、數學優化、統計估測，以及在影像科學、信號研究。?Emmanuel Candes?教?授曾獲數項國際獎項，包括國家科學基金會最高個人獎項（該獎項主要獎勵?35?歲以下的學者）、?2008?年信息社?會理論論文獎，以及國際行業應用數學學會授予的獎項等等。
David Donoho ??WaveLab是小波和相關的時頻變換的一個Matlab例程庫，由美國斯坦福大學的donoho維護
/***********************基本思想***********************/
壓縮感知的概念：
將未知的要獲得的信號記為AK，它是一個波形。我們希望它越不連續越好，越擴散越好，而我所要做的是按照?一定的順序獲得圖像信號的信息。我們按照高斯分布來收集數據，而不是線性的，所以我們只會有少量的感測次數，而這些數據?的相關性非常低。
壓縮的意思，是指比較先前及當前數據的差異，并記錄下這些差異而減少?需儲存的資料量。對于壓縮感知的問題比壓縮難多了，像是我們要收集怎樣分布的數據、如何收集、保留一些什?么系數，從而得到最佳的結果。我們會得到一些機變，保留最大的，最有意義的系數在里頭。我們可以做一些抽樣，把最重要的保留下來。一個信號，我們知道它是非常好的，但這個信號完全是稀疏的，可能并不是我們要損失掉的。
對核磁共振的圖像，來看一下這些系數，?6000?個不連續性系數，我說我們只?要看?1800?不連續的測量，讓我們看有什么變化，讓我們看看重建后的圖片，這些圖片是非常接近真實圖像的，?我們可以用少于三倍或甚至四倍的測量次數而得到一個非常接近的結果。
感知壓縮難點在于，壓縮后的數據并不是壓縮前的數據的一個子集，并不是說，本來有照相機的感光器上有一千萬個像素，扔掉其中八百萬個，剩下的兩百萬個采集到的就是壓縮后的圖像，──這樣只能采集到不完整的一小塊圖像，有些信息被永遠的丟失了而且不可能被恢復。
如果要想采集很少一部分數據并且指望從這些少量數據中「解壓縮」出大量信息，就需要保證：第一：這些少量的采集到的數據包含了原信號的全局信息，第二：存在一種算法能夠從這些少量的數據中還原出原先的信息來。
有趣的是，在某些特定的場合，上述第一件事情是自動得到滿足的。最典型的例子就是醫學圖像成像，例如斷層掃描（CT）技術和核磁共振（MRI）技術。對這兩種技術稍有了解的人都知道，這兩種成像技術中，儀器所采集到的都不是直接的圖像像素，而是圖像經歷過全局傅立葉變換后的數據。也就是說，每一個單獨的數據都在某種程度上包含了全圖像的信息。在這種情況下，去掉一部分采集到的數據并不會導致一部分圖像信息永久的丟失（它們仍舊被包含在其它數據里）。這正是我們想要的情況。
上述第二件事就要歸功于陶哲軒和坎戴的工作了。他們的工作指出，如果假定信號（無論是圖像還是聲音還是其他別的種類的信號）滿足某種特定的「稀疏性」，那么從這些少量的測量數據中，確實有可能還原出原始的較大的信號來，其中所需要的計算部分是一個復雜的迭代優化過程，即所謂的「L1-最小化」算法。
把上述兩件事情放在一起，我們就能看到這種模式的優點所在。它意味著：我們可以在采集數據的時候只簡單采集一部分數據（「壓縮感知」），然后把復雜的部分交給數據還原的這一端來做，正好匹配了我們期望的格局。在醫學圖像領域里，這個方案特別有好處，因為采集數據的過程往往是對病人帶來很大麻煩甚至身體傷害的過程。以 X 光斷層掃描為例，眾所周知 X 光輻射會對病人造成身體損害，而「壓縮感知」就意味著我們可以用比經典方法少得多的輻射劑量來進行數據采集，這在醫學上的意義是不言而喻的。
/***********************基本概念詳細說明舉例***********************/
本部分為陶哲軒在一篇blog中對于comprehensive sensing 文章翻譯過來的精華部分，提取了重點，并加入了一些理解，這里用來解釋CS的概念堪稱經典。
相機的用途，自然是記錄圖像。為了簡化論述，我們把圖像假設成一個長方形陣列，比如說一個1024×2048像素的陣列（這樣就總共是二百萬像素）。為了省略彩色的問題（這個比較次要），我們就假設只需要黑白圖像，那么每個像素就可以用一個整型的灰度值來計量其亮度（例如用八位整型數表示0到255，16位表示0到65535）。接下來，按照最最簡化的說法，傳統相機會測量每一個像素的亮度（在上述例子中就是二百萬個測量值），結果得到的圖片文件就比較大（用8位灰度值就是2MB（1024*2048*8b），16位灰度就是4MB）。數學上就認為這個文件是用超高維矢量值描繪的（在本例中就是約二百萬維）,進行。
在我開始講“壓縮感知”這個新故事之前，必須先快速回顧一下“老式壓縮”的舊故事。（已經了解圖像壓縮算法的讀者可以跳過這幾段。）
老式壓縮：
怎么樣壓縮圖像？方式多種多樣，其中有些非常先進，不過我來試試用一種不太高科技的（而且也不太精確的）說法來描述一下這些先進技術。圖像通常都含有大片無細節部分–比如在風景照里面，將近一半的畫面都可能被單色的天空背景占據。我們假設提取一個大方塊，比方說100×100像素，其中完全是同一顏色的——假設是全白的吧。無壓縮時，這個方塊要占10000字節存儲空間（按照8位灰度算）；但是我們可以只記錄這個方塊的維度和坐標，還有填充整個方塊的單一顏色；這樣總共也只要記錄四五個字節，省下了可觀的空間。不過在現實中，壓縮效果沒有這么好，因為表面看來沒有細節的地方其實是有著細微的色差的。所以，給定一個無細節方塊，我們記錄其平均色值，就把圖片中這一塊區域提取出來，只留下微小的殘余誤差。接下來就可以繼續選取更多無細節的方塊，抽象成單色色塊。最后剩下的是亮度（色彩強度）很小的，肉眼無法察覺的細節。于是就可以拋棄這些剩余的細節，只需要記錄那些“可見”色塊的大小，位置和亮度。日后則可以反向操作，重建出比原始圖像質量稍低一些，占空間卻小得多的復制圖片。
其實上述的算法并不適合處理顏色劇烈變動的情況，所以在實際應用中不很有效。事實上，更好的辦法不是用均勻色塊，而是用“不均勻”的色塊——比方說右半邊色彩強度平均值大于左半邊這樣的色塊。這種情況可以用（二維）Haar小波系統來描述。后來人們又發現一種”更平滑的”小波系統更能夠避免誤差，不過這都是技術細節，我們就不深入討論了。然而所有這些系統的原理都是相同的：把原始圖像表示為不同“小波（類似于上文中的色塊）”的線性疊加，記錄顯著的（高強度的）小波的系數，放棄掉（或者用閾值排除掉）剩下的小波系數。這種“小波系數硬閾值”壓縮算法沒有實際應用的算法（比如JPEG 2000標準中所定義的）那么精細，不過多少也能描述壓縮的普遍原理。
總體來講（也是非常簡化的說法），原始的1024×2048圖像可能含有兩百萬自由度，想要用小波來表示這個圖像的人需要兩百萬個不同小波才能完美重建。但是典型的有意義的圖像，從小波理論的角度看來是非常稀疏的，也就是可壓縮的：可能只需要十萬個小波就已經足夠獲取圖像所有的可見細節了，其余一百九十萬小波只貢獻很少量的，大多數觀測者基本看不見的“隨機噪聲”。（這也不是永遠適用：含有大量紋理的圖像–比如毛發、毛皮的圖像——用小波算法特別難壓縮，也是圖像壓縮算法的一大挑戰。But that is another story。）
接下來呢，如果我們（或者不如說是相機）事先知道兩百萬小波系數里面哪十萬個是重要的，那camera就可以只計算這十萬個系數，別的就不管了。（對于單個系數的計算，可以在圖像上應用一種合適的filter“濾波器”或叫mask“濾鏡/掩模”，然后計量過濾出來的每個像素的色彩強度）但是，相機是不會知道哪個系數是重要的，所以它只好計量全部兩百萬個像素，把整個圖像轉換成基本小波，找出需要留下的那十萬個主導基本小波，再刪掉其余的。（這當然只是真正的圖像壓縮算法的一個草圖，不過為了便于討論我們還是就這么用吧。）
PS: 經典的數據壓縮技術，無論是音頻壓縮（例如 mp3），圖像壓縮（例如 jpeg），視頻壓縮（mpeg），還是一般的編碼壓縮（zip），都是從數據本身的特性出發，尋找并剔除數據中隱含的冗余度，從而達到壓縮的目的。這樣的壓縮有兩個特點：第一、它是發生在數據已經被完整采集到之后；第二、它本身需要復雜的算法來完成。相較而言，解碼過程反而一般來說在計算上比較簡單，以音頻壓縮為例，壓制一個 mp3 文件的計算量遠大于播放（即解壓縮）一個 mp3 文件的計算量。
那么，如今的數碼相機當然已經很強大了，沒什么問題干嗎還要改進？事實上，上述的算法，需要收集大量數據，但是只需要存儲一部分，在消費攝影中是沒有問題的。尤其是隨著數據存儲變得很廉價，現在拍一大堆完全不壓縮的照片也無所謂。而且，盡管出了名地耗電，壓縮所需的運算過程仍然算得上輕松。但是，在非消費領域的某些應用中，這種數據收集方式并不可行，特別是在傳感器網絡中。如果打算用上千個傳感器來收集數據，而這些傳感器需要在固定地點呆上幾個月那么長的時間，那么就需要盡可能地便宜和節能的傳感器——這首先就排除了那些有強大運算能力的傳感器（然而——這也相當重要——我們在接收處理數據的接收端仍然需要現代科技提供的奢侈的運算能力）。在這類應用中，數據收集方式越“傻瓜”越好（而且這樣的系統也需要很強壯，比如說，能夠忍受10%的傳感器丟失或者各種噪聲和數據缺損）。所謂的「壓縮感知」，也就是說，直接感知壓縮了的信息。
壓縮感知：
這就是壓縮感知的用武之地了。其理論依據是：如果只需要10萬個分量就可以重建絕大部分的圖像，那何必還要做所有的200萬次測量，只做10萬次不就夠了嗎？（在實際應用中，我們會留一個安全余量，比如說測量30萬像素，以應付可能遭遇的所有問題，從干擾到量化噪聲，以及恢復算法的故障。）這樣基本上能使節能上一個數量級，這對消費攝影沒什么意義，對感知器網絡而言卻有實實在在的好處。
不過，正像我前面說的，相機自己不會預先知道兩百萬小波系數中需要記錄哪十萬個。要是相機選取了另外10萬（或者30萬），反而把圖片中所有有用的信息都扔掉了怎么辦？
※※※※※※※※※※※※※※※
解決的辦法簡單但是不太直觀。就是用非小波的算法來做30萬個測量——盡管我前面確實講過小波算法是觀察和壓縮圖像的最佳手段。實際上最好的測量其實應該是（偽）隨機測量——比如說隨機生成30萬個濾鏡（mask）圖像并測量真實圖像與每個mask的相關程度。這樣，圖像與mask之間的這些測量結果（也就是“相關性”）很有可能是非常小非常隨機的。但是——這是關鍵所在——構成圖像的2百萬種可能的小波函數會在這些隨機的mask的測量下生成自己特有的“特征”，它們每一個都會與某一些mask成正相關，與另一些mask成負相關，但是與更多的mask不相關。可是（在極大的概率下）2百萬個特征都各不相同；這就導致，其中任意十萬個的線性組合仍然是各不相同的（以線性代數的觀點來看，這是因為一個30萬維線性子空間中任意兩個10萬維的子空間幾乎互不相交）。因此，理論上是有可能從這30萬個隨機mask數據中恢復圖像的（至少可以恢復圖像中的10萬個主要細節）。簡而言之，我們是在討論一個哈希函數的線性代數版本。
PS: 這里的原理就是說，如果3維線性子空間中的任意兩個2維子空間是線性相關的話，比如：
①3x+2y=8
②6x+4y=16
③4x+5y=10
中，①②就是線性相關的，①③不是線性相關的。將200萬個小波函數降維到30萬個掩模基的過程就是類似去掉①②中冗余基的過程。
然而這種方式仍然存在兩個技術問題。首先是噪聲問題：10萬個小波系數的疊加并不能完全代表整幅圖像，另190萬個系數也有少許貢獻。這些小小貢獻有可能會干擾那10萬個小波的特征，這就是所謂的“失真”問題。第二個問題是如何運用得到的30萬測量數據來重建圖像。
我們先來關注后一個問題（怎樣恢復圖像）。如果我們知道了2百萬小波中哪10萬個是有用的，那就可以使用標準的線性代數方法（高斯消除法，最小二乘法等等）來重建信號。（這正是線性編碼最大的優點之一——它們比非線性編碼更容易求逆。大多數哈希變換實際上是不可能求逆的——這在密碼學上是一大優勢，在信號恢復中卻不是。）可是，就像前面說的那樣，我們事前并不知道哪些小波是有用的。怎么找出來呢？一個單純的最小二乘近似法會得出牽扯到全部2百萬系數的可怕結果，生成的圖像也含有大量顆粒噪點。要不然也可以代之以一種強力搜索，為每一組可能的10萬關鍵系數都做一次線性代數處理，不過這樣做的耗時非常恐怖（總共要考慮大約10的17萬次方個組合！），而且這種強力搜索通常是NP完備的（其中有些特例是所謂的“子集合加總”問題）。不過還好，還是有兩種可行的手段來恢復數據：
?匹配追蹤：找到一個其標記看上去與收集到的數據相關的小波；在數據中去除這個標記的所有印跡；不斷重復直到我們能用小波標記“解釋”收集到的所有數據。
Matching pursuit: locate a wavelet whose signature seems to correlate with the data collected; remove all traces of that signature from the data; and repeat until we have totally “explained” the data collected in terms of wavelet signatures. 就是先找出一個貌似是基的小波，然后去掉該小波在圖像中的分量，迭代直到找出所有10w個小波.
?基追蹤（又名L1模最小化）：在所有與(image)數據匹配的小波組合中，找到一個“最稀疏的”基，也就是其中所有系數的絕對值總和越小越好。（這種最小化的結果趨向于迫使絕大多數系數都消失了。）這種最小化算法可以利用單純形法之類的凸規劃算法，在合理的時間內計算出來。
Basis pursuit?(or??minimisation): Out of all the possible combinations of wavelets which would fit the data collected, find the one which is “sparsest” in the sense that the total sum of the magnitudes of all the coefficients is as small as possible. (It turns out that this particular minimisation tends to force most of the coefficients to vanish.) This type of minimisation can be computed in reasonable time via?convex optimisationmethods such as the?simplex method.
現在已經有嚴密的結果顯示，對原始圖像設定不同的壓縮率或稀疏性，這兩種算法完美或近似完美地重建圖像的成功率都很高。匹配追蹤法通常比較快，而基追蹤算法在考慮到噪聲時則顯得比較準確。這些算法確切的適用范圍問題在今天仍然是非常熱門的研究領域。（說來遺憾，目前還沒有出現對P不等于NP問題的應用；如果一個重建問題（在考慮到測量矩陣時）是NP完備的，那它剛好就不能用上述算法解決。）
由于壓縮感知還是一個相當新的領域（尤其是嚴密的數學結果剛剛出現），現在就期望這個技術應用到實用的傳感器上還為時尚早。不過已經有概念驗證模型出現了，其中最著名的是Rice大學研制的單像素相機。
最后必須提到的是，壓縮感知技術是一種抽象的數學概念，而不是具體的操作方案，它可以應用到成像以外的許多領域。以下只是其中幾個例子：
? 磁共振成像(MRI)。在醫學上，磁共振的工作原理是做許多次（但次數仍是有限的）測量（基本上就是對人體圖像進行離散拉東變換（也叫X光變換）），再對數據進行加工來生成圖像（在這里就是人體內水的密度分布圖像）。由于測量次數必須很多，整個過程對患者來說太過漫長。壓縮感知技術可以顯著減少測量次數，加快成像（甚至有可能做到實時成像，也就是核磁共振的視頻而非靜態圖像）。此外我們還可以以測量次數換圖像質量，用與原來一樣的測量次數可以得到好得多的圖像分辨率。ps:在C牛的video中也有提到
?天文學。許多天文現象（如脈沖星）具有多種頻率震蕩特性，使其在頻域上是高度稀疏也就是可壓縮的。壓縮感知技術將使我們能夠在時域內測量這些現象（即記錄望遠鏡數據）并能夠精確重建原始信號，即使原始數據不完整或者干擾嚴重（原因可能是天氣不佳，上機時間不夠，或者就是因為地球自傳使我們得不到全時序的數據）。
?線性編碼。壓縮感知技術提供了一個簡單的方法，讓多個傳送者可以將其信號帶糾錯地合并傳送，這樣即使輸出信號的一大部分丟失或毀壞，仍然可以恢復出原始信號。例如，可以用任意一種線性編碼把1000比特信息編碼進一個3000比特的流；那么，即使其中300位被（惡意）毀壞，原始信息也能完全無損失地完美重建。這是因為壓縮感知技術可以把破壞動作本身看作一個稀疏的信號（只集中在3000比特中的300位）。
許多這種應用都還只停留在理論階段，可是這種算法能夠影響測量和信號處理中如此之多的領域，其潛力實在是振奮人心。筆者自己最有成就感的就是能看到自己在純數學領域的工作（例如估算傅立葉子式的行列式或單數值）最終具備造福現實世界的前景。
/***********************CS研究內容***********************/
研究壓縮感知的內容有幾塊呢？
（1）壓縮感知理論，比如測量矩陣，重建性能分析，測量數據量化影響；
（2）優化算法，本質上是重建算法優化，比如線性規劃（LP）、貝葉斯優化等等；
（3）實際的應用，壓縮？后處理？分類？等等
The main theoretical findings in this recent field have mostly centered on how many multiplexed measurements are necessary to reconstruct the original signal and the attendant nonlinear reconstruction techniques needed to demultiplex these signals.?
最近的理論研究主要集中在 ①需要多少多維測度才能重建原始信號 ②分解信號所需的非線性重建技術；還有能夠直接進行多維信號選擇的感知硬件(sensing hardware)。
/***********************CS的壓縮/解壓效果***********************/
由于剛剛看這一方面的資料，未免經驗不足，就借鑒了其他人（Ganer）在該領域的探究結果，他的博客中寫到：
很多mpressive sensing的實際用于信號采集效果其實并不是很好。
就從我的實驗而言，對于圖像壓縮甚至會差的很，遠遠低于傳統的壓縮方式。
那就不難有學者發出感嘆，實際上compressive sensing 就是depressive sensing了。
我的理解是什么呢？有2點牢牢記住的
（1）compressive sensing實際上是對信號采集的顛覆性的理論，打破了乃奎斯特采樣（也稱香農采樣）。
? ? ? ? 實際上，大部分信號是稀疏的，沒有必要用乃奎斯特采樣，進行時間離散化。
? ? ? ? 注意兩點：（1）乃奎斯特采樣對信號沒有稀疏性的假設；
? ? ? ? ? ? ? ? ? ? ? ? ?（2）CS對信號有稀疏性假設，既K稀疏；
? ? ? ?那么，信號采集過程也就是說從A2D，變成了A2I。
? ? ? 但是在實際應用角度，2者結合會有很大的收益。（個人觀點）
（2）compressive sensing本事是最大后驗（MAP）解碼，這點比傳統的方式要更為”先進“，也更為”危險“。
關于Compressive Sensing更多的學習資料將繼續更新，敬請關注本博客和新浪微博Sophia_qing。
References：
1.?Compressed sensing and single-pixel cameras?- Terrytao
2.?斯坦福大學Emmanuel Candes教授：壓縮感知?video2
3.?An Introduction to Compressed Sensing?（斯坦福課程，可根據syllabus分塊啃食）
4.Near Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?-Emmanuel Candes,?Terence Tao
5.?http://blog.163.com/gan_research/blog/static/16534814820107912256225/
6.?C牛在Stanford的課程
7.?中國壓縮傳感資源（China Compressive Sensing Resources）
8.Using Math to Turn Lo-Res Datasets Into Hi-Res Samples? - Jordan Ellenberg?
(ellenber@math.wisc.edu),?an associate professor of mathematics at the University of Wisconsin, wrote about theNetflix Prize in issue 16.03.
總結
以上是生活随笔為你收集整理的初识压缩感知 compressive sensing的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Matlab中的CVX工具包安装
- 下一篇： 华为2016年应届毕业生招聘公告