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

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

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

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

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

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

一、壓縮感知與單像素相機

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由于壓縮傳感還是一個相當(dāng)新的領(lǐng)域（尤其是嚴密的數(shù)學(xué)結(jié)果剛剛出現(xiàn)），現(xiàn)在就期望這個技術(shù)應(yīng)用到實用的傳感器上還為時尚早。不過已經(jīng)有概念驗證模型出現(xiàn)了，其中最著名的是Rice大學(xué)研制的單像素相機。

最后必須提到的是，壓縮傳感技術(shù)是一種抽象的數(shù)學(xué)概念，而不是具體的操作方案，它可以應(yīng)用到成像以外的許多領(lǐng)域。以下只是其中幾個例子：

? 磁共振成像(MRI)。在醫(yī)學(xué)上，磁共振的工作原理是做許多次（但次數(shù)仍是有限的）測量（基本上就是對人體圖像進行離散拉東變換（也叫X光變換）），再對數(shù)據(jù)進行加工來生成圖像（在這里就是人體內(nèi)水的密度分布圖像）。由于測量次數(shù)必須很多，整個過程對患者來說太過漫長。壓縮傳感技術(shù)可以顯著減少測量次數(shù)，加快成像（甚至有可能做到實時成像，也就是核磁共振的視頻而非靜態(tài)圖像）。此外我們還可以以測量次數(shù)換圖像質(zhì)量，用與原來一樣的測量次數(shù)可以得到好得多的圖像分辨率。

? 天文學(xué)。許多天文現(xiàn)象（如脈沖星）具有多種頻率震蕩特性，使其在頻域上是高度稀疏也就是可壓縮的。壓縮傳感技術(shù)將使我們能夠在時域內(nèi)測量這些現(xiàn)象（即記錄望遠鏡數(shù)據(jù)）并能夠精確重建原始信號，即使原始數(shù)據(jù)不完整或者干擾嚴重（原因可能是天氣不佳，上機時間不夠，或者就是因為地球自傳使我們得不到全時序的數(shù)據(jù)）。

? 線性編碼。壓縮傳感技術(shù)提供了一個簡單的方法，讓多個傳送者可以將其信號帶糾錯地合并傳送，這樣即使輸出信號的一大部分丟失或毀壞，仍然可以恢復(fù)出原始信號。例如，可以用任意一種線性編碼把1000比特信息編碼進一個3000比特的流；那么，即使其中300位被（惡意）毀壞，原始信息也能完全無損失地完美重建。這是因為壓縮傳感技術(shù)可以把破壞動作本身看作一個稀疏的信號（只集中在3000比特中的300位）。

許多這種應(yīng)用都還只停留在理論階段，可是這種算法能夠影響測量和信號處理中如此之多的領(lǐng)域，其潛力實在是振奮人心。筆者自己最有成就感的就是能看到自己在純數(shù)學(xué)領(lǐng)域的工作（例如估算傅立葉子式的行列式或單數(shù)值）最終具備造?，F(xiàn)實世界的前景。

?

二、填補空缺——壓縮感知

紅豬按（by?木遙）

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

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

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

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

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

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

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

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

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

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

?

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

原文作者：

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