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