壓縮感知從字面上看起來，好像是數(shù)據(jù)壓縮的意思，而實(shí)則出于完全不同的考慮。經(jīng)典的數(shù)據(jù)壓縮技術(shù)，無論是音頻壓縮（例如 mp3），圖像壓縮（例如 jpeg），視頻壓縮（mpeg），還是一般的編碼壓縮（zip），都是從數(shù)據(jù)本身的特性出發(fā)，尋找并剔除數(shù)據(jù)中隱含的冗余度，從而達(dá)到壓縮的目的。這樣的壓縮有兩個特點(diǎn)：第一、它是發(fā)生在數(shù)據(jù)已經(jīng)被完整采集到之后；第二、它本身需要復(fù)雜的算法來完成。相較而言，解碼過程反而一般來說在計算上比較簡單，以音頻壓縮為例，壓制一個 mp3 文件的計算量遠(yuǎn)大于播放（即解壓縮）一個 mp3 文件的計算量。
稍加思量就會發(fā)現(xiàn)，這種壓縮和解壓縮的不對稱性正好同人們的需求是相反的。在大多數(shù)情況下，采集并處理數(shù)據(jù)的設(shè)備，往往是廉價、省電、計算能力較低的便攜設(shè)備，例如傻瓜相機(jī)、或者錄音筆、或者遙控監(jiān)視器等等。而負(fù)責(zé)處理（即解壓縮）信息的過程卻反而往往在大型計算機(jī)上進(jìn)行，它有更高的計算能力，也常常沒有便攜和省電的要求。也就是說，我們是在用廉價節(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ù)的一個子集，并不是說，本來有照相機(jī)的感光器上有一千萬個像素，扔掉其中八百萬個，剩下的兩百萬個采集到的就是壓縮后的圖像，──這樣只能采集到不完整的一小塊圖像，有些信息被永遠(yuǎn)的丟失了而且不可能被恢復(fù)。如果要想采集很少一部分?jǐn)?shù)據(jù)并且指望從這些少量數(shù)據(jù)中「解壓縮」出大量信息，就需要保證：第一：這些少量的采集到的數(shù)據(jù)包含了原信號的全局信息，第二：存在一種算法能夠從這些少量的數(shù)據(jù)中還原出原先的信息來。
有趣的是，在某些特定的場合，上述第一件事情是自動得到滿足的。最典型的例子就是醫(yī)學(xué)圖像成像，例如斷層掃描（CT）技術(shù)和核磁共振（MRI）技術(shù)。對這兩種技術(shù)稍有了解的人都知道，這兩種成像技術(shù)中，儀器所采集到的都不是直接的圖像像素，而是圖像經(jīng)歷過全局傅立葉變換后的數(shù)據(jù)。也就是說，每一個單獨(dú)的數(shù)據(jù)都在某種程度上包含了全圖像的信息。在這種情況下，去掉一部分采集到的數(shù)據(jù)并不會導(dǎo)致一部分圖像信息永久的丟失（它們?nèi)耘f被包含在其它數(shù)據(jù)里）。這正是我們想要的情況。
上述第二件事就要?dú)w功于陶哲軒和坎戴的工作了。他們的工作指出，如果假定信號（無論是圖像還是聲音還是其他別的種類的信號）滿足某種特定的「稀疏性」，那么從這些少量的測量數(shù)據(jù)中，確實(shí)有可能還原出原始的較大的信號來，其中所需要的計算部分是一個復(fù)雜的迭代優(yōu)化過程，即所謂的「L1-最小化」算法。
把上述兩件事情放在一起，我們就能看到這種模式的優(yōu)點(diǎn)所在。它意味著：我們可以在采集數(shù)據(jù)的時候只簡單采集一部分?jǐn)?shù)據(jù)（「壓縮感知」），然后把復(fù)雜的部分交給數(shù)據(jù)還原的這一端來做，正好匹配了我們期望的格局。在醫(yī)學(xué)圖像領(lǐng)域里，這個方案特別有好處，因為采集數(shù)據(jù)的過程往往是對病人帶來很大麻煩甚至身體傷害的過程。以 X 光斷層掃描為例，眾所周知 X 光輻射會對病人造成身體損害，而「壓縮感知」就意味著我們可以用比經(jīng)典方法少得多的輻射劑量來進(jìn)行數(shù)據(jù)采集，這在醫(yī)學(xué)上的意義是不言而喻的。
這一思路可以擴(kuò)展到很多領(lǐng)域。在大量的實(shí)際問題中，我們傾向于盡量少地采集數(shù)據(jù)，或者由于客觀條件所限不得不采集不完整的數(shù)據(jù)。如果這些數(shù)據(jù)和我們所希望重建的信息之間有某種全局性的變換關(guān)系，并且我們預(yù)先知道那些信息滿足某種稀疏性條件，就總可以試著用類似的方式從比較少的數(shù)據(jù)中還原出比較多的信號來。到今天為止，這樣的研究已經(jīng)拓展地非常廣泛了。
但是同樣需要說明的是，這樣的做法在不同的應(yīng)用領(lǐng)域里并不總能滿足上面所描述的兩個條件。有的時候，第一個條件（也就是說測量到的數(shù)據(jù)包含信號的全局信息）無法得到滿足，例如最傳統(tǒng)的攝影問題，每個感光元件所感知到的都只是一小塊圖像而不是什么全局信息，這是由照相機(jī)的物理性質(zhì)決定的。為了解決這個問題，美國 Rice 大學(xué)的一部分科學(xué)家正在試圖開發(fā)一種新的攝影裝置（被稱為「單像素照相機(jī)」），爭取用盡量少的感光元件實(shí)現(xiàn)盡量高分辨率的攝影。有的時候，第二個條件（也就是說有數(shù)學(xué)方法保證能夠從不完整的數(shù)據(jù)中還原出信號）無法得到滿足。這種時候，實(shí)踐就走在了理論前面。人們已經(jīng)可以在算法上事先很多數(shù)據(jù)重建的過程，但是相應(yīng)的理論分析卻成為了留在數(shù)學(xué)家面前的課題。
但是無論如何，壓縮感知所代表的基本思路：從盡量少的數(shù)據(jù)中提取盡量多的信息，毫無疑問是一種有著極大理論和應(yīng)用前景的想法。它是傳統(tǒng)信息論的一個延伸，但是又超越了傳統(tǒng)的壓縮理論，成為了一門嶄新的子分支。它從誕生之日起到現(xiàn)在不過五年時間，其影響卻已經(jīng)席卷了大半個應(yīng)用科學(xué)。
譯者：Armeny 原文 校對：擬南芥、剃刀、木遙
擴(kuò)展閱讀：數(shù)字圖像的壓縮與恢復(fù)/奧卡姆剃刀
2009年早春，斯坦福大學(xué)露西爾·帕卡德兒童醫(yī)院的一組醫(yī)生把一名兩歲男孩送進(jìn)磁共振成像[f1] 掃描儀。這個將被我稱為布賴斯的男孩身處巨洞般的金屬儀器中，看上去是那么弱小無助。他被施以全身麻醉，一根彎彎曲曲的管子從他的咽喉聯(lián)接到掃描儀傍的呼吸機(jī)上。十個月前， 布賴斯接受了肝臟移植術(shù)，來自捐獻(xiàn)者的部分肝臟取代了他自己的已壞死的肝臟。他的康復(fù)情況一度不錯。但是，最近的實(shí)驗室測試結(jié)果令人擔(dān)憂，他的身體出現(xiàn)了問題——可能一條或者全部的兩條膽管被堵住了。
帕卡德醫(yī)院的兒童放射科醫(yī)生施里亞斯（校對者注：這個first name有多種翻譯方法，請編輯注意）·瓦薩納瓦拉需要高精度的掃描結(jié)果來告訴他問題出在哪，但是這將意味著他的小病人在掃描過程中不得不保持絕對靜止。哪怕布賴斯只是呼吸了一次，成像結(jié)果都會變得模糊。要避免上述情況，就需要進(jìn)行足夠深的麻醉讓病人停止呼吸。進(jìn)行一次標(biāo)準(zhǔn)的磁共振成像檢測需要兩分鐘時間，但如果麻醉師真的讓布賴斯在這么長時間里停止呼吸，那么帶來的問題將遠(yuǎn)遠(yuǎn)超過他肝臟的小毛病。
不過，瓦薩納瓦拉和他的電子工程師同事邁克爾·勒斯蒂格打算使用一種快得多的新掃描方法，名曰“壓縮感知”。這種技術(shù)可能是當(dāng)今應(yīng)用數(shù)學(xué)界最熱門的話題了。未來，它可能會改變我們尋找遙遠(yuǎn)星系的方式。而現(xiàn)在，這種技術(shù)使得瓦薩納瓦拉和勒斯蒂格只需要40秒就可以采集到精確重建布賴斯肝臟圖像所需的數(shù)據(jù)。
壓縮感知的發(fā)現(xiàn)純屬偶然。2004年2月，伊曼紐爾·坎迪斯正在自己的電腦上看著Shepp-Logan圖像（譯注：這是醫(yī)學(xué)圖像處理領(lǐng)域用來進(jìn)行仿真測試的標(biāo)準(zhǔn)模擬圖像，由一些大大小小的橢圓模擬生物器官）打發(fā)時間。這幅通常被計算機(jī)科學(xué)家和工程師用于測試成像算法的標(biāo)準(zhǔn)圖像，看起來就像《第三類接觸》里那個搞笑地將眉毛揚(yáng)起的外星人?？驳纤?，斯坦福大學(xué)教授，曾在加州理工學(xué)院工作過，打算用一個嚴(yán)重失真的模型圖像作為磁共振成像儀不能精確掃描而產(chǎn)生的非清晰圖像來進(jìn)行實(shí)驗。他想到一種名為L1（校對注：這里雖然原文用的是小寫，但是在中文上下文中用小寫則極易同11混淆，而數(shù)學(xué)上這里大小寫都可以用）范數(shù)極小化的數(shù)學(xué)技術(shù)可能有助于清除小部分斑痕。他按下一個鍵，算法運(yùn)行起來了。
坎迪斯希望屏幕上的模型圖像變得稍微清晰一些。但是，他突然發(fā)現(xiàn)用殘缺的數(shù)據(jù)渲染出來的圖像是那么細(xì)膩完美，對每個細(xì)節(jié)而言都是如此，這簡直就像變魔術(shù)一樣。太不可思議了，他認(rèn)為。“這就好像，你給了我十位銀行賬號的前三位，然后我能夠猜出接下來的七位數(shù)字。”他說。他嘗試在不同類型的模型圖像上重新進(jìn)行這個實(shí)驗，結(jié)果都非常好。
在博士后賈斯廷·龍伯格的幫助下，坎迪斯提出了一個粗略的理論。之后，他在黑板上向加州大學(xué)洛杉磯分校的同事陶哲軒介紹了自己的理論?？驳纤乖诮Y(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é)基金授予研究者的最高榮譽(yù)。其原因是顯而易見的。想象一下，磁共振成像儀可以在幾秒鐘的時間里生成原本需要花費(fèi)一個小時才能生成的圖像；軍用軟件截獲敵方通信的能力得到極大加強(qiáng)；傳感器能夠解析遙遠(yuǎn)星際的無線電波。突然之間，數(shù)據(jù)的采集、操作以及解析都變得容易了。
壓縮感知的原理是這樣的：你有一張圖片，假設(shè)是總統(tǒng)的腎臟圖片，這不是關(guān)鍵。圖片由一百萬個像素構(gòu)成。對傳統(tǒng)成像來說，你不得不進(jìn)行一百萬次量度。而采用壓縮感知技術(shù)，你只需要量度一小部分，好比說從圖像的不同部分隨機(jī)抽取十萬個像素。從這里開始，有大量的實(shí)際上是無窮多的方式填充那剩余的九十萬個像素點(diǎn)。
尋找那個唯一正確的表示方式的關(guān)鍵在于一種叫稀疏度的概念。所謂稀疏度，是描述圖像的復(fù)雜性或者其中所缺的一種數(shù)學(xué)方法。一幅由少數(shù)幾個簡單、可理解的元素（例如色塊或者波浪線構(gòu)成的圖片）是稀疏的；滿屏隨機(jī)、散亂的點(diǎn)陣則不是稀疏的。原來在無限多的可能性中，最簡單、最稀疏的那幅圖像往往就是正解，至少很接近正解。
但是，怎樣進(jìn)行數(shù)字運(yùn)算，才能快速獲得最稀疏的圖像呢？分析所有可能的情況太費(fèi)時間。然而，坎迪斯和陶哲軒知道最稀疏的圖像是用最少的成分構(gòu)成的，并且，他們可以用L1范數(shù)極小化技術(shù)迅速找到它。
這樣，在輸入不完整的圖像后，算法開始試著用大色塊來填充空白區(qū)。如果有一團(tuán)綠色的像素點(diǎn)聚集在一起，算法可能會用一個大的綠色矩形填充它們之間的空間;而如果是一團(tuán)黃色的像素點(diǎn)，那么就用黃色的矩形來填充。在不同顏色交錯散布的區(qū)域，算法會使用越來越小的矩形或其他形狀填充各種顏色之間的空間。算法會重復(fù)這樣的過程，最終，得到一幅由最少的可能的色塊構(gòu)成的圖像，它的一百萬像素都已被彩色填滿。
并不能絕對保證這樣的圖像就是最稀疏的，或者正是你所試圖重建的那個。但是坎迪斯和陶哲軒已經(jīng)從數(shù)學(xué)上證明了，它的錯誤率是無窮小的。算法運(yùn)行可能還是需要幾個小時，但是，讓電腦多跑一個小時，總好過讓孩子在額外的一分鐘里停止呼吸。
壓縮感知已經(jīng)產(chǎn)生了令人驚嘆的科學(xué)影響。這是因為每一個有趣的信號都是稀疏的，只要你能夠正確定義它的稀疏性。例如，鋼琴和弦的樂音是一小組不超過五個純音符的組合。在所演奏的音頻中，只有少部分頻率包含有效的音樂信息，而其余大部分頻段是一片無聲地帶。因此，你可以用壓縮感知技術(shù)從“欠采樣”的老舊唱片中重建出當(dāng)時的樂章，而不用擔(dān)心失去了由特定頻率構(gòu)成的聲波的信息。只需要你手頭的材料，就可以用L1范數(shù)極小化法以稀疏方式填補(bǔ)空白，從而獲得與原音一般無二的旋律。
帶著建筑師式的眼睛，頂著略顯蓬松的頭發(fā)，坎迪斯散發(fā)著時尚極客的氣息。這個39歲的法國人語氣溫和，但是面對他認(rèn)為不達(dá)標(biāo)的事情絕不妥協(xié)。“不，不，他說的沒有道理。”當(dāng)我提到壓縮感知領(lǐng)域某個和他有些觀點(diǎn)有著細(xì)小差別的專家的工作時，他如是說，“不，不，不，不。那沒有道理，沒道理，是錯的。”
坎迪斯曾經(jīng)預(yù)見，將來會有大量應(yīng)用技術(shù)是以他的研究成果作為理論基礎(chǔ)的。他舉例說道，在未來，這項技術(shù)不會僅僅用在磁共振成像儀上。例如，數(shù)碼相機(jī)收集了大量信息，然后壓縮圖像。但是，至少在壓縮感知技術(shù)可用的情況下，壓縮是一種極大的浪費(fèi)。如果你的相機(jī)記錄了大量的數(shù)據(jù)，卻在壓縮時丟棄了其中的90%，那么為什么不在一開始就只記錄10%的數(shù)據(jù)從而節(jié)省電池電量和內(nèi)存？對于您的孩子的數(shù)碼快照，費(fèi)電可能沒什么大不了，你只要插上電源為相機(jī)充電就可以了。“但是，當(dāng)廢電池多到可以環(huán)繞木星，”坎迪斯說，“結(jié)果就不是那么簡單了”。同樣，如果你希望自己的相機(jī)能夠拍攝萬億像素的照片而不是幾百萬像素，你就必須使用壓縮感知技術(shù)。
從信息的小樣本中收集有用數(shù)據(jù)的能力也引起了軍方的重視：比如，敵方通信可能從一個頻率跳到另一個頻率。但是，還沒有一種硬件設(shè)備能以足夠快的速度掃描整個頻域。但是無論在什么情況下，對手的信號都是稀疏的，是由頻段內(nèi)極少數(shù)的某種簡單信號構(gòu)成的，出現(xiàn)在一些相對較小卻未知的頻段。這意味著壓縮感知可以用來從“噼啵”聲中區(qū)分來自任意波段的敵人的交談。所以不出意外的，美國國防部先進(jìn)計劃研究署正在支持壓縮感知技術(shù)的研究。
壓縮感知不僅可以用于解決現(xiàn)在的技術(shù)難題。將來，它還將幫助我們處理已存儲的大量信息。每天，全世界都要產(chǎn)生數(shù)不清的數(shù)據(jù)，我們希望這些數(shù)據(jù)安全、有效、可恢復(fù)地保存起來。目前，我們大部分的視聽信息都是用復(fù)雜的壓縮格式存儲起來的。如果有一天，這種格式被淘汰了，你不得不進(jìn)行痛苦的格式轉(zhuǎn)換。但是坎迪斯相信，在擁有壓縮感知技術(shù)的未來，對于采用高成本紅外技術(shù)拍攝的天文圖像，只需要拍攝到20％的像素就可以了。因為我們一開始就只記錄了極少部分的數(shù)據(jù)，所以不需要再進(jìn)行壓縮。那么我們只需要逐步改進(jìn)數(shù)據(jù)的解析算法，而不是數(shù)據(jù)的壓縮算法，就可以精確地恢復(fù)出原始圖像了。
上面說的都是將來的事情。今天，壓縮感知技術(shù)已經(jīng)改寫了我們獲取醫(yī)學(xué)信息的方式。在GE醫(yī)療集團(tuán)的參與下，威斯康辛大學(xué)的一個研究小組正在把壓縮感知技術(shù)與HYPR和VIPR技術(shù)結(jié)合，以提高特定種類磁共振掃描的速度，在某種情況下可以達(dá)到原來的幾千倍。（我是這所大學(xué)的教員，但是沒有參與這項研究。）GE醫(yī)療集團(tuán)還在實(shí)驗一種新的方法，有希望利用壓縮感知技術(shù)大大改善對癌癥病人代謝動力學(xué)的觀測。同時，帕卡德醫(yī)院應(yīng)用了壓縮感知技術(shù)，使磁共振成像儀的圖像記錄速度提升為傳統(tǒng)掃描儀的三倍。
這對于兩歲的布賴斯來說恰好夠用。瓦薩納瓦拉在控制室發(fā)出工作信號，麻醉師給男孩注射了一點(diǎn)鎮(zhèn)靜劑，然后關(guān)掉了呼吸機(jī)。男孩的呼吸立刻停止了。瓦薩納瓦拉開始掃描，而麻醉師監(jiān)視著布賴斯的心率和血氧水平。40秒鐘之后，掃描結(jié)束，布賴斯沒有出現(xiàn)明顯的缺氧情況。當(dāng)天晚些時候，壓縮感知算法從粗略的掃描中生成了清晰的圖像，能讓瓦薩納瓦拉看清雙側(cè)膽管的堵塞情況。一名介入放射科醫(yī)生將一根彎曲的導(dǎo)線依次插入雙側(cè)膽管中，輕輕清除淤塞，并為男孩安裝了讓膽汁恰當(dāng)流出的細(xì)小導(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)古老的音樂錄音、尋找敵人的無線電信號，并更加迅速地完成磁共振成像。這里展示的是它如何處理照片。
[f1]堅持用‘磁共振’的原因：1）MRI直譯就是磁共振成像；2）現(xiàn)代人談‘核’色變，而傳統(tǒng)‘核磁共振’中的‘核’其實(shí)指的是原子核。因為‘核磁共振’這個名字讓我們在招募fMRI實(shí)驗被試時困難重重……趕明兒打算寫個磁共振成像原理給大家做科普，希望以后招被試容易些……