初识压缩感知 compressive sensing
壓縮感知是近年來極為熱門的研究前沿，在若干應(yīng)用領(lǐng)域中都引起矚目。最近粗淺地看了這方面一些研究，對(duì)于Compressive Sensing有了初步理解，在此分享一些資料與精華。本文針對(duì)陶哲軒和Emmanuel Candes上次到北京的講座中對(duì)壓縮感知的講解進(jìn)行講解，讓大家能夠?qū)@個(gè)新興領(lǐng)域有一個(gè)初步概念。
compressive sensing（CS） 又稱 compressived sensing ，compressived sample，大意是在采集信號(hào)的時(shí)候（模擬到數(shù)字），同時(shí)完成對(duì)信號(hào)壓縮之意。中文的翻譯成“壓縮感知”，意思變得至少不太好理解了。
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年左右的一篇博士論文中，已經(jīng)出現(xiàn)了雛形。后來被陶哲軒，C牛（Emmanuel Candes）和D（Donoho）牛，完善理論。這幾位頂尖高手聯(lián)手挖出了信號(hào)處理領(lǐng)域、機(jī)器學(xué)習(xí)領(lǐng)域，近10年最大的學(xué)術(shù)大坑。
2004年左右，大牛們聊天，覺得要起一個(gè)簡單的名字，因?yàn)槔碚摫旧硎恰?span style="color:rgb(255,0,0)">通過對(duì)信號(hào)的高度不完備線性測(cè)量的高精確的重建”，如果這樣名字不響，不能起到理論推廣作用。所以就成了現(xiàn)在的名字"compressive sensing"。
（2）陶哲軒，是這個(gè)世界上最聰明的人，他怎么會(huì)關(guān)注到CS呢？陶哲軒是這個(gè)世界上搞調(diào)和分析的頂尖高手之一（當(dāng)然他別的方面也很厲害）。?壓縮感知的發(fā)現(xiàn)是一次意外，話說一天，當(dāng)時(shí)是加州理工學(xué)院教授（現(xiàn)在去了斯坦福）的Emmanuel Candès在研究名叫Shepp-Logan Phantom的圖像，這種標(biāo)準(zhǔn)圖像常被計(jì)算機(jī)科學(xué)家和工程師測(cè)試圖像算法。Candès檢查的圖像質(zhì)量非常差，充滿了噪聲，他認(rèn)為名叫L1-minimization的數(shù)學(xué)算法能去除掉噪聲條紋，結(jié)果算法真的起作用了，突然就覺得好神奇哦，“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.。而且在圖像變干凈的同時(shí)，他發(fā)現(xiàn)圖像的細(xì)節(jié)出人意料的完美起來。
某一日Candes去幼兒園接孩子，正好遇上了也在接孩子的陶哲軒，兩人攀談的過程中他提到了自己手頭的困難，于是陶哲軒也開始想這個(gè)問題，它們成為兩人合作的壓縮感知領(lǐng)域第一篇論文的基礎(chǔ)。Emmanuel Candès認(rèn)為壓縮感知（簡寫CS）技術(shù)具有廣闊的應(yīng)用前景，比如MRI，數(shù)碼相機(jī)。數(shù)碼相機(jī)鏡頭收集了大量的數(shù)據(jù)，然后再壓縮，壓縮時(shí)丟棄掉90%的數(shù)據(jù)。如果有CS，如果你的照相機(jī)收集了如此多的數(shù)據(jù)只是為了隨后的刪除，那么為什么不一開始就丟棄那90%的數(shù)據(jù)，直接去除冗余信息不僅可以節(jié)省電池電量，還能節(jié)省空間。
/***********************大牛介紹***********************/
陶哲軒：澳籍華人數(shù)學(xué)家，童年時(shí)期即天資過人，目前主要研究調(diào)和分析、偏微分方程、組合數(shù)學(xué)、解析數(shù)論和表示論。24歲起，他在加利福尼亞大學(xué)洛杉磯分校擔(dān)任教授。他現(xiàn)在為該校終身數(shù)學(xué)教授。
Emmanuel Candes?（C牛）是斯坦福大學(xué)的數(shù)學(xué)、統(tǒng)計(jì)學(xué)，電子工程榮譽(yù)教授，同時(shí)也是應(yīng)用計(jì)算數(shù)學(xué)領(lǐng)域的教授。他的?研究領(lǐng)域主要是在這種數(shù)學(xué)協(xié)調(diào)分析、數(shù)學(xué)優(yōu)化、統(tǒng)計(jì)估測(cè)，以及在影像科學(xué)、信號(hào)研究。?Emmanuel Candes?教?授曾獲數(shù)項(xiàng)國際獎(jiǎng)項(xiàng)，包括國家科學(xué)基金會(huì)最高個(gè)人獎(jiǎng)項(xiàng)（該獎(jiǎng)項(xiàng)主要獎(jiǎng)勵(lì)?35?歲以下的學(xué)者）、?2008?年信息社?會(huì)理論論文獎(jiǎng)，以及國際行業(yè)應(yīng)用數(shù)學(xué)學(xué)會(huì)授予的獎(jiǎng)項(xiàng)等等。
David Donoho ??WaveLab是小波和相關(guān)的時(shí)頻變換的一個(gè)Matlab例程庫，由美國斯坦福大學(xué)的donoho維護(hù)
/***********************基本思想***********************/
壓縮感知的概念：
將未知的要獲得的信號(hào)記為AK，它是一個(gè)波形。我們希望它越不連續(xù)越好，越擴(kuò)散越好，而我所要做的是按照?一定的順序獲得圖像信號(hào)的信息。我們按照高斯分布來收集數(shù)據(jù)，而不是線性的，所以我們只會(huì)有少量的感測(cè)次數(shù)，而這些數(shù)據(jù)?的相關(guān)性非常低。
壓縮的意思，是指比較先前及當(dāng)前數(shù)據(jù)的差異，并記錄下這些差異而減少?需儲(chǔ)存的資料量。對(duì)于壓縮感知的問題比壓縮難多了，像是我們要收集怎樣分布的數(shù)據(jù)、如何收集、保留一些什?么系數(shù)，從而得到最佳的結(jié)果。我們會(huì)得到一些機(jī)變，保留最大的，最有意義的系數(shù)在里頭。我們可以做一些抽樣，把最重要的保留下來。一個(gè)信號(hào)，我們知道它是非常好的，但這個(gè)信號(hào)完全是稀疏的，可能并不是我們要損失掉的。
對(duì)核磁共振的圖像，來看一下這些系數(shù)，?6000?個(gè)不連續(xù)性系數(shù)，我說我們只?要看?1800?不連續(xù)的測(cè)量，讓我們看有什么變化，讓我們看看重建后的圖片，這些圖片是非常接近真實(shí)圖像的，?我們可以用少于三倍或甚至四倍的測(cè)量次數(shù)而得到一個(gè)非常接近的結(jié)果。
感知壓縮難點(diǎn)在于，壓縮后的數(shù)據(jù)并不是壓縮前的數(shù)據(jù)的一個(gè)子集，并不是說，本來有照相機(jī)的感光器上有一千萬個(gè)像素，扔掉其中八百萬個(gè)，剩下的兩百萬個(gè)采集到的就是壓縮后的圖像，──這樣只能采集到不完整的一小塊圖像，有些信息被永遠(yuǎn)的丟失了而且不可能被恢復(fù)。
如果要想采集很少一部分?jǐn)?shù)據(jù)并且指望從這些少量數(shù)據(jù)中「解壓縮」出大量信息，就需要保證：第一：這些少量的采集到的數(shù)據(jù)包含了原信號(hào)的全局信息，第二：存在一種算法能夠從這些少量的數(shù)據(jù)中還原出原先的信息來。
有趣的是，在某些特定的場(chǎng)合，上述第一件事情是自動(dòng)得到滿足的。最典型的例子就是醫(yī)學(xué)圖像成像，例如斷層掃描（CT）技術(shù)和核磁共振（MRI）技術(shù)。對(duì)這兩種技術(shù)稍有了解的人都知道，這兩種成像技術(shù)中，儀器所采集到的都不是直接的圖像像素，而是圖像經(jīng)歷過全局傅立葉變換后的數(shù)據(jù)。也就是說，每一個(gè)單獨(dú)的數(shù)據(jù)都在某種程度上包含了全圖像的信息。在這種情況下，去掉一部分采集到的數(shù)據(jù)并不會(huì)導(dǎo)致一部分圖像信息永久的丟失（它們?nèi)耘f被包含在其它數(shù)據(jù)里）。這正是我們想要的情況。
上述第二件事就要?dú)w功于陶哲軒和坎戴的工作了。他們的工作指出，如果假定信號(hào)（無論是圖像還是聲音還是其他別的種類的信號(hào)）滿足某種特定的「稀疏性」，那么從這些少量的測(cè)量數(shù)據(jù)中，確實(shí)有可能還原出原始的較大的信號(hào)來，其中所需要的計(jì)算部分是一個(gè)復(fù)雜的迭代優(yōu)化過程，即所謂的「L1-最小化」算法。
把上述兩件事情放在一起，我們就能看到這種模式的優(yōu)點(diǎn)所在。它意味著：我們可以在采集數(shù)據(jù)的時(shí)候只簡單采集一部分?jǐn)?shù)據(jù)（「壓縮感知」），然后把復(fù)雜的部分交給數(shù)據(jù)還原的這一端來做，正好匹配了我們期望的格局。在醫(yī)學(xué)圖像領(lǐng)域里，這個(gè)方案特別有好處，因?yàn)椴杉瘮?shù)據(jù)的過程往往是對(duì)病人帶來很大麻煩甚至身體傷害的過程。以 X 光斷層掃描為例，眾所周知 X 光輻射會(huì)對(duì)病人造成身體損害，而「壓縮感知」就意味著我們可以用比經(jīng)典方法少得多的輻射劑量來進(jìn)行數(shù)據(jù)采集，這在醫(yī)學(xué)上的意義是不言而喻的。
/***********************基本概念詳細(xì)說明舉例***********************/
本部分為陶哲軒在一篇blog中對(duì)于comprehensive sensing 文章翻譯過來的精華部分，提取了重點(diǎn)，并加入了一些理解，這里用來解釋CS的概念堪稱經(jīng)典。
相機(jī)的用途，自然是記錄圖像。為了簡化論述，我們把圖像假設(shè)成一個(gè)長方形陣列，比如說一個(gè)1024×2048像素的陣列（這樣就總共是二百萬像素）。為了省略彩色的問題（這個(gè)比較次要），我們就假設(shè)只需要黑白圖像，那么每個(gè)像素就可以用一個(gè)整型的灰度值來計(jì)量其亮度（例如用八位整型數(shù)表示0到255，16位表示0到65535）。接下來，按照最最簡化的說法，傳統(tǒng)相機(jī)會(huì)測(cè)量每一個(gè)像素的亮度（在上述例子中就是二百萬個(gè)測(cè)量值），結(jié)果得到的圖片文件就比較大（用8位灰度值就是2MB（1024*2048*8b），16位灰度就是4MB）。數(shù)學(xué)上就認(rèn)為這個(gè)文件是用超高維矢量值描繪的（在本例中就是約二百萬維）,進(jìn)行。
在我開始講“壓縮感知”這個(gè)新故事之前，必須先快速回顧一下“老式壓縮”的舊故事。（已經(jīng)了解圖像壓縮算法的讀者可以跳過這幾段。）
老式壓縮：
怎么樣壓縮圖像？方式多種多樣，其中有些非常先進(jìn)，不過我來試試用一種不太高科技的（而且也不太精確的）說法來描述一下這些先進(jìn)技術(shù)。圖像通常都含有大片無細(xì)節(jié)部分–比如在風(fēng)景照里面，將近一半的畫面都可能被單色的天空背景占據(jù)。我們假設(shè)提取一個(gè)大方塊，比方說100×100像素，其中完全是同一顏色的——假設(shè)是全白的吧。無壓縮時(shí)，這個(gè)方塊要占10000字節(jié)存儲(chǔ)空間（按照8位灰度算）；但是我們可以只記錄這個(gè)方塊的維度和坐標(biāo)，還有填充整個(gè)方塊的單一顏色；這樣總共也只要記錄四五個(gè)字節(jié)，省下了可觀的空間。不過在現(xiàn)實(shí)中，壓縮效果沒有這么好，因?yàn)楸砻婵磥頉]有細(xì)節(jié)的地方其實(shí)是有著細(xì)微的色差的。所以，給定一個(gè)無細(xì)節(jié)方塊，我們記錄其平均色值，就把圖片中這一塊區(qū)域提取出來，只留下微小的殘余誤差。接下來就可以繼續(xù)選取更多無細(xì)節(jié)的方塊，抽象成單色色塊。最后剩下的是亮度（色彩強(qiáng)度）很小的，肉眼無法察覺的細(xì)節(jié)。于是就可以拋棄這些剩余的細(xì)節(jié)，只需要記錄那些“可見”色塊的大小，位置和亮度。日后則可以反向操作，重建出比原始圖像質(zhì)量稍低一些，占空間卻小得多的復(fù)制圖片。
其實(shí)上述的算法并不適合處理顏色劇烈變動(dòng)的情況，所以在實(shí)際應(yīng)用中不很有效。事實(shí)上，更好的辦法不是用均勻色塊，而是用“不均勻”的色塊——比方說右半邊色彩強(qiáng)度平均值大于左半邊這樣的色塊。這種情況可以用（二維）Haar小波系統(tǒng)來描述。后來人們又發(fā)現(xiàn)一種”更平滑的”小波系統(tǒng)更能夠避免誤差，不過這都是技術(shù)細(xì)節(jié)，我們就不深入討論了。然而所有這些系統(tǒng)的原理都是相同的：把原始圖像表示為不同“小波（類似于上文中的色塊）”的線性疊加，記錄顯著的（高強(qiáng)度的）小波的系數(shù)，放棄掉（或者用閾值排除掉）剩下的小波系數(shù)。這種“小波系數(shù)硬閾值”壓縮算法沒有實(shí)際應(yīng)用的算法（比如JPEG 2000標(biāo)準(zhǔn)中所定義的）那么精細(xì)，不過多少也能描述壓縮的普遍原理。
總體來講（也是非常簡化的說法），原始的1024×2048圖像可能含有兩百萬自由度，想要用小波來表示這個(gè)圖像的人需要兩百萬個(gè)不同小波才能完美重建。但是典型的有意義的圖像，從小波理論的角度看來是非常稀疏的，也就是可壓縮的：可能只需要十萬個(gè)小波就已經(jīng)足夠獲取圖像所有的可見細(xì)節(jié)了，其余一百九十萬小波只貢獻(xiàn)很少量的，大多數(shù)觀測(cè)者基本看不見的“隨機(jī)噪聲”。（這也不是永遠(yuǎn)適用：含有大量紋理的圖像–比如毛發(fā)、毛皮的圖像——用小波算法特別難壓縮，也是圖像壓縮算法的一大挑戰(zhàn)。But that is another story。）
接下來呢，如果我們（或者不如說是相機(jī)）事先知道兩百萬小波系數(shù)里面哪十萬個(gè)是重要的，那camera就可以只計(jì)算這十萬個(gè)系數(shù)，別的就不管了。（對(duì)于單個(gè)系數(shù)的計(jì)算，可以在圖像上應(yīng)用一種合適的filter“濾波器”或叫mask“濾鏡/掩模”，然后計(jì)量過濾出來的每個(gè)像素的色彩強(qiáng)度）但是，相機(jī)是不會(huì)知道哪個(gè)系數(shù)是重要的，所以它只好計(jì)量全部兩百萬個(gè)像素，把整個(gè)圖像轉(zhuǎn)換成基本小波，找出需要留下的那十萬個(gè)主導(dǎo)基本小波，再刪掉其余的。（這當(dāng)然只是真正的圖像壓縮算法的一個(gè)草圖，不過為了便于討論我們還是就這么用吧。）
PS: 經(jīng)典的數(shù)據(jù)壓縮技術(shù)，無論是音頻壓縮（例如 mp3），圖像壓縮（例如 jpeg），視頻壓縮（mpeg），還是一般的編碼壓縮（zip），都是從數(shù)據(jù)本身的特性出發(fā)，尋找并剔除數(shù)據(jù)中隱含的冗余度，從而達(dá)到壓縮的目的。這樣的壓縮有兩個(gè)特點(diǎn)：第一、它是發(fā)生在數(shù)據(jù)已經(jīng)被完整采集到之后；第二、它本身需要復(fù)雜的算法來完成。相較而言，解碼過程反而一般來說在計(jì)算上比較簡單，以音頻壓縮為例，壓制一個(gè) mp3 文件的計(jì)算量遠(yuǎn)大于播放（即解壓縮）一個(gè) mp3 文件的計(jì)算量。
那么，如今的數(shù)碼相機(jī)當(dāng)然已經(jīng)很強(qiáng)大了，沒什么問題干嗎還要改進(jìn)？事實(shí)上，上述的算法，需要收集大量數(shù)據(jù)，但是只需要存儲(chǔ)一部分，在消費(fèi)攝影中是沒有問題的。尤其是隨著數(shù)據(jù)存儲(chǔ)變得很廉價(jià)，現(xiàn)在拍一大堆完全不壓縮的照片也無所謂。而且，盡管出了名地耗電，壓縮所需的運(yùn)算過程仍然算得上輕松。但是，在非消費(fèi)領(lǐng)域的某些應(yīng)用中，這種數(shù)據(jù)收集方式并不可行，特別是在傳感器網(wǎng)絡(luò)中。如果打算用上千個(gè)傳感器來收集數(shù)據(jù)，而這些傳感器需要在固定地點(diǎn)呆上幾個(gè)月那么長的時(shí)間，那么就需要盡可能地便宜和節(jié)能的傳感器——這首先就排除了那些有強(qiáng)大運(yùn)算能力的傳感器（然而——這也相當(dāng)重要——我們?cè)诮邮仗幚頂?shù)據(jù)的接收端仍然需要現(xiàn)代科技提供的奢侈的運(yùn)算能力）。在這類應(yīng)用中，數(shù)據(jù)收集方式越“傻瓜”越好（而且這樣的系統(tǒng)也需要很強(qiáng)壯，比如說，能夠忍受10%的傳感器丟失或者各種噪聲和數(shù)據(jù)缺損）。所謂的「壓縮感知」，也就是說，直接感知壓縮了的信息。
壓縮感知：
這就是壓縮感知的用武之地了。其理論依據(jù)是：如果只需要10萬個(gè)分量就可以重建絕大部分的圖像，那何必還要做所有的200萬次測(cè)量，只做10萬次不就夠了嗎？（在實(shí)際應(yīng)用中，我們會(huì)留一個(gè)安全余量，比如說測(cè)量30萬像素，以應(yīng)付可能遭遇的所有問題，從干擾到量化噪聲，以及恢復(fù)算法的故障。）這樣基本上能使節(jié)能上一個(gè)數(shù)量級(jí)，這對(duì)消費(fèi)攝影沒什么意義，對(duì)感知器網(wǎng)絡(luò)而言卻有實(shí)實(shí)在在的好處。
不過，正像我前面說的，相機(jī)自己不會(huì)預(yù)先知道兩百萬小波系數(shù)中需要記錄哪十萬個(gè)。要是相機(jī)選取了另外10萬（或者30萬），反而把圖片中所有有用的信息都扔掉了怎么辦？
※※※※※※※※※※※※※※※
解決的辦法簡單但是不太直觀。就是用非小波的算法來做30萬個(gè)測(cè)量——盡管我前面確實(shí)講過小波算法是觀察和壓縮圖像的最佳手段。實(shí)際上最好的測(cè)量其實(shí)應(yīng)該是（偽）隨機(jī)測(cè)量——比如說隨機(jī)生成30萬個(gè)濾鏡（mask）圖像并測(cè)量真實(shí)圖像與每個(gè)mask的相關(guān)程度。這樣，圖像與mask之間的這些測(cè)量結(jié)果（也就是“相關(guān)性”）很有可能是非常小非常隨機(jī)的。但是——這是關(guān)鍵所在——構(gòu)成圖像的2百萬種可能的小波函數(shù)會(huì)在這些隨機(jī)的mask的測(cè)量下生成自己特有的“特征”，它們每一個(gè)都會(huì)與某一些mask成正相關(guān)，與另一些mask成負(fù)相關(guān)，但是與更多的mask不相關(guān)。可是（在極大的概率下）2百萬個(gè)特征都各不相同；這就導(dǎo)致，其中任意十萬個(gè)的線性組合仍然是各不相同的（以線性代數(shù)的觀點(diǎn)來看，這是因?yàn)橐粋€(gè)30萬維線性子空間中任意兩個(gè)10萬維的子空間幾乎互不相交）。因此，理論上是有可能從這30萬個(gè)隨機(jī)mask數(shù)據(jù)中恢復(fù)圖像的（至少可以恢復(fù)圖像中的10萬個(gè)主要細(xì)節(jié)）。簡而言之，我們是在討論一個(gè)哈希函數(shù)的線性代數(shù)版本。
PS: 這里的原理就是說，如果3維線性子空間中的任意兩個(gè)2維子空間是線性相關(guān)的話，比如：
①3x+2y=8
②6x+4y=16
③4x+5y=10
中，①②就是線性相關(guān)的，①③不是線性相關(guān)的。將200萬個(gè)小波函數(shù)降維到30萬個(gè)掩模基的過程就是類似去掉①②中冗余基的過程。
然而這種方式仍然存在兩個(gè)技術(shù)問題。首先是噪聲問題：10萬個(gè)小波系數(shù)的疊加并不能完全代表整幅圖像，另190萬個(gè)系數(shù)也有少許貢獻(xiàn)。這些小小貢獻(xiàn)有可能會(huì)干擾那10萬個(gè)小波的特征，這就是所謂的“失真”問題。第二個(gè)問題是如何運(yùn)用得到的30萬測(cè)量數(shù)據(jù)來重建圖像。
我們先來關(guān)注后一個(gè)問題（怎樣恢復(fù)圖像）。如果我們知道了2百萬小波中哪10萬個(gè)是有用的，那就可以使用標(biāo)準(zhǔn)的線性代數(shù)方法（高斯消除法，最小二乘法等等）來重建信號(hào)。（這正是線性編碼最大的優(yōu)點(diǎn)之一——它們比非線性編碼更容易求逆。大多數(shù)哈希變換實(shí)際上是不可能求逆的——這在密碼學(xué)上是一大優(yōu)勢(shì)，在信號(hào)恢復(fù)中卻不是。）可是，就像前面說的那樣，我們事前并不知道哪些小波是有用的。怎么找出來呢？一個(gè)單純的最小二乘近似法會(huì)得出牽扯到全部2百萬系數(shù)的可怕結(jié)果，生成的圖像也含有大量顆粒噪點(diǎn)。要不然也可以代之以一種強(qiáng)力搜索，為每一組可能的10萬關(guān)鍵系數(shù)都做一次線性代數(shù)處理，不過這樣做的耗時(shí)非常恐怖（總共要考慮大約10的17萬次方個(gè)組合！），而且這種強(qiáng)力搜索通常是NP完備的（其中有些特例是所謂的“子集合加總”問題）。不過還好，還是有兩種可行的手段來恢復(fù)數(shù)據(jù)：
?匹配追蹤：找到一個(gè)其標(biāo)記看上去與收集到的數(shù)據(jù)相關(guān)的小波；在數(shù)據(jù)中去除這個(gè)標(biāo)記的所有印跡；不斷重復(fù)直到我們能用小波標(biāo)記“解釋”收集到的所有數(shù)據(jù)。
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. 就是先找出一個(gè)貌似是基的小波，然后去掉該小波在圖像中的分量，迭代直到找出所有10w個(gè)小波.
?基追蹤（又名L1模最小化）：在所有與(image)數(shù)據(jù)匹配的小波組合中，找到一個(gè)“最稀疏的”基，也就是其中所有系數(shù)的絕對(duì)值總和越小越好。（這種最小化的結(jié)果趨向于迫使絕大多數(shù)系數(shù)都消失了。）這種最小化算法可以利用單純形法之類的凸規(guī)劃算法，在合理的時(shí)間內(nèi)計(jì)算出來。
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.
現(xiàn)在已經(jīng)有嚴(yán)密的結(jié)果顯示，對(duì)原始圖像設(shè)定不同的壓縮率或稀疏性，這兩種算法完美或近似完美地重建圖像的成功率都很高。匹配追蹤法通常比較快，而基追蹤算法在考慮到噪聲時(shí)則顯得比較準(zhǔn)確。這些算法確切的適用范圍問題在今天仍然是非常熱門的研究領(lǐng)域。（說來遺憾，目前還沒有出現(xiàn)對(duì)P不等于NP問題的應(yīng)用；如果一個(gè)重建問題（在考慮到測(cè)量矩陣時(shí)）是NP完備的，那它剛好就不能用上述算法解決。）
由于壓縮感知還是一個(gè)相當(dāng)新的領(lǐng)域（尤其是嚴(yán)密的數(shù)學(xué)結(jié)果剛剛出現(xiàn)），現(xiàn)在就期望這個(gè)技術(shù)應(yīng)用到實(shí)用的傳感器上還為時(shí)尚早。不過已經(jīng)有概念驗(yàn)證模型出現(xiàn)了，其中最著名的是Rice大學(xué)研制的單像素相機(jī)。
最后必須提到的是，壓縮感知技術(shù)是一種抽象的數(shù)學(xué)概念，而不是具體的操作方案，它可以應(yīng)用到成像以外的許多領(lǐng)域。以下只是其中幾個(gè)例子：
? 磁共振成像(MRI)。在醫(yī)學(xué)上，磁共振的工作原理是做許多次（但次數(shù)仍是有限的）測(cè)量（基本上就是對(duì)人體圖像進(jìn)行離散拉東變換（也叫X光變換）），再對(duì)數(shù)據(jù)進(jìn)行加工來生成圖像（在這里就是人體內(nèi)水的密度分布圖像）。由于測(cè)量次數(shù)必須很多，整個(gè)過程對(duì)患者來說太過漫長。壓縮感知技術(shù)可以顯著減少測(cè)量次數(shù)，加快成像（甚至有可能做到實(shí)時(shí)成像，也就是核磁共振的視頻而非靜態(tài)圖像）。此外我們還可以以測(cè)量次數(shù)換圖像質(zhì)量，用與原來一樣的測(cè)量次數(shù)可以得到好得多的圖像分辨率。ps:在C牛的video中也有提到
?天文學(xué)。許多天文現(xiàn)象（如脈沖星）具有多種頻率震蕩特性，使其在頻域上是高度稀疏也就是可壓縮的。壓縮感知技術(shù)將使我們能夠在時(shí)域內(nèi)測(cè)量這些現(xiàn)象（即記錄望遠(yuǎn)鏡數(shù)據(jù)）并能夠精確重建原始信號(hào)，即使原始數(shù)據(jù)不完整或者干擾嚴(yán)重（原因可能是天氣不佳，上機(jī)時(shí)間不夠，或者就是因?yàn)榈厍蜃詡魇刮覀兊貌坏饺珪r(shí)序的數(shù)據(jù)）。
?線性編碼。壓縮感知技術(shù)提供了一個(gè)簡單的方法，讓多個(gè)傳送者可以將其信號(hào)帶糾錯(cuò)地合并傳送，這樣即使輸出信號(hào)的一大部分丟失或毀壞，仍然可以恢復(fù)出原始信號(hào)。例如，可以用任意一種線性編碼把1000比特信息編碼進(jìn)一個(gè)3000比特的流；那么，即使其中300位被（惡意）毀壞，原始信息也能完全無損失地完美重建。這是因?yàn)閴嚎s感知技術(shù)可以把破壞動(dòng)作本身看作一個(gè)稀疏的信號(hào)（只集中在3000比特中的300位）。
許多這種應(yīng)用都還只停留在理論階段，可是這種算法能夠影響測(cè)量和信號(hào)處理中如此之多的領(lǐng)域，其潛力實(shí)在是振奮人心。筆者自己最有成就感的就是能看到自己在純數(shù)學(xué)領(lǐng)域的工作（例如估算傅立葉子式的行列式或單數(shù)值）最終具備造福現(xiàn)實(shí)世界的前景。
/***********************CS研究內(nèi)容***********************/
研究壓縮感知的內(nèi)容有幾塊呢？
（1）壓縮感知理論，比如測(cè)量矩陣，重建性能分析，測(cè)量數(shù)據(jù)量化影響；
（2）優(yōu)化算法，本質(zhì)上是重建算法優(yōu)化，比如線性規(guī)劃（LP）、貝葉斯優(yōu)化等等；
（3）實(shí)際的應(yīng)用，壓縮？后處理？分類？等等
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.?
最近的理論研究主要集中在 ①需要多少多維測(cè)度才能重建原始信號(hào) ②分解信號(hào)所需的非線性重建技術(shù)；還有能夠直接進(jìn)行多維信號(hào)選擇的感知硬件(sensing hardware)。
/***********************CS的壓縮/解壓效果***********************/
由于剛剛看這一方面的資料，未免經(jīng)驗(yàn)不足，就借鑒了其他人（Ganer）在該領(lǐng)域的探究結(jié)果，他的博客中寫到：
很多mpressive sensing的實(shí)際用于信號(hào)采集效果其實(shí)并不是很好。
就從我的實(shí)驗(yàn)而言，對(duì)于圖像壓縮甚至?xí)畹暮?#xff0c;遠(yuǎn)遠(yuǎn)低于傳統(tǒng)的壓縮方式。
那就不難有學(xué)者發(fā)出感嘆，實(shí)際上compressive sensing 就是depressive sensing了。
我的理解是什么呢？有2點(diǎn)牢牢記住的
（1）compressive sensing實(shí)際上是對(duì)信號(hào)采集的顛覆性的理論，打破了乃奎斯特采樣（也稱香農(nóng)采樣）。
? ? ? ? 實(shí)際上，大部分信號(hào)是稀疏的，沒有必要用乃奎斯特采樣，進(jìn)行時(shí)間離散化。
? ? ? ? 注意兩點(diǎn)：（1）乃奎斯特采樣對(duì)信號(hào)沒有稀疏性的假設(shè)；
? ? ? ? ? ? ? ? ? ? ? ? ?（2）CS對(duì)信號(hào)有稀疏性假設(shè)，既K稀疏；
? ? ? ?那么，信號(hào)采集過程也就是說從A2D，變成了A2I。
? ? ? 但是在實(shí)際應(yīng)用角度，2者結(jié)合會(huì)有很大的收益。（個(gè)人觀點(diǎn)）
（2）compressive sensing本事是最大后驗(yàn)（MAP）解碼，這點(diǎn)比傳統(tǒng)的方式要更為”先進(jìn)“，也更為”危險(xiǎn)“。
關(guān)于Compressive Sensing更多的學(xué)習(xí)資料將繼續(xù)更新，敬請(qǐng)關(guān)注本博客和新浪微博Sophia_qing。
References：
1.?Compressed sensing and single-pixel cameras?- Terrytao
2.?斯坦福大學(xué)Emmanuel Candes教授：壓縮感知?video2
3.?An Introduction to Compressed Sensing?（斯坦福課程，可根據(jù)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.
總結(jié)
以上是生活随笔為你收集整理的初识压缩感知 compressive sensing的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Matlab中的CVX工具包安装
- 下一篇： 华为2016年应届毕业生招聘公告