淺談壓縮感知（八）：兩篇科普文章

分享兩篇來(lái)自科學(xué)松鼠會(huì)的科普性文章：

1、壓縮感知與單像素相機(jī)(陶哲軒,Terence Tao)

2、填補(bǔ)空白：用數(shù)學(xué)方法將低分辨率圖像變成高分辨率圖像(Jordan Ellenberg)

英文名：Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples

一、壓縮感知與單像素相機(jī)

木遙按：這是數(shù)學(xué)家陶哲軒在他自己的blog上寫(xiě)的一篇科普文章，討論的是近年來(lái)在應(yīng)用數(shù)學(xué)領(lǐng)域里最熱門(mén)的話題之一：壓縮感知（compressed sensing）。所謂壓縮感知，最核心的概念在于試圖從原理上降低對(duì)一個(gè)信號(hào)進(jìn)行測(cè)量的成本。比如說(shuō)，一個(gè)信號(hào)包含一千個(gè)數(shù)據(jù)，那么按照傳統(tǒng)的信號(hào)處理理論，至少需要做一千次測(cè)量才能完整的復(fù)原這個(gè)信號(hào)。這就相當(dāng)于是說(shuō)，需要有一千個(gè)方程才能精確地解出一千個(gè)未知數(shù)來(lái)。但是壓縮感知的想法是假定信號(hào)具有某種特點(diǎn)（比如文中所描述得在小波域上系數(shù)稀疏的特點(diǎn)），那么就可以只做三百次測(cè)量就完整地復(fù)原這個(gè)信號(hào)（這就相當(dāng)于只通過(guò)三百個(gè)方程解出一千個(gè)未知數(shù)）?？上攵?，這件事情包含了許多重要的數(shù)學(xué)理論和廣泛的應(yīng)用前景，因此在最近三四年里吸引了大量注意力，得到了非常蓬勃的發(fā)展。陶哲軒本身是這個(gè)領(lǐng)域的奠基人之一（可以參考《陶哲軒：長(zhǎng)大的神童》一文），因此這篇文章的權(quán)威性毋庸諱言。另外，這也是比較少見(jiàn)的由一流數(shù)學(xué)家直接撰寫(xiě)的關(guān)于自己前沿工作的普及性文章。需要說(shuō)明的是，這篇文章是雖然是寫(xiě)給非數(shù)學(xué)專業(yè)的讀者，但是也并不好懂，也許具有一些理工科背景會(huì)更容易理解一些。

【作者 Terence Tao；譯者 山寨盲流，他的更多譯作在這，那；校對(duì) 木遙】

最近有不少人問(wèn)我究竟"壓縮感知"是什么意思（特別是隨著最近這個(gè)概念名聲大噪），所謂“單像素相機(jī)”又是怎樣工作的（又怎么能在某些場(chǎng)合比傳統(tǒng)相機(jī)有優(yōu)勢(shì)呢）。這個(gè)課題已經(jīng)有了大量文獻(xiàn)，不過(guò)對(duì)于這么一個(gè)相對(duì)比較新的領(lǐng)域，還沒(méi)有一篇優(yōu)秀的非技術(shù)性介紹。所以筆者在此小做嘗試，希望能夠?qū)Ψ菙?shù)學(xué)專業(yè)的讀者有所幫助。

具體而言我將主要討論攝像應(yīng)用，盡管壓縮傳感作為測(cè)量技術(shù)應(yīng)用于比成像廣泛得多的領(lǐng)域（例如天文學(xué)，核磁共振，統(tǒng)計(jì)選取，等等），我將在帖子結(jié)尾簡(jiǎn)單談?wù)勥@些領(lǐng)域。

相機(jī)的用途，自然是記錄圖像。為了簡(jiǎn)化論述，我們把圖像假設(shè)成一個(gè)長(zhǎng)方形陣列，比如說(shuō)一個(gè)1024x2048像素的陣列（這樣就總共是二百萬(wàn)像素）。為了省略彩色的問(wèn)題（這個(gè)比較次要），我們就假設(shè)只需要黑白圖像，那么每個(gè)像素就可以用一個(gè)整型的灰度值來(lái)計(jì)量其亮度（例如用八位整型數(shù)表示0到255，16位表示0到65535）。

接下來(lái)，按照最最簡(jiǎn)化的說(shuō)法，傳統(tǒng)相機(jī)會(huì)測(cè)量每一個(gè)像素的亮度（在上述例子中就是二百萬(wàn)個(gè)測(cè)量值），結(jié)果得到的圖片文件就比較大（用8位灰度值就是2MB，16位灰度就是4MB）。數(shù)學(xué)上就認(rèn)為這個(gè)文件是用超高維矢量值描繪的（在本例中就是約二百萬(wàn)維）。

在我開(kāi)始講“壓縮感知”這個(gè)新故事之前，必須先快速回顧一下“老式壓縮”的舊故事。（已經(jīng)了解圖像壓縮算法的讀者可以跳過(guò)這幾段。）

上述的圖片會(huì)占掉相機(jī)的很多存儲(chǔ)空間（上傳到計(jì)算機(jī)里還占磁盤(pán)空間），在各種介質(zhì)之間傳輸?shù)臅r(shí)候也要浪費(fèi)時(shí)間。于是，相機(jī)帶有顯著壓縮圖像的功能就順理成章了（通常能從2MB那么大壓縮到十分之一——200KB的一小坨）。關(guān)鍵是盡管“所有圖片”所構(gòu)成的空間要占用2MB的“自由度”或者說(shuō)“熵”，由“有意義的圖片”所構(gòu)成的空間其實(shí)要小得多，尤其是如果人們?cè)敢饨档鸵稽c(diǎn)圖像質(zhì)量的話。（實(shí)際上，如果一個(gè)人真的利用所有的自由度隨機(jī)生成一幅圖片，他不大可能得到什么有意義的圖像，而是得到相當(dāng)于電視熒屏上的靜電雪花那樣的隨機(jī)噪聲之類。）

怎么樣壓縮圖像？方式多種多樣，其中有些非常先進(jìn)，不過(guò)我來(lái)試試用一種不太高科技的（而且也不太精確的）說(shuō)法來(lái)描述一下這些先進(jìn)技術(shù)。圖像通常都含有大片無(wú)細(xì)節(jié)部分--比如在風(fēng)景照里面，將近一半的畫(huà)面都可能被單色的天空背景占據(jù)。我們假設(shè)提取一個(gè)大方塊，比方說(shuō)100x100像素，其中完全是同一顏色的——假設(shè)是全白的吧。無(wú)壓縮時(shí)，這個(gè)方塊要占10000字節(jié)存儲(chǔ)空間（按照8位灰度算）；但是我們可以只記錄這個(gè)方塊的維度和坐標(biāo)，還有填充整個(gè)方塊的單一顏色；這樣總共也只要記錄四五個(gè)字節(jié)，省下了可觀的空間。不過(guò)在現(xiàn)實(shí)中，壓縮效果沒(méi)有這么好，因?yàn)楸砻婵磥?lái)沒(méi)有細(xì)節(jié)的地方其實(shí)是有著細(xì)微的色差的。所以，給定一個(gè)無(wú)細(xì)節(jié)方塊，我們記錄其平均色值，就把圖片中這一塊區(qū)域抽象成了單色色塊，只留下微小的殘余誤差。接下來(lái)就可以繼續(xù)選取更多色彩可見(jiàn)的方塊，抽象成單色色塊。最后剩下的是亮度（色彩強(qiáng)度）很小的，肉眼無(wú)法察覺(jué)的細(xì)節(jié)。于是就可以拋棄這些剩余的細(xì)節(jié)，只需要記錄那些“可見(jiàn)”色塊的大小，位置和亮度。日后則可以反向操作，重建出比原始圖像質(zhì)量稍低一些，占空間卻小得多的復(fù)制圖片。

其實(shí)上述的算法并不適合處理顏色劇烈變動(dòng)的情況，所以在實(shí)際應(yīng)用中不很有效。事實(shí)上，更好的辦法不是用均勻色塊，而是用“不均勻”的色塊——比方說(shuō)右半邊色彩強(qiáng)度平均值大于左半邊這樣的色塊。這種情況可以用（二維）Haar小波系統(tǒng)來(lái)描述。后來(lái)人們又發(fā)現(xiàn)一種"更平滑的"小波系統(tǒng)更能夠避免誤差，不過(guò)這都是技術(shù)細(xì)節(jié)，我們就不深入討論了。然而所有這些系統(tǒng)的原理都是相同的：把原始圖像表示為不同“小波（類似于上文中的色塊）”的線性疊加，記錄顯著的（高強(qiáng)度的）小波的系數(shù)，放棄掉（或者用閾值排除掉）剩下的小波系數(shù)。這種“小波系數(shù)硬閾值”壓縮算法沒(méi)有實(shí)際應(yīng)用的算法（比如JPEG 2000標(biāo)準(zhǔn)中所定義的）那么精細(xì)，不過(guò)多少也能描述壓縮的普遍原理。

總體來(lái)講（也是非常簡(jiǎn)化的說(shuō)法），原始的1024x2048圖像可能含有兩百萬(wàn)自由度，想要用小波來(lái)表示這個(gè)圖像的人需要兩百萬(wàn)個(gè)不同小波才能完美重建。但是典型的有意義的圖像，從小波理論的角度看來(lái)是非常稀疏的，也就是可壓縮的：可能只需要十萬(wàn)個(gè)小波就已經(jīng)足夠獲取圖像所有的可見(jiàn)細(xì)節(jié)了，其余一百九十萬(wàn)小波只貢獻(xiàn)很少量的，大多數(shù)觀測(cè)者基本看不見(jiàn)的“隨機(jī)噪聲”。（這也不是永遠(yuǎn)適用：含有大量紋理的圖像--比如毛發(fā)、毛皮的圖像——用小波算法特別難壓縮，也是圖像壓縮算法的一大挑戰(zhàn)。不過(guò)這是另一個(gè)故事了。）

接下來(lái)呢，如果我們（或者不如說(shuō)是相機(jī)）事先知道兩百萬(wàn)小波系數(shù)里面哪十萬(wàn)個(gè)是重要的，那就可以只計(jì)量這十萬(wàn)個(gè)系數(shù)，別的就不管了。（在圖像上設(shè)置一種合適的“過(guò)濾器”或叫“濾鏡”，然后計(jì)量過(guò)濾出來(lái)的每個(gè)像素的色彩強(qiáng)度，是一種可行的系數(shù)計(jì)量方法。）但是，相機(jī)是不會(huì)知道哪個(gè)系數(shù)是重要的，所以它只好計(jì)量全部?jī)砂偃f(wàn)個(gè)像素，把整個(gè)圖像轉(zhuǎn)換成基本小波，找出需要留下的那十萬(wàn)個(gè)主導(dǎo)基本小波，再刪掉其余的。（這當(dāng)然只是真正的圖像壓縮算法的一個(gè)草圖，不過(guò)為了便于討論我們還是就這么用吧。）

那么，如今的數(shù)碼相機(jī)當(dāng)然已經(jīng)很強(qiáng)大了，沒(méi)什么問(wèn)題干嗎還要改進(jìn)？事實(shí)上，上述的算法，需要收集大量數(shù)據(jù)，但是只需要存儲(chǔ)一部分，在消費(fèi)攝影中是沒(méi)有問(wèn)題的。尤其是隨著數(shù)據(jù)存儲(chǔ)變得很廉價(jià)，現(xiàn)在拍一大堆完全不壓縮的照片也無(wú)所謂。而且，盡管出了名地耗電，壓縮所需的運(yùn)算過(guò)程仍然算得上輕松。但是，在非消費(fèi)領(lǐng)域的某些應(yīng)用中，這種數(shù)據(jù)收集方式并不可行，特別是在傳感器網(wǎng)絡(luò)中。如果打算用上千個(gè)傳感器來(lái)收集數(shù)據(jù)，而這些傳感器需要在固定地點(diǎn)呆上幾個(gè)月那么長(zhǎng)的時(shí)間，那么就需要盡可能地便宜和節(jié)能的傳感器——這首先就排除了那些有強(qiáng)大運(yùn)算能力的傳感器（然而——這也相當(dāng)重要——我們?cè)诮邮仗幚頂?shù)據(jù)的接收端仍然需要現(xiàn)代科技提供的奢侈的運(yùn)算能力）。在這類應(yīng)用中，數(shù)據(jù)收集方式越“傻瓜”越好（而且這樣的系統(tǒng)也需要很強(qiáng)壯，比如說(shuō)，能夠忍受10%的傳感器丟失或者各種噪聲和數(shù)據(jù)缺損）。

這就是壓縮傳感的用武之地了。其理論依據(jù)是：如果只需要10萬(wàn)個(gè)分量就可以重建絕大部分的圖像，那何必還要做所有的200萬(wàn)次測(cè)量，只做10萬(wàn)次不就夠了嗎？（在實(shí)際應(yīng)用中，我們會(huì)留一個(gè)安全余量，比如說(shuō)測(cè)量30萬(wàn)像素，以應(yīng)付可能遭遇的所有問(wèn)題，從干擾到量化噪聲，以及恢復(fù)算法的故障。）這樣基本上能使節(jié)能上一個(gè)數(shù)量級(jí)，這對(duì)消費(fèi)攝影沒(méi)什么意義，對(duì)傳感器網(wǎng)絡(luò)而言卻有實(shí)實(shí)在在的好處。

不過(guò)，正像我前面說(shuō)的，相機(jī)自己不會(huì)預(yù)先知道兩百萬(wàn)小波系數(shù)中需要記錄哪十萬(wàn)個(gè)。要是相機(jī)選取了另外10萬(wàn)（或者30萬(wàn)），反而把圖片中所有有用的信息都扔掉了怎么辦？

解決的辦法簡(jiǎn)單但是不太直觀。就是用非小波的算法來(lái)做30萬(wàn)個(gè)測(cè)量——盡管我前面確實(shí)講過(guò)小波算法是觀察和壓縮圖像的最佳手段。實(shí)際上最好的測(cè)量其實(shí)應(yīng)該是（偽）隨機(jī)測(cè)量——比如說(shuō)隨機(jī)生成30萬(wàn)個(gè)“濾鏡”圖像并測(cè)量真實(shí)圖像與每個(gè)濾鏡的相關(guān)程度。這樣，圖像與濾鏡之間的這些測(cè)量結(jié)果（也就是“相關(guān)性”）很有可能是非常小非常隨機(jī)的。但是——這是關(guān)鍵所在——構(gòu)成圖像的2百萬(wàn)種可能的小波函數(shù)會(huì)在這些隨機(jī)的濾鏡的測(cè)量下生成自己特有的“特征”，它們每一個(gè)都會(huì)與某一些濾鏡成正相關(guān)，與另一些濾鏡成負(fù)相關(guān)，但是與更多的濾鏡不相關(guān)?？墒牵ㄔ跇O大的概率下）2百萬(wàn)個(gè)特征都各不相同；更有甚者，其中任意十萬(wàn)個(gè)的線性組合仍然是各不相同的（以線性代數(shù)的觀點(diǎn)來(lái)看，這是因?yàn)橐粋€(gè)30萬(wàn)維線性子空間中任意兩個(gè)10萬(wàn)維的子空間極有可能互不相交）。因此，基本上是有可能從這30萬(wàn)個(gè)隨機(jī)數(shù)據(jù)中恢復(fù)圖像的（至少是恢復(fù)圖像中的10萬(wàn)個(gè)主要細(xì)節(jié)）。簡(jiǎn)而言之，我們是在討論一個(gè)哈希函數(shù)的線性代數(shù)版本。

然而這種方式仍然存在兩個(gè)技術(shù)問(wèn)題。首先是噪聲問(wèn)題：10萬(wàn)個(gè)小波系數(shù)的疊加并不能完全代表整幅圖像，另190萬(wàn)個(gè)系數(shù)也有少許貢獻(xiàn)。這些小小貢獻(xiàn)有可能會(huì)干擾那10萬(wàn)個(gè)小波的特征，這就是所謂的“失真”問(wèn)題。第二個(gè)問(wèn)題是如何運(yùn)用得到的30萬(wàn)測(cè)量數(shù)據(jù)來(lái)重建圖像。

我們先來(lái)關(guān)注后一個(gè)問(wèn)題。如果我們知道了2百萬(wàn)小波中哪10萬(wàn)個(gè)是有用的，那就可以使用標(biāo)準(zhǔn)的線性代數(shù)方法（高斯消除法，最小二乘法等等）來(lái)重建信號(hào)。（這正是線性編碼最大的優(yōu)點(diǎn)之一——它們比非線性編碼更容易求逆。大多數(shù)哈希變換實(shí)際上是不可能求逆的——這在密碼學(xué)上是一大優(yōu)勢(shì)，在信號(hào)恢復(fù)中卻不是。）可是，就像前面說(shuō)的那樣，我們事前并不知道哪些小波是有用的。怎么找出來(lái)呢？一個(gè)單純的最小二乘近似法會(huì)得出牽扯到全部2百萬(wàn)系數(shù)的可怕結(jié)果，生成的圖像也含有大量顆粒噪點(diǎn)。要不然也可以代之以一種強(qiáng)力搜索，為每一組可能的10萬(wàn)關(guān)鍵系數(shù)都做一次線性代數(shù)處理，不過(guò)這樣做的耗時(shí)非?？植溃偣惨紤]大約10的17萬(wàn)次方個(gè)組合！），而且這種強(qiáng)力搜索通常是NP完備的（其中有些特例是所謂的“子集合加總”問(wèn)題）。不過(guò)還好，還是有兩種可行的手段來(lái)恢復(fù)數(shù)據(jù)：

? 匹配追蹤：找到一個(gè)其標(biāo)記看上去與收集到的數(shù)據(jù)相關(guān)的小波；在數(shù)據(jù)中去除這個(gè)標(biāo)記的所有印跡；不斷重復(fù)直到我們能用小波標(biāo)記“解釋”收集到的所有數(shù)據(jù)。

? 基追蹤（又名L1模最小化）：在所有與錄得數(shù)據(jù)匹配的小波組合中，找到一個(gè)“最稀疏的”，也就是其中所有系數(shù)的絕對(duì)值總和越小越好。（這種最小化的結(jié)果趨向于迫使絕大多數(shù)系數(shù)都消失了。）這種最小化算法可以利用單純形法之類的凸規(guī)劃算法，在合理的時(shí)間內(nèi)計(jì)算出來(lái)。

需要注意到的是，這類圖像恢復(fù)算法還是需要相當(dāng)?shù)倪\(yùn)算能力的（不過(guò)也還不是太變態(tài)），不過(guò)在傳感器網(wǎng)絡(luò)這樣的應(yīng)用中這不成問(wèn)題，因?yàn)閳D像恢復(fù)是在接收端（這端有辦法連接到強(qiáng)大的計(jì)算機(jī)）而不是傳感器端（這端就沒(méi)辦法了）進(jìn)行的。

現(xiàn)在已經(jīng)有嚴(yán)密的結(jié)果顯示，對(duì)原始圖像設(shè)定不同的壓縮率或稀疏性，這兩種算法完美或近似完美地重建圖像的成功率都很高。匹配追蹤法通常比較快，而基追蹤算法在考慮到噪聲時(shí)則顯得比較準(zhǔn)確。這些算法確切的適用范圍問(wèn)題在今天仍然是非常熱門(mén)的研究領(lǐng)域。（說(shuō)來(lái)遺憾，目前還沒(méi)有出現(xiàn)對(duì)P不等于NP問(wèn)題的應(yīng)用；如果一個(gè)重建問(wèn)題（在考慮到測(cè)量矩陣時(shí)）是NP完備的，那它剛好就不能用上述算法解決。）

由于壓縮傳感還是一個(gè)相當(dāng)新的領(lǐng)域（尤其是嚴(yán)密的數(shù)學(xué)結(jié)果剛剛出現(xiàn)），現(xiàn)在就期望這個(gè)技術(shù)應(yīng)用到實(shí)用的傳感器上還為時(shí)尚早。不過(guò)已經(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)行加工來(lái)生成圖像（在這里就是人體內(nèi)水的密度分布圖像）。由于測(cè)量次數(shù)必須很多，整個(gè)過(guò)程對(duì)患者來(lái)說(shuō)太過(guò)漫長(zhǎng)。壓縮傳感技術(shù)可以顯著減少測(cè)量次數(shù)，加快成像（甚至有可能做到實(shí)時(shí)成像，也就是核磁共振的視頻而非靜態(tài)圖像）。此外我們還可以以測(cè)量次數(shù)換圖像質(zhì)量，用與原來(lái)一樣的測(cè)量次數(shù)可以得到好得多的圖像分辨率。

? 天文學(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è)簡(jiǎn)單的方法，讓多個(gè)傳送者可以將其信號(hào)帶糾錯(cuò)地合并傳送，這樣即使輸出信號(hào)的一大部分丟失或毀壞，仍然可以恢復(fù)出原始信號(hào)。例如，可以用任意一種線性編碼把1000比特信息編碼進(jìn)一個(gè)3000比特的流；那么，即使其中300位被（惡意）毀壞，原始信息也能完全無(wú)損失地完美重建。這是因?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í)世界的前景。

?

二、填補(bǔ)空缺——壓縮感知

紅豬按（by?木遙）

壓縮感知是近年來(lái)極為熱門(mén)的研究前沿，在若干應(yīng)用領(lǐng)域中都引起矚目。關(guān)于這個(gè)題目，松鼠會(huì)已經(jīng)翻譯了兩篇文章，一篇來(lái)自于壓縮感知技術(shù)最初的研究者陶哲軒（鏈接），一篇來(lái)自威斯康辛大學(xué)的數(shù)學(xué)家艾倫伯格（本文正文）。這兩篇文章都是普及性的，但是由于作者是專業(yè)的研究人員，所以事實(shí)上行文仍然偏于晦澀。因此我不揣冒昧，在這里附上一個(gè)畫(huà)蛇添足的導(dǎo)讀，以幫助更多的讀者更好了解這個(gè)新穎的研究領(lǐng)域在理論和實(shí)踐上的意義。

壓縮感知從字面上看起來(lái)，好像是數(shù)據(jù)壓縮的意思，而實(shí)則出于完全不同的考慮。經(jīng)典的數(shù)據(jù)壓縮技術(shù)，無(wú)論是音頻壓縮（例如 mp3），圖像壓縮（例如 jpeg），視頻壓縮（mpeg），還是一般的編碼壓縮（zip），都是從數(shù)據(jù)本身的特性出發(fā)，尋找并剔除數(shù)據(jù)中隱含的冗余度，從而達(dá)到壓縮的目的。這樣的壓縮有兩個(gè)特點(diǎn)：第一、它是發(fā)生在數(shù)據(jù)已經(jīng)被完整采集到之后；第二、它本身需要復(fù)雜的算法來(lái)完成。相較而言，解碼過(guò)程反而一般來(lái)說(shuō)在計(jì)算上比較簡(jiǎn)單，以音頻壓縮為例，壓制一個(gè) mp3 文件的計(jì)算量遠(yuǎn)大于播放（即解壓縮）一個(gè) mp3 文件的計(jì)算量。

稍加思量就會(huì)發(fā)現(xiàn)，這種壓縮和解壓縮的不對(duì)稱性正好同人們的需求是相反的。在大多數(shù)情況下，采集并處理數(shù)據(jù)的設(shè)備，往往是廉價(jià)、省電、計(jì)算能力較低的便攜設(shè)備，例如傻瓜相機(jī)、或者錄音筆、或者遙控監(jiān)視器等等。而負(fù)責(zé)處理（即解壓縮）信息的過(guò)程卻反而往往在大型計(jì)算機(jī)上進(jìn)行，它有更高的計(jì)算能力，也常常沒(méi)有便攜和省電的要求。也就是說(shuō)，我們是在用廉價(jià)節(jié)能的設(shè)備來(lái)處理復(fù)雜的計(jì)算任務(wù)，而用大型高效的設(shè)備處理相對(duì)簡(jiǎn)單的計(jì)算任務(wù)。這一矛盾在某些情況下甚至?xí)鼮榧怃J，例如在野外作業(yè)或者軍事作業(yè)的場(chǎng)合，采集數(shù)據(jù)的設(shè)備往往曝露在自然環(huán)境之中，隨時(shí)可能失去能源供給或者甚至部分喪失性能，在這種情況下，傳統(tǒng)的數(shù)據(jù)采集-壓縮-傳輸-解壓縮的模式就基本上失效了。

壓縮感知的概念就是為了解決這樣的矛盾而產(chǎn)生的。既然采集數(shù)據(jù)之后反正要壓縮掉其中的冗余度，而這個(gè)壓縮過(guò)程又相對(duì)來(lái)說(shuō)比較困難，那么我們?yōu)槭裁床恢苯印覆杉箟嚎s后的數(shù)據(jù)？這樣采集的任務(wù)要輕得多，而且還省去了壓縮的麻煩。這就是所謂的「壓縮感知」，也就是說(shuō)，直接感知壓縮了的信息。

可是這看起來(lái)是不可能的事情。因?yàn)閴嚎s后的數(shù)據(jù)并不是壓縮前的數(shù)據(jù)的一個(gè)子集，并不是說(shuō)，本來(lái)有照相機(jī)的感光器上有一千萬(wàn)個(gè)像素，扔掉其中八百萬(wàn)個(gè)，剩下的兩百萬(wàn)個(gè)采集到的就是壓縮后的圖像，──這樣只能采集到不完整的一小塊圖像，有些信息被永遠(yuǎn)的丟失了而且不可能被恢復(fù)。如果要想采集很少一部分?jǐn)?shù)據(jù)并且指望從這些少量數(shù)據(jù)中「解壓縮」出大量信息，就需要保證：第一：這些少量的采集到的數(shù)據(jù)包含了原信號(hào)的全局信息，第二：存在一種算法能夠從這些少量的數(shù)據(jù)中還原出原先的信息來(lái)。

有趣的是，在某些特定的場(chǎng)合，上述第一件事情是自動(dòng)得到滿足的。最典型的例子就是醫(yī)學(xué)圖像成像，例如斷層掃描（CT）技術(shù)和核磁共振（MRI）技術(shù)。對(duì)這兩種技術(shù)稍有了解的人都知道，這兩種成像技術(shù)中，儀器所采集到的都不是直接的圖像像素，而是圖像經(jīng)歷過(guò)全局傅立葉變換后的數(shù)據(jù)。也就是說(shuō)，每一個(gè)單獨(dú)的數(shù)據(jù)都在某種程度上包含了全圖像的信息。在這種情況下，去掉一部分采集到的數(shù)據(jù)并不會(huì)導(dǎo)致一部分圖像信息永久的丟失（它們?nèi)耘f被包含在其它數(shù)據(jù)里）。這正是我們想要的情況。

上述第二件事就要?dú)w功于陶哲軒和坎戴的工作了。他們的工作指出，如果假定信號(hào)（無(wú)論是圖像還是聲音還是其他別的種類的信號(hào)）滿足某種特定的「稀疏性」，那么從這些少量的測(cè)量數(shù)據(jù)中，確實(shí)有可能還原出原始的較大的信號(hào)來(lái)，其中所需要的計(jì)算部分是一個(gè)復(fù)雜的迭代優(yōu)化過(guò)程，即所謂的「L1-最小化」算法。

把上述兩件事情放在一起，我們就能看到這種模式的優(yōu)點(diǎn)所在。它意味著：我們可以在采集數(shù)據(jù)的時(shí)候只簡(jiǎn)單采集一部分?jǐn)?shù)據(jù)（「壓縮感知」），然后把復(fù)雜的部分交給數(shù)據(jù)還原的這一端來(lái)做，正好匹配了我們期望的格局。在醫(yī)學(xué)圖像領(lǐng)域里，這個(gè)方案特別有好處，因?yàn)椴杉瘮?shù)據(jù)的過(guò)程往往是對(duì)病人帶來(lái)很大麻煩甚至身體傷害的過(guò)程。以 X 光斷層掃描為例，眾所周知 X 光輻射會(huì)對(duì)病人造成身體損害，而「壓縮感知」就意味著我們可以用比經(jīng)典方法少得多的輻射劑量來(lái)進(jìn)行數(shù)據(jù)采集，這在醫(yī)學(xué)上的意義是不言而喻的。

這一思路可以擴(kuò)展到很多領(lǐng)域。在大量的實(shí)際問(wèn)題中，我們傾向于盡量少地采集數(shù)據(jù)，或者由于客觀條件所限不得不采集不完整的數(shù)據(jù)。如果這些數(shù)據(jù)和我們所希望重建的信息之間有某種全局性的變換關(guān)系，并且我們預(yù)先知道那些信息滿足某種稀疏性條件，就總可以試著用類似的方式從比較少的數(shù)據(jù)中還原出比較多的信號(hào)來(lái)。到今天為止，這樣的研究已經(jīng)拓展地非常廣泛了。
但是同樣需要說(shuō)明的是，這樣的做法在不同的應(yīng)用領(lǐng)域里并不總能滿足上面所描述的兩個(gè)條件。有的時(shí)候，第一個(gè)條件（也就是說(shuō)測(cè)量到的數(shù)據(jù)包含信號(hào)的全局信息）無(wú)法得到滿足，例如最傳統(tǒng)的攝影問(wèn)題，每個(gè)感光元件所感知到的都只是一小塊圖像而不是什么全局信息，這是由照相機(jī)的物理性質(zhì)決定的。為了解決這個(gè)問(wèn)題，美國(guó) Rice 大學(xué)的一部分科學(xué)家正在試圖開(kāi)發(fā)一種新的攝影裝置（被稱為「單像素照相機(jī)」），爭(zhēng)取用盡量少的感光元件實(shí)現(xiàn)盡量高分辨率的攝影。有的時(shí)候，第二個(gè)條件（也就是說(shuō)有數(shù)學(xué)方法保證能夠從不完整的數(shù)據(jù)中還原出信號(hào)）無(wú)法得到滿足。這種時(shí)候，實(shí)踐就走在了理論前面。人們已經(jīng)可以在算法上事先很多數(shù)據(jù)重建的過(guò)程，但是相應(yīng)的理論分析卻成為了留在數(shù)學(xué)家面前的課題。

但是無(wú)論如何，壓縮感知所代表的基本思路：從盡量少的數(shù)據(jù)中提取盡量多的信息，毫無(wú)疑問(wèn)是一種有著極大理論和應(yīng)用前景的想法。它是傳統(tǒng)信息論的一個(gè)延伸，但是又超越了傳統(tǒng)的壓縮理論，成為了一門(mén)嶄新的子分支。它從誕生之日起到現(xiàn)在不過(guò)五年時(shí)間，其影響卻已經(jīng)席卷了大半個(gè)應(yīng)用科學(xué)。

?

譯者：Armeny ??原文?校對(duì)：擬南芥、剃刀、木遙

擴(kuò)展閱讀：數(shù)字圖像的壓縮與恢復(fù)/奧卡姆剃刀

?

2009年早春，斯坦福大學(xué)露西爾·帕卡德兒童醫(yī)院的一組醫(yī)生把一名兩歲男孩送進(jìn)磁共振成像[f1]?掃描儀。這個(gè)將被我稱為布賴斯的男孩身處巨洞般的金屬儀器中，看上去是那么弱小無(wú)助。他被施以全身麻醉，一根彎彎曲曲的管子從他的咽喉聯(lián)接到掃描儀傍的呼吸機(jī)上。十個(gè)月前， 布賴斯接受了肝臟移植術(shù)，來(lái)自捐獻(xiàn)者的部分肝臟取代了他自己的已壞死的肝臟。他的康復(fù)情況一度不錯(cuò)。但是，最近的實(shí)驗(yàn)室測(cè)試結(jié)果令人擔(dān)憂，他的身體出現(xiàn)了問(wèn)題——可能一條或者全部的兩條膽管被堵住了。

帕卡德醫(yī)院的兒童放射科醫(yī)生施里亞斯·瓦薩納瓦拉需要高精度的掃描結(jié)果來(lái)告訴他問(wèn)題出在哪，但是這將意味著他的小病人在掃描過(guò)程中不得不保持絕對(duì)靜止。哪怕布賴斯只是呼吸了一次，成像結(jié)果都會(huì)變得模糊。要避免上述情況，就需要進(jìn)行足夠深的麻醉讓病人停止呼吸。進(jìn)行一次標(biāo)準(zhǔn)的磁共振成像檢測(cè)需要兩分鐘時(shí)間，但如果麻醉師真的讓布賴斯在這么長(zhǎng)時(shí)間里停止呼吸，那么帶來(lái)的問(wèn)題將遠(yuǎn)遠(yuǎn)超過(guò)他肝臟的小毛病。

不過(guò)，瓦薩納瓦拉和他的電子工程師同事邁克爾·勒斯蒂格打算使用一種快得多的新掃描方法，名曰“壓縮感知”。這種技術(shù)可能是當(dāng)今應(yīng)用數(shù)學(xué)界最熱門(mén)的話題了。未來(lái)，它可能會(huì)改變我們尋找遙遠(yuǎn)星系的方式。而現(xiàn)在，這種技術(shù)使得瓦薩納瓦拉和勒斯蒂格只需要40秒就可以采集到精確重建布賴斯肝臟圖像所需的數(shù)據(jù)。

壓縮感知的發(fā)現(xiàn)純屬偶然。2004年2月，伊曼紐爾·坎迪斯正在自己的電腦上看著Shepp-Logan圖像（譯注：這是醫(yī)學(xué)圖像處理領(lǐng)域用來(lái)進(jìn)行仿真測(cè)試的標(biāo)準(zhǔn)模擬圖像，由一些大大小小的橢圓模擬生物器官）打發(fā)時(shí)間。這幅通常被計(jì)算機(jī)科學(xué)家和工程師用于測(cè)試成像算法的標(biāo)準(zhǔn)圖像，看起來(lái)就像《第三類接觸》里那個(gè)搞笑地將眉毛揚(yáng)起的外星人?？驳纤?，斯坦福大學(xué)教授，曾在加州理工學(xué)院工作過(guò)，打算用一個(gè)嚴(yán)重失真的模型圖像作為磁共振成像儀不能精確掃描而產(chǎn)生的非清晰圖像來(lái)進(jìn)行實(shí)驗(yàn)。他想到一種名為L(zhǎng)1（校對(duì)注：這里雖然原文用的是小寫(xiě)，但是在中文上下文中用小寫(xiě)則極易同11混淆，而數(shù)學(xué)上這里大小寫(xiě)都可以用）范數(shù)極小化的數(shù)學(xué)技術(shù)可能有助于清除小部分斑痕。他按下一個(gè)鍵，算法運(yùn)行起來(lái)了。

坎迪斯希望屏幕上的模型圖像變得稍微清晰一些。但是，他突然發(fā)現(xiàn)用殘缺的數(shù)據(jù)渲染出來(lái)的圖像是那么細(xì)膩完美，對(duì)每個(gè)細(xì)節(jié)而言都是如此，這簡(jiǎn)直就像變魔術(shù)一樣。太不可思議了，他認(rèn)為。“這就好像，你給了我十位銀行賬號(hào)的前三位，然后我能夠猜出接下來(lái)的七位數(shù)字?！彼f(shuō)。他嘗試在不同類型的模型圖像上重新進(jìn)行這個(gè)實(shí)驗(yàn)，結(jié)果都非常好。

在博士后賈斯廷·龍伯格的幫助下，坎迪斯提出了一個(gè)粗略的理論。之后，他在黑板上向加州大學(xué)洛杉磯分校的同事陶哲軒介紹了自己的理論?？驳纤乖诮Y(jié)束討論離開(kāi)的時(shí)候覺(jué)得陶哲軒對(duì)此持懷疑態(tài)度，畢竟，圖像清晰度的提高也太離譜了。然而，第二天晚上，陶哲軒給坎迪斯送去關(guān)于他們之前討論的問(wèn)題的一疊筆記。這疊筆記為他們共同發(fā)表的第一篇論文奠定了基礎(chǔ)。在隨后的兩年中，他們寫(xiě)了更多文章。

上面介紹的是壓縮感知技術(shù)的開(kāi)端，這個(gè)數(shù)學(xué)界的全新領(lǐng)域改變了人們處理大規(guī)模數(shù)據(jù)集的方式。僅僅六年時(shí)光，它為上千篇論文提供了靈感，吸引了數(shù)百萬(wàn)美元的聯(lián)邦基金。2006年，坎迪斯在這一領(lǐng)域內(nèi)的工作為他贏得了獎(jiǎng)金值50萬(wàn)美元的沃特曼獎(jiǎng)，這是美國(guó)國(guó)家科學(xué)基金授予研究者的最高榮譽(yù)。其原因是顯而易見(jiàn)的。想象一下，磁共振成像儀可以在幾秒鐘的時(shí)間里生成原本需要花費(fèi)一個(gè)小時(shí)才能生成的圖像；軍用軟件截獲敵方通信的能力得到極大加強(qiáng)；傳感器能夠解析遙遠(yuǎn)星際的無(wú)線電波。突然之間，數(shù)據(jù)的采集、操作以及解析都變得容易了。

壓縮感知的原理是這樣的：你有一張圖片，假設(shè)是總統(tǒng)的腎臟圖片，這不是關(guān)鍵。圖片由一百萬(wàn)個(gè)像素構(gòu)成。對(duì)傳統(tǒng)成像來(lái)說(shuō)，你不得不進(jìn)行一百萬(wàn)次量度。而采用壓縮感知技術(shù)，你只需要量度一小部分，好比說(shuō)從圖像的不同部分隨機(jī)抽取十萬(wàn)個(gè)像素。從這里開(kāi)始，有大量的實(shí)際上是無(wú)窮多的方式填充那剩余的九十萬(wàn)個(gè)像素點(diǎn)。

尋找那個(gè)唯一正確的表示方式的關(guān)鍵在于一種叫稀疏度的概念。所謂稀疏度，是描述圖像的復(fù)雜性或者其中所缺的一種數(shù)學(xué)方法。一幅由少數(shù)幾個(gè)簡(jiǎn)單、可理解的元素（例如色塊或者波浪線構(gòu)成的圖片）是稀疏的；滿屏隨機(jī)、散亂的點(diǎn)陣則不是稀疏的。原來(lái)在無(wú)限多的可能性中，最簡(jiǎn)單、最稀疏的那幅圖像往往就是正解，至少很接近正解。

但是，怎樣進(jìn)行數(shù)字運(yùn)算，才能快速獲得最稀疏的圖像呢？分析所有可能的情況太費(fèi)時(shí)間。然而，坎迪斯和陶哲軒知道最稀疏的圖像是用最少的成分構(gòu)成的，并且，他們可以用L1范數(shù)極小化技術(shù)迅速找到它。

這樣，在輸入不完整的圖像后，算法開(kāi)始試著用大色塊來(lái)填充空白區(qū)。如果有一團(tuán)綠色的像素點(diǎn)聚集在一起，算法可能會(huì)用一個(gè)大的綠色矩形填充它們之間的空間;而如果是一團(tuán)黃色的像素點(diǎn)，那么就用黃色的矩形來(lái)填充。在不同顏色交錯(cuò)散布的區(qū)域，算法會(huì)使用越來(lái)越小的矩形或其他形狀填充各種顏色之間的空間。算法會(huì)重復(fù)這樣的過(guò)程，最終，得到一幅由最少的可能的色塊構(gòu)成的圖像，它的一百萬(wàn)像素都已被彩色填滿。

并不能絕對(duì)保證這樣的圖像就是最稀疏的，或者正是你所試圖重建的那個(gè)。但是坎迪斯和陶哲軒已經(jīng)從數(shù)學(xué)上證明了，它的錯(cuò)誤率是無(wú)窮小的。算法運(yùn)行可能還是需要幾個(gè)小時(shí)，但是，讓電腦多跑一個(gè)小時(shí)，總好過(guò)讓孩子在額外的一分鐘里停止呼吸。

壓縮感知已經(jīng)產(chǎn)生了令人驚嘆的科學(xué)影響。這是因?yàn)槊恳粋€(gè)有趣的信號(hào)都是稀疏的，只要你能夠正確定義它的稀疏性。例如，鋼琴和弦的樂(lè)音是一小組不超過(guò)五個(gè)純音符的組合。在所演奏的音頻中，只有少部分頻率包含有效的音樂(lè)信息，而其余大部分頻段是一片無(wú)聲地帶。因此，你可以用壓縮感知技術(shù)從“欠采樣”的老舊唱片中重建出當(dāng)時(shí)的樂(lè)章，而不用擔(dān)心失去了由特定頻率構(gòu)成的聲波的信息。只需要你手頭的材料，就可以用L1范數(shù)極小化法以稀疏方式填補(bǔ)空白，從而獲得與原音一般無(wú)二的旋律。

帶著建筑師式的眼睛，頂著略顯蓬松的頭發(fā)，坎迪斯散發(fā)著時(shí)尚極客的氣息。這個(gè)39歲的法國(guó)人語(yǔ)氣溫和，但是面對(duì)他認(rèn)為不達(dá)標(biāo)的事情絕不妥協(xié)。“不，不，他說(shuō)的沒(méi)有道理?！碑?dāng)我提到壓縮感知領(lǐng)域某個(gè)和他有些觀點(diǎn)有著細(xì)小差別的專家的工作時(shí)，他如是說(shuō)，“不，不，不，不。那沒(méi)有道理，沒(méi)道理，是錯(cuò)的?！?/p>

坎迪斯曾經(jīng)預(yù)見(jiàn)，將來(lái)會(huì)有大量應(yīng)用技術(shù)是以他的研究成果作為理論基礎(chǔ)的。他舉例說(shuō)道，在未來(lái)，這項(xiàng)技術(shù)不會(huì)僅僅用在磁共振成像儀上。例如，數(shù)碼相機(jī)收集了大量信息，然后壓縮圖像。但是，至少在壓縮感知技術(shù)可用的情況下，壓縮是一種極大的浪費(fèi)。如果你的相機(jī)記錄了大量的數(shù)據(jù)，卻在壓縮時(shí)丟棄了其中的90%，那么為什么不在一開(kāi)始就只記錄10%的數(shù)據(jù)從而節(jié)省電池電量和內(nèi)存？對(duì)于您的孩子的數(shù)碼快照，費(fèi)電可能沒(méi)什么大不了，你只要插上電源為相機(jī)充電就可以了。“但是，當(dāng)廢電池多到可以環(huán)繞木星，”坎迪斯說(shuō)，“結(jié)果就不是那么簡(jiǎn)單了”。同樣，如果你希望自己的相機(jī)能夠拍攝萬(wàn)億像素的照片而不是幾百萬(wàn)像素，你就必須使用壓縮感知技術(shù)。

從信息的小樣本中收集有用數(shù)據(jù)的能力也引起了軍方的重視：比如，敵方通信可能從一個(gè)頻率跳到另一個(gè)頻率。但是，還沒(méi)有一種硬件設(shè)備能以足夠快的速度掃描整個(gè)頻域。但是無(wú)論在什么情況下，對(duì)手的信號(hào)都是稀疏的，是由頻段內(nèi)極少數(shù)的某種簡(jiǎn)單信號(hào)構(gòu)成的，出現(xiàn)在一些相對(duì)較小卻未知的頻段。這意味著壓縮感知可以用來(lái)從“噼啵”聲中區(qū)分來(lái)自任意波段的敵人的交談。所以不出意外的，美國(guó)國(guó)防部先進(jìn)計(jì)劃研究署正在支持壓縮感知技術(shù)的研究。

壓縮感知不僅可以用于解決現(xiàn)在的技術(shù)難題。將來(lái)，它還將幫助我們處理已存儲(chǔ)的大量信息。每天，全世界都要產(chǎn)生數(shù)不清的數(shù)據(jù)，我們希望這些數(shù)據(jù)安全、有效、可恢復(fù)地保存起來(lái)。目前，我們大部分的視聽(tīng)信息都是用復(fù)雜的壓縮格式存儲(chǔ)起來(lái)的。如果有一天，這種格式被淘汰了，你不得不進(jìn)行痛苦的格式轉(zhuǎn)換。但是坎迪斯相信，在擁有壓縮感知技術(shù)的未來(lái)，對(duì)于采用高成本紅外技術(shù)拍攝的天文圖像，只需要拍攝到20％的像素就可以了。因?yàn)槲覀円婚_(kāi)始就只記錄了極少部分的數(shù)據(jù)，所以不需要再進(jìn)行壓縮。那么我們只需要逐步改進(jìn)數(shù)據(jù)的解析算法，而不是數(shù)據(jù)的壓縮算法，就可以精確地恢復(fù)出原始圖像了。

上面說(shuō)的都是將來(lái)的事情。今天，壓縮感知技術(shù)已經(jīng)改寫(xiě)了我們獲取醫(yī)學(xué)信息的方式。在GE醫(yī)療集團(tuán)的參與下，威斯康辛大學(xué)的一個(gè)研究小組正在把壓縮感知技術(shù)與HYPR和VIPR技術(shù)結(jié)合，以提高特定種類磁共振掃描的速度，在某種情況下可以達(dá)到原來(lái)的幾千倍。（我是這所大學(xué)的教員，但是沒(méi)有參與這項(xiàng)研究。）GE醫(yī)療集團(tuán)還在實(shí)驗(yàn)一種新的方法，有希望利用壓縮感知技術(shù)大大改善對(duì)癌癥病人代謝動(dòng)力學(xué)的觀測(cè)。同時(shí)，帕卡德醫(yī)院應(yīng)用了壓縮感知技術(shù)，使磁共振成像儀的圖像記錄速度提升為傳統(tǒng)掃描儀的三倍。

這對(duì)于兩歲的布賴斯來(lái)說(shuō)恰好夠用。瓦薩納瓦拉在控制室發(fā)出工作信號(hào)，麻醉師給男孩注射了一點(diǎn)鎮(zhèn)靜劑，然后關(guān)掉了呼吸機(jī)。男孩的呼吸立刻停止了。瓦薩納瓦拉開(kāi)始掃描，而麻醉師監(jiān)視著布賴斯的心率和血氧水平。40秒鐘之后，掃描結(jié)束，布賴斯沒(méi)有出現(xiàn)明顯的缺氧情況。當(dāng)天晚些時(shí)候，壓縮感知算法從粗略的掃描中生成了清晰的圖像，能讓瓦薩納瓦拉看清雙側(cè)膽管的堵塞情況。一名介入放射科醫(yī)生將一根彎曲的導(dǎo)線依次插入雙側(cè)膽管中，輕輕清除淤塞，并為男孩安裝了讓膽汁恰當(dāng)流出的細(xì)小導(dǎo)管。正是數(shù)學(xué)與醫(yī)學(xué)的結(jié)合，才使得布賴斯的檢測(cè)結(jié)果又恢復(fù)了正常。

原文作者：

Jordan Ellenberg (ellenber@math.wisc.edu),?是威斯康辛大學(xué)的數(shù)學(xué)副教授。原文發(fā)表在《連線》雜志三月號(hào)上。
數(shù)學(xué)怎樣得出那些顆粒：壓縮感知技術(shù)是一種從低分辨率樣本中重建高精度數(shù)據(jù)的數(shù)學(xué)工具。它可以用來(lái)重現(xiàn)古老的音樂(lè)錄音、尋找敵人的無(wú)線電信號(hào)，并更加迅速地完成磁共振成像。這里展示的是它如何處理照片。