壓縮感覺科普文兩則：
原文連結：http://www.cvchina.info/2010/06/08/compressed-sensing-2/
這幾天由于happyharry的辛勤勞動，大夥紛紛表示對稀疏表達，壓縮感覺很感興趣啊。我是搞不太懂這個前沿啊，隻好轉兩篇科學松鼠會的科普文，都是譯文，說不定大夥都看過了原文。
第一篇是陶哲軒寫的。
這是數學家陶哲軒在他自己的blog上寫的一篇科普文章，讨論的是近年來在應用數學領域裡最熱門的話題之一：壓縮感覺（compressed
sensing）。所謂壓縮感覺，最核心的概念在于試圖從原理上降低對一個信号進行測量的成本。比如說，一個信号包含一千個資料，那麼按照傳統的信号處理理論，至少需要做一千次測量才能完整的複原這個信号。這就相當于是說，需要有一千個方程才能精确地解出一千個未知數來。但是壓縮感覺的想法是假定信号具有某種特點（比如文中所描述得在小波域上系數稀疏的特點），那麼就可以隻做三百次測量就完整地複原這個信号（這就相當于隻通過三百個方程解出一千個未知數）。可想而知，這件事情包含了許多重要的數學理論和廣泛的應用前景，是以在最近三四年裡吸引了大量注意力，得到了非常蓬勃的發展。陶哲軒本身是這個領域的創始者之一（可以參考《陶哲軒：長大的神童》一文），是以這篇文章的權威性毋庸諱言。另外，這也是比較少見的由一流數學家直接撰寫的關于自己前沿工作的普及性文章。需要說明的是，這篇文章是雖然是寫給非數學專業的讀者，但是也并不好懂，也許具有一些理工科背景會更容易了解一些。
【作者 Terence Tao；譯者 山寨盲流，他的更多譯作在這，那；校對 木遙】
最近有不少人問我究竟”壓縮感覺”是什麼意思（特别是随着最近這個概念名聲大噪），所謂“單像素相機”又是怎樣工作的（又怎麼能在某些場合比傳統相機有優勢呢）。這個課題已經有了大量文獻，不過對于這麼一個相對比較新的領域，還沒有一篇優秀的非技術性介紹。是以筆者在此小做嘗試，希望能夠對非數學專業的讀者有所幫助。
具體而言我将主要讨論攝像應用，盡管壓縮傳感作為測量技術應用于比成像廣泛得多的領域（例如天文學，核磁共振，統計選取，等等），我将在文章結尾簡單談談這些領域。
相機的用途，自然是記錄圖像。為了簡化論述，我們把圖像假設成一個長方形陣列，比如說一個1024×2048像素的陣列（這樣就總共是二百萬像素）。為了省略彩色的問題（這個比較次要），我們就假設隻需要黑白圖像，那麼每個像素就可以用一個整型的灰階值來計量其亮度（例如用八位整型數表示0到255，16位表示0到65535）。
接下來，按照最最簡化的說法，傳統相機會測量每一個像素的亮度（在上述例子中就是二百萬個測量值），結果得到的圖檔檔案就比較大（用8位灰階值就是2MB，16位灰階就是4MB）。數學上就認為這個檔案是用超高維矢量值描繪的（在本例中就是約二百萬維）。
在我開始講“壓縮感覺”這個新故事之前，必須先快速回顧一下“老式壓縮”的舊故事。（已經了解圖像壓縮算法的讀者可以跳過這幾段。）
上述的圖檔會占掉相機的很多存儲空間（上傳到計算機裡還占磁盤空間），在各種媒體之間傳輸的時候也要浪費時間。于是，相機帶有顯著壓縮圖像的功能就順理成章了（通常能從2MB那麼大壓縮到十分之一——200KB的一小坨）。關鍵是盡管“所有圖檔”所構成的空間要占用2MB的“自由度”或者說“熵”，由“有意義的圖檔”所構成的空間其實要小得多，尤其是如果人們願意降低一點圖像品質的話。（實際上，如果一個人真的利用所有的自由度随機生成一幅圖檔，他不大可能得到什麼有意義的圖像，而是得到相當于電視熒屏上的靜電雪花那樣的随機噪聲之類。）
怎麼樣壓縮圖像？方式多種多樣，其中有些非常先進，不過我來試試用一種不太高科技的（而且也不太精确的）說法來描述一下這些先進技術。圖像通常都含有大片無細節部分–比如在風景照裡面，将近一半的畫面都可能被單色的天空背景占據。我們假設提取一個大方塊，比方說100×100像素，其中完全是同一顔色的——假設是全白的吧。無壓縮時，這個方塊要占10000位元組存儲空間（按照8位灰階算）；但是我們可以隻記錄這個方塊的次元和坐标，還有填充整個方塊的單一顔色；這樣總共也隻要記錄四五個位元組，省下了可觀的空間。不過在現實中，壓縮效果沒有這麼好，因為表面看來沒有細節的地方其實是有着細微的色差的。是以，給定一個無細節方塊，我們記錄其平均色值，就把圖檔中這一塊區域抽象成了單色色塊，隻留下微小的殘餘誤差。接下來就可以繼續選取更多色彩可見的方塊，抽象成單色色塊。最後剩下的是亮度（色彩強度）很小的，肉眼無法察覺的細節。于是就可以抛棄這些剩餘的細節，隻需要記錄那些“可見”色塊的大小，位置和亮度。日後則可以反向操作，重建出比原始圖像品質稍低一些，占空間卻小得多的複制圖檔。
其實上述的算法并不适合處理顔色劇烈變動的情況，是以在實際應用中不很有效。事實上，更好的辦法不是用均勻色塊，而是用“不均勻”的色塊——比方說右半邊色彩強度平均值大于左半邊這樣的色塊。這種情況可以用（二維）Haar小波系統來描述。後來人們又發現一種”更平滑的”小波系統更能夠避免誤差，不過這都是技術細節，我們就不深入讨論了。然而所有這些系統的原理都是相同的：把原始圖像表示為不同“小波（類似于上文中的色塊）”的線性疊加，記錄顯著的（高強度的）小波的系數，放棄掉（或者用門檻值排除掉）剩下的小波系數。這種“小波系數硬門檻值”壓縮算法沒有實際應用的算法（比如JPEG
2000标準中所定義的）那麼精細，不過多少也能描述壓縮的普遍原理。
總體來講（也是非常簡化的說法），原始的1024×2048圖像可能含有兩百萬自由度，想要用小波來表示這個圖像的人需要兩百萬個不同小波才能完美重建。但是典型的有意義的圖像，從小波理論的角度看來是非常稀疏的，也就是可壓縮的：可能隻需要十萬個小波就已經足夠擷取圖像所有的可見細節了，其餘一百九十萬小波隻貢獻很少量的，大多數觀測者基本看不見的“随機噪聲”。（這也不是永遠适用：含有大量紋理的圖像–比如毛發、毛皮的圖像——用小波算法特别難壓縮，也是圖像壓縮算法的一大挑戰。不過這是另一個故事了。）
接下來呢，如果我們（或者不如說是相機）事先知道兩百萬小波系數裡面哪十萬個是重要的，那就可以隻計量這十萬個系數，别的就不管了。（在圖像上設定一種合适的“過濾器”或叫“濾鏡”，然後計量過濾出來的每個像素的色彩強度，是一種可行的系數計量方法。）但是，相機是不會知道哪個系數是重要的，是以它隻好計量全部兩百萬個像素，把整個圖像轉換成基本小波，找出需要留下的那十萬個主導基本小波，再删掉其餘的。（這當然隻是真正的圖像壓縮算法的一個草圖，不過為了便于讨論我們還是就這麼用吧。）
那麼，如今的數位相機當然已經很強大了，沒什麼問題幹嗎還要改進？事實上，上述的算法，需要收集大量資料，但是隻需要存儲一部分，在消費攝影中是沒有問題的。尤其是随着資料存儲變得很廉價，現在拍一大堆完全不壓縮的照片也無所謂。而且，盡管出了名地耗電，壓縮所需的運算過程仍然算得上輕松。但是，在非消費領域的某些應用中，這種資料收集方式并不可行，特别是在傳感器網絡中。如果打算用上千個傳感器來收集資料，而這些傳感器需要在固定地點呆上幾個月那麼長的時間，那麼就需要盡可能地便宜和節能的傳感器——這首先就排除了那些有強大運算能力的傳感器（然而——這也相當重要——我們在接收處理資料的接收端仍然需要現代科技提供的奢侈的運算能力）。在這類應用中，資料收集方式越“傻瓜”越好（而且這樣的系統也需要很強壯，比如說，能夠忍受10%的傳感器丢失或者各種噪聲和資料缺損）。
這就是壓縮傳感的用武之地了。其理論依據是：如果隻需要10萬個分量就可以重建絕大部分的圖像，那何必還要做所有的200萬次測量，隻做10萬次不就夠了嗎？（在實際應用中，我們會留一個安全餘量，比如說測量30萬像素，以應付可能遭遇的所有問題，從幹擾到量化噪聲，以及恢複算法的故障。）這樣基本上能使節能上一個數量級，這對消費攝影沒什麼意義，對傳感器網絡而言卻有實實在在的好處。
不過，正像我前面說的，相機自己不會預先知道兩百萬小波系數中需要記錄哪十萬個。要是相機選取了另外10萬（或者30萬），反而把圖檔中所有有用的資訊都扔掉了怎麼辦？
解決的辦法簡單但是不太直覺。就是用非小波的算法來做30萬個測量——盡管我前面确實講過小波算法是觀察和壓縮圖像的最佳手段。實際上最好的測量其實應該是（僞）随機測量——比如說随機生成30萬個“濾鏡”圖像并測量真實圖像與每個濾鏡的相關程度。這樣，圖像與濾鏡之間的這些測量結果（也就是“相關性”）很有可能是非常小非常随機的。但是——這是關鍵所在——構成圖像的2百萬種可能的小波函數會在這些随機的濾鏡的測量下生成自己特有的“特征”，它們每一個都會與某一些濾鏡成正相關，與另一些濾鏡成負相關，但是與更多的濾鏡不相關。可是（在極大的機率下）2百萬個特征都各不相同；更有甚者，其中任意十萬個的線性組合仍然是各不相同的（以線性代數的觀點來看，這是因為一個30萬維線性子空間中任意兩個10萬維的子空間極有可能互不相交）。是以，基本上是有可能從這30萬個随機資料中恢複圖像的（至少是恢複圖像中的10萬個主要細節）。簡而言之，我們是在讨論一個哈希函數的線性代數版本。
然而這種方式仍然存在兩個技術問題。首先是噪聲問題：10萬個小波系數的疊加并不能完全代表整幅圖像，另190萬個系數也有少許貢獻。這些小小貢獻有可能會幹擾那10萬個小波的特征，這就是所謂的“失真”問題。第二個問題是如何運用得到的30萬測量資料來重建圖像。
我們先來關注後一個問題。如果我們知道了2百萬小波中哪10萬個是有用的，那就可以使用标準的線性代數方法（高斯消除法，最小二乘法等等）來重建信号。（這正是線性編碼最大的優點之一——它們比非線性編碼更容易求逆。大多數哈希變換實際上是不可能求逆的——這在密碼學上是一大優勢，在信号恢複中卻不是。）可是，就像前面說的那樣，我們事前并不知道哪些小波是有用的。怎麼找出來呢？一個單純的最小二乘近似法會得出牽扯到全部2百萬系數的可怕結果，生成的圖像也含有大量顆粒噪點。要不然也可以代之以一種強力搜尋，為每一組可能的10萬關鍵系數都做一次線性代數處理，不過這樣做的耗時非常恐怖（總共要考慮大約10的17萬次方個組合！），而且這種強力搜尋通常是NP完備的（其中有些特例是所謂的“子集合加總”問題）。不過還好，還是有兩種可行的手段來恢複資料：
• 比對追蹤：找到一個其标記看上去與收集到的資料相關的小波；在資料中去除這個标記的所有印迹；不斷重複直到我們能用小波标記“解釋”收集到的所有資料。
• 基追蹤（又名L1模最小化）：在所有與錄得資料比對的小波組合中，找到一個“最稀疏的”，也就是其中所有系數的絕對值總和越小越好。（這種最小化的結果趨向于迫使絕大多數系數都消失了。）這種最小化算法可以利用單純形法之類的凸規劃算法，在合理的時間内計算出來。
需要注意到的是，這類圖像恢複算法還是需要相當的運算能力的（不過也還不是太變态），不過在傳感器網絡這樣的應用中這不成問題，因為圖像恢複是在接收端（這端有辦法連接配接到強大的計算機）而不是傳感器端（這端就沒辦法了）進行的。
現在已經有嚴密的結果顯示，對原始圖像設定不同的壓縮率或稀疏性，這兩種算法完美或近似完美地重建圖像的成功率都很高。比對追蹤法通常比較快，而基追蹤算法在考慮到噪聲時則顯得比較準确。這些算法确切的适用範圍問題在今天仍然是非常熱門的研究領域。（說來遺憾，目前還沒有出現對P不等于NP問題的應用；如果一個重建問題（在考慮到測量矩陣時）是NP完備的，那它剛好就不能用上述算法解決。）
由于壓縮傳感還是一個相當新的領域（尤其是嚴密的數學結果剛剛出現），現在就期望這個技術應用到實用的傳感器上還為時尚早。不過已經有概念驗證模型出現了，其中最著名的是Rice大學研制的單像素相機。
最後必須提到的是，壓縮傳感技術是一種抽象的數學概念，而不是具體的操作方案，它可以應用到成像以外的許多領域。以下隻是其中幾個例子：
•磁共振成像(MRI)。在醫學上，磁共振的工作原理是做許多次（但次數仍是有限的）測量（基本上就是對人體圖像進行離散拉東變換（也叫X光變換）），再對資料進行加工來生成圖像（在這裡就是人體内水的密度分布圖像）。由于測量次數必須很多，整個過程對患者來說太過漫長。壓縮傳感技術可以顯著減少測量次數，加快成像（甚至有可能做到實時成像，也就是核磁共振的視訊而非靜态圖像）。此外我們還可以以測量次數換圖像品質，用與原來一樣的測量次數可以得到好得多的圖像分辨率。
•天文學。許多天文現象（如脈沖星）具有多種頻率震蕩特性，使其在頻域上是高度稀疏也就是可壓縮的。壓縮傳感技術将使我們能夠在時域内測量這些現象（即記錄望遠鏡資料）并能夠精确重建原始信号，即使原始資料不完整或者幹擾嚴重（原因可能是天氣不佳，上機時間不夠，或者就是因為地球自傳使我們得不到全時序的資料）。
•線性編碼。壓縮傳感技術提供了一個簡單的方法，讓多個傳送者可以将其信号帶糾錯地合并傳送，這樣即使輸出信号的一大部分丢失或毀壞，仍然可以恢複出原始信号。例如，可以用任意一種線性編碼把1000比特資訊編碼進一個3000比特的流；那麼，即使其中300位被（惡意）毀壞，原始資訊也能完全無損失地完美重建。這是因為壓縮傳感技術可以把破壞動作本身看作一個稀疏的信号（隻集中在3000比特中的300位）。
許多這種應用都還隻停留在理論階段，可是這種算法能夠影響測量和信号進行中如此之多的領域，其潛力實在是振奮人心。筆者自己最有成就感的就是能看到自己在純數學領域的工作（例如估算傅立葉子式的行列式或單數值）最終具備造福現實世界的前景。
第二篇
壓縮感覺是近年來極為熱門的研究前沿，在若幹應用領域中都引起矚目。關于這個題目，松鼠會已經翻譯了兩篇文章，一篇來自于壓縮感覺技術最初的研究者陶哲軒（連結），一篇來自威斯康辛大學的數學家艾倫伯格（本文正文）。這兩篇文章都是普及性的，但是由于作者是專業的研究人員，是以事實上行文仍然偏于晦澀。是以我不揣冒昧，在這裡附上一個畫蛇添足的導讀，以幫助更多的讀者更好了解這個新穎的研究領域在理論和實踐上的意義。
壓縮感覺從字面上看起來，好像是資料壓縮的意思，而實則出于完全不同的考慮。經典的資料壓縮技術，無論是音頻壓縮（例如 mp3），圖像壓縮（例如 jpeg），視訊壓縮（mpeg），還是一般的編碼壓縮（zip），都是從資料本身的特性出發，尋找并剔除資料中隐含的備援度，進而達到壓縮的目的。這樣的壓縮有兩個特點：第一、它是發生在資料已經被完整采集到之後；第二、它本身需要複雜的算法來完成。相較而言，解碼過程反而一般來說在計算上比較簡單，以音頻壓縮為例，壓制一個 mp3 檔案的計算量遠大于播放（即解壓縮）一個 mp3
檔案的計算量。
稍加思量就會發現，這種壓縮和解壓縮的不對稱性正好同人們的需求是相反的。在大多數情況下，采集并處理資料的裝置，往往是廉價、省電、計算能力較低的便攜裝置，例如傻瓜相機、或者錄音筆、或者遙控螢幕等等。而負責處理（即解壓縮）資訊的過程卻反而往往在大型計算機上進行，它有更高的計算能力，也常常沒有便攜和省電的要求。也就是說，我們是在用廉價節能的裝置來處理複雜的計算任務，而用大型高效的裝置處理相對簡單的計算任務。這一沖突在某些情況下甚至會更為尖銳，例如在野外作業或者軍事作業的場合，采集資料的裝置往往曝露在自然環境之中，随時可能失去能源供給或者甚至部分喪失性能，在這種情況下，傳統的資料采集-壓縮-傳輸-解壓縮的模式就基本上失效了。
壓縮感覺的概念就是為了解決這樣的沖突而産生的。既然采集資料之後反正要壓縮掉其中的備援度，而這個壓縮過程又相對來說比較困難，那麼我們為什麼不直接「采集」壓縮後的資料？這樣采集的任務要輕得多，而且還省去了壓縮的麻煩。這就是所謂的「壓縮感覺」，也就是說，直接感覺壓縮了的資訊。
可是這看起來是不可能的事情。因為壓縮後的資料并不是壓縮前的資料的一個子集，并不是說，本來有照相機的感光器上有一千萬個像素，扔掉其中八百萬個，剩下的兩百萬個采集到的就是壓縮後的圖像，──這樣隻能采集到不完整的一小塊圖像，有些資訊被永遠的丢失了而且不可能被恢複。如果要想采集很少一部分資料并且指望從這些少量資料中「解壓縮」出大量資訊，就需要保證：第一：這些少量的采集到的資料包含了原信号的全局資訊，第二：存在一種算法能夠從這些少量的資料中還原出原先的資訊來。
有趣的是，在某些特定的場合，上述第一件事情是自動得到滿足的。最典型的例子就是醫學圖像成像，例如斷層掃描（CT）技術和核磁共振（MRI）技術。對這兩種技術稍有了解的人都知道，這兩種成像技術中，儀器所采集到的都不是直接的圖像像素，而是圖像經曆過全局傅立葉變換後的資料。也就是說，每一個單獨的資料都在某種程度上包含了全圖像的資訊。在這種情況下，去掉一部分采集到的資料并不會導緻一部分圖像資訊永久的丢失（它們仍舊被包含在其它資料裡）。這正是我們想要的情況。
上述第二件事就要歸功于陶哲軒和坎戴的工作了。他們的工作指出，如果假定信号（無論是圖像還是聲音還是其他别的種類的信号）滿足某種特定的「稀疏性」，那麼從這些少量的測量資料中，确實有可能還原出原始的較大的信号來，其中所需要的計算部分是一個複雜的疊代優化過程，即所謂的「L1-最小化」算法。
把上述兩件事情放在一起，我們就能看到這種模式的優點所在。它意味着：我們可以在采集資料的時候隻簡單采集一部分資料（「壓縮感覺」），然後把複雜的部分交給資料還原的這一端來做，正好比對了我們期望的格局。在醫學圖像領域裡，這個方案特别有好處，因為采集資料的過程往往是對病人帶來很大麻煩甚至身體傷害的過程。以 X 光斷層掃描為例，衆所周知 X 光輻射會對病人造成身體損害，而「壓縮感覺」就意味着我們可以用比經典方法少得多的輻射劑量來進行資料采集，這在醫學上的意義是不言而喻的。
這一思路可以擴充到很多領域。在大量的實際問題中，我們傾向于盡量少地采集資料，或者由于客觀條件所限不得不采集不完整的資料。如果這些資料和我們所希望重建的資訊之間有某種全局性的變換關系，并且我們預先知道那些資訊滿足某種稀疏性條件，就總可以試着用類似的方式從比較少的資料中還原出比較多的信号來。到今天為止，這樣的研究已經拓展地非常廣泛了。
但是同樣需要說明的是，這樣的做法在不同的應用領域裡并不總能滿足上面所描述的兩個條件。有的時候，第一個條件（也就是說測量到的資料包含信号的全局資訊）無法得到滿足，例如最傳統的攝影問題，每個感光元件所感覺到的都隻是一小塊圖像而不是什麼全局資訊，這是由照相機的實體性質決定的。為了解決這個問題，美國 Rice 大學的一部分科學家正在試圖開發一種新的攝影裝置（被稱為「單像素照相機」），争取用盡量少的感光元件實作盡量高分辨率的攝影。有的時候，第二個條件（也就是說有數學方法保證能夠從不完整的資料中還原出信号）無法得到滿足。這種時候，實踐就走在了理論前面。人們已經可以在算法上事先很多資料重建的過程，但是相應的理論分析卻成為了留在數學家面前的課題。
但是無論如何，壓縮感覺所代表的基本思路：從盡量少的資料中提取盡量多的資訊，毫無疑問是一種有着極大理論和應用前景的想法。它是傳統資訊論的一個延伸，但是又超越了傳統的壓縮理論，成為了一門嶄新的子分支。它從誕生之日起到現在不過五年時間，其影響卻已經席卷了大半個應用科學。