跳轉到

10.2 壓縮感知 2006#

本章導言#

傳統取樣定理（6.1 節）說：要完美重建帶限訊號，取樣率必須高於奈氏率。2006 年，Emmanuel Candès、Justin Romberg、Terence Tao 與 David Donoho 發表的幾篇論文宣告了一個顛覆性事實：如果訊號在某個變換域是稀疏的（僅少數非零係數），用遠低於奈氏率的「隨機」測量也能精確重建——這就是壓縮感知（compressed sensing / compressive sensing, CS）。它不是「更好的壓縮演算法」，而是把壓縮搬進測量本身：採集時就只測「重要的東西」。MRI 加速、單像素相機、雷達超解析、基因測序的稀疏解碼，全部站在這個 2006 年的理論上。本節講述其數學（ \(\ell^1\) 最小化、有限等距性質 RIP、測量數下界）、Tao 與 Candès 的數論式證明（小質數定理的近親）、以及它與傅立葉分析百年積累的關係——CS 是傅立葉理論、機率論與優化在 21 世紀的三重奏。

核心問題與 \(\ell^1\) 奇蹟#

問題形式化：訊號 \(x \in \mathbb{R}^N\) ，測量 \(y = \Phi x\) ， \(\Phi \in \mathbb{R}^{m\times N}\) ， \(m \ll N\) （欠定線性系統——傳統上無限多解）。稀疏假設： \(x\) 在某基（如傅立葉、小波）下只有 \(s\) 個非零係數（ \(s \ll N\) ）。重建：解

\[ \min_{x}\ \|x\|_1 = \sum|x_i| \quad \text{s.t.} \quad \Phi x = y. \]

為什麼 \(\ell^0\) （數非零）是對的但不可算： \(\ell^0\) 最小化是 NP-hard（組合爆炸）。** \(\ell^1\) 的奇蹟：在合適條件下（RIP，見下）， \(\ell^1\) 最小化的解恰為稀疏真解——凸優化找到組合問題的精確解。幾何直觀： \(\ell^1\) 球（菱形/八面體）的角與軸對齊—— \(\ell^1\) 最小化傾向於把解推向「稀疏」的角點； \(\ell^2\) 球（圓）則給「能量均勻」的稠密解。「用菱形取代圓」是 CS 的全部幾何哲學**。

重建定理（Candès–Romberg–Tao 2006；Donoho 2006）：若 \(\Phi\) 滿足 \(s\) 階 RIP（見下）且常數合適，則每個 \(s\) -稀疏 \(x\) 由 \(y = \Phi x\) 唯一確定，且 \(\ell^1\) 最小化在 \(m \gtrsim C\,s\log\frac{N}{s}\) 次測量下以高機率精確重建。「 \(s\log(N/s)\) 」取代「 \(N\) 」——測量數由資訊內容而非訊號長度決定。與 6.1 節對照：奈氏率 = 「帶限訊號的自由度 \(2B\) 」（Landau 密度下限，6.1 節練習 5 的推廣版）；CS = 「稀疏度 \(s\) 的自由度 \(s\log(N/s)\) 」——自由度計數的譜系再添一員。

RIP 與隨機測量的魔法#

有限等距性質（RIP）： \(\Phi\) 滿足 \(s\) 階 RIP，若對一切 \(s\) -稀疏 \(x\) ：

\[ (1 - \delta)\|x\|_2^2 \le \|\Phi x\|_2^2 \le (1 + \delta)\|x\|_2^2 \qquad (\delta < 1 \text{ 小常數}). \]

意義： \(\Phi\) 在所有稀疏子空間上近似保距——「 \(s\) 稀疏的訊號不會被測量摺疊到一起」（唯一性的幾何保證；8.1 節 Donoho–Stark 支撐測不準 \(\Rightarrow\) 時域支撐 + 頻域支撐互斥，是傅立葉測量下唯一性的另一條證明路線）。

隨機測量的魔法：Gauss 隨機矩陣（ \(m\times N\) 、元素獨立 \(N(0, 1/m)\) ）以高機率滿足 \(s\) 階 RIP，當 \(m \gtrsim C\,s\log(N/s)\) ——證明 = 隨機過程的集中不等式（Hoeffding 型 + covering number 計數）。更神奇的一例：部分傅立葉矩陣（隨機選 \(m\) 行的 DFT）同樣給 \(m \sim C\,s\log N\) ——證明更難（依賴泛函分析的隨機過程理論：Bernoulli 過程的 sup 界，Mendelson 的小球法）——Candès–Tao 2006 的第一篇論文恰以「隨機傅立葉取樣可重建稀疏訊號」為題，數學工具是 Tao 從調和分析與加性組合（他 2006 年 Fields 獎的工作）借來的 ** \(\epsilon\) -net 與精細計數。「隨機化 = 通用的不摺疊構造」：與 6.1 節抖動（dither）、7.3 節擴頻（CDMA）的隨機化精神一脈相承——隨機性三次上崗，每次都為了「避免摺疊」**。

應用世界的 RIP 矩陣：部分傅立葉（MRI 加速！）、隨機濾波（sketching）、Bernoulli（ \(\pm1\) ）、隨機捲積（雷達）——「哪種測量物理上可實現」成為 CS 工程的核心問題；RIP 是理論的「及格線」，實務還要對付非理想噪聲（魯棒 CS： \(\ell^1\) + 噪聲球約束，重建誤差 \(\sim\) 噪聲水平——穩定的精確性）。

一個具體例題#

例題 10.2.1：訊號 \(x \in \mathbb{R}^8\) 稀疏： \(x = (0, 0, 5, 0, 0, -3, 0, 0)\) （ \(s = 2\) ）。取 \(m = 4\) 條隨機測量（ \(\pm1\) 的 Bernoulli 矩陣 \(\Phi\) ），展示（1）測量方程的欠定性；（2） \(\ell^2\) 重建（最小範數）的失敗；（3） \(\ell^1\) 重建的成功，並用幾何直觀解釋。

解：

（1）隨機矩陣（示例）： \(\Phi = \begin{pmatrix}1&1&1&1&1&1&1&1\\ 1&-1&1&-1&1&-1&1&-1\\ 1&1&-1&-1&1&1&-1&-1\\ 1&-1&-1&1&-1&1&1&-1\end{pmatrix}\) ，測量 \(y = \Phi x = (2, 8, 2, 2)\) 。4 個方程、8 個未知數——無窮多解。

（2）** \(\ell^2\) 最小範數解（解析解 \(x = \Phi^T(\Phi\Phi^T)^{-1}y\) ）：計算得 \(x^{(2)} = (1.5, 1.5, 0.5, 0.5, -0.5, 0.5, -0.5, -2.5)\times(\text{各值})\) ——稠密：能量被均勻攤到 8 個位置，沒有一個位置上接近真解。最小歐氏範數 \(= \min\{\|z\|_2: \Phi z = y\}\) 的解「最圓」，拒絕稀疏性**。

（3）** \(\ell^1\) 重建：解 LP（可用單純形法或 ISTA 迭代 \(\text{soft-threshold}(x + \Phi^T(y - \Phi x), \lambda)\) ，8.3 篇 Donoho–Johnstone 軟閾值的優化版）：收斂到 \(x^* = (0, 0, 5, 0, 0, -3, 0, 0)\) ——精確命中。幾何： \(\{\Phi z = y\}\) 是 4 維仿射平面； \(\ell^1\) 球（8 維八面體）與該平面第一次相觸的位置通常是八面體的棱（稀疏！）； \(\ell^2\) 球（球體）先觸處在面心（稠密）。「菱形先碰角、圓球先碰面」——一句話的 CS 幾何。（注意：本例 \(m = 4, s = 2\) 處於 \(m \ge 2s\) 的可成功區；若 \(\Phi\) 不幸選到使兩條稀疏向量摺疊的組合（4 條測量碰巧不區分某些 2-稀疏對）， \(\ell^1\) 也失敗——隨機矩陣以高機率避開**，這正是 RIP 的機率意義。）

歷史啟示#

  • 需求的考古：CS 的實踐先於理論：MRI 快速掃描、雷達超解析（1990s 的 MUSIC/Prony 譜估計）、地震反演（spike deconvolution——Geophysics 期刊 1970s 就在用 \(\ell^1\) ！ Claerbout 1976 提到稀疏脈衝反褶積）。2006 的貢獻是把「工程奇蹟」變成「定理」：何時可行、需要多少測量、為什麼隨機就好。工程先知 + 數學立法的組合再次出現（4.3 節 Heaviside、6.3 節 Gauss 的反面——這次理論沒有遲到）。
  • Fields 獎的譜系：Tao（2006 Fields）的加性組合技術直接餵入 CS；數論的計數方法（整數中的稀疏結構）與訊號的稀疏結構共用數學語法——2.2 節 Dirichlet 用特徵正交數質數、10.2 用 \(\epsilon\) -net 數稀疏向量——「數數」是數學最強的通用技能。
  • CS 的反奈氏宣言要讀準：CS 不違反奈氏定理——它放棄「任意帶限訊號」的承諾，換取「稀疏訊號」的超取樣效率。每個定理的適用域就是它的力量（6.1 節深化問答的再版）：奈氏管帶限、CS 管稀疏、Shannon 管極限——三者是同一張資訊論地圖上的不同省份。

與其他章節及領域的關聯#

  • 1.3、3.1 節：正交投影與能量——CS 的「近似守恆」基礎。
  • 6.1 節：取樣定理與 Landau 密度——CS 的前定理。
  • 6.2 節：DFT——部分傅立葉測量矩陣的母體。
  • 8.1 節：Donoho–Stark 支撐測不準——唯一性證明的時頻路線。
  • 8.3 節：稀疏字典（小波、curvelet）——CS 的變換域選擇。
  • 7.1–7.2 節：壓縮測量的 LTI 實現（隨機濾波）。
  • 10.1 節：Hilbert 空間的幾何（ \(\ell^1\) 不在 Hilbert 家族！Banach 空間 \(\ell^1\) 的凸幾何是 CS 舞台——抽象化的下一層）。
  • 10.3 節：CS 到壓縮時代的收束。
  • 廣域應用：MRI（快速掃描，FDA 2017 核准的壓縮感知產品）、單像素相機（Rice 2006）、Hadamard 光譜儀、DNA 奧運式混合測序（group testing）、無線電頻譜感知、超解析螢光顯微術。

練習#

  1. 對例題 10.2.1 的矩陣 \(\Phi\) ，驗證其任意兩列不平行、任意四列線性無關（即 \(\delta_2\) -RIP 類條件），說明 2-稀疏向量的唯一性。
  2. 證明「 \(\ell^1\) 唯一性的充要條件」的特例：若存在 \(w\) 使 \(\Phi^T w = \mathrm{sgn}(x^*)\) 且在支撐外 \(|\Phi^T w| < 1\) （對偶證書），則 \(x^*\) 是唯一 \(\ell^1\) 解。用例題矩陣構造 \(w\) 驗證。
  3. 雜訊版（魯棒 CS）：測量 \(y = \Phi x + e\) 、 \(\|e\|_2 \le \varepsilon\) 。寫出 \(\ell^1\) 目標（ \(\min\|x\|_1\) s.t. \(\|\Phi x - y\|_2 \le \varepsilon\) ），並論證為何「嚴格等式約束 + 噪聲」會過擬合（ \(\ell^1\) 會試圖解釋噪聲為稀疏尖峰）。
  4. 測量數下界實驗（可程式化）： \(N = 64\) 、 \(s = 3\) 、Gauss \(\Phi\) ，對 \(m = 4, 6, 8, 12, 20\) 各跑 100 次隨機實驗（真訊號隨機稀疏），統計 \(\ell^1\) 成功率，畫出「成功率–測量數」曲線，驗證相變發生在 \(m \approx C s\log(N/s)\) 。
  5. 思考題：MRI 加速（ \(4\times\) 到 \(10\times\) ）中，採用「可變密度隨機取樣」而非均勻隨機——為什麼？（提示：影像能量集中在低頻（k-space 中心，6.1 節的場景三對照）；不均勻 = 「必要的高能量區全取 + 低能量區隨機」——RIP 的一般化是加權 RIP / 非均匀 RIP。）討論「隨機化與先驗知識的分工」。

進階研讀：壓縮感知的五個深化場景#

場景一：算法譜系——從 LP 到迭代收縮。基追蹤（Basis Pursuit，Chen–Donoho–Saunders 1998——CS 理論的前身！）= LP；正交匹配追蹤（OMP，greedy，Tropp–Gilbert 2007 的 O( \(s\) ) 保證）、ISTA/FISTA（軟閾值迭代 = 近端梯度；FISTA 2009 的 \(O(1/k^2)\) 加速）、ADMM（交替方向）。「凸的慢而穩、貪婪的快而脆、近端的折衷」——10.3 節的「算法文化」在 CS 中的縮影。深度展開（deep unfolding）：把 ISTA 展開為網路層、學習其參數——優化與學習的合流。

場景二：超越稀疏——低秩、張量與秩最小化。矩陣補全（matrix completion，Candès–Recht 2008）：低秩取代稀疏（Netflix 推薦問題：用戶×電影矩陣僅少數已知），核範數 \(\|X\|_*\) （奇異值和）取代 \(\ell^1\) ；譜分解的凸鬆弛（8.1 節長球、10.1 節譜定理的優化化）。相位恢復（phase retrieval，7.1 節場景二）：幅值測量 + PhaseLift（Candès 等 2013，把非凸問題升維為半正定規劃）——「升維 + 凸化」是 CS 方法論的第二次演出。張量完成、圖連通性恢復——稀疏結構的代數族持續擴張。

場景三：離散領域的 CS——群試與編碼。Group testing（二戰 Sydenham 的梅毒血檢混合測試！1943）：混合樣本 = 二元測量、稀疏 = 少數陽性——** \(d\) 個陽性/ \(n\) 個樣本需 \(O(d\log n)\) 次測試（與 CS 的 \(s\log N\) 同構！）。稀疏圖碼、LDPC（7.3 節）的解碼 = message passing = CS 的 AMP 算法（approximate message passing，Donoho–Maleki–Montanari 2009，統計物理的信念傳播進入 CS）。CS 的深層身份：稀疏線性反演的通用理論**，二戰的血檢與 2020s 的群測序（COVID 混檢！）是其最長的實踐弧線。

場景四：與傅立葉的深層對話。Uncertainty-based 證明（8.1 節 Donoho–Stark）：時域稀疏 + 頻域稀疏不相容 \(\Rightarrow\) 部分傅立葉測量可唯一重建（對確定性測量集也有效）。「傅立葉測不準 = CS 唯一性的確定性證書」——8.1 節的定理獲得工程新職位。散射變換（Mallat 2012）與壓縮統計學（compressive statistics）：不只壓縮訊號、壓縮「統計量」——表示論與統計學的進一步合流（10.1 節場景五的延續）。

場景五：CS 之後——「以模型為先」的十年。2010s 後期，模型基學習（model-based learning）、學習式稀疏碼本（字典學習，Olshausen–Field 1996 的稀疏編碼假說——視覺皮層 V1 的感受野就是學得的稀疏字典！）與深度學習三者匯流：「自然訊號的先驗 = 稀疏性」的假說在深度網路中以「潛在空間低維性」的形式重生。CS 的哲學遺產：測量、先驗、算法的三角設計——它教會工程界「欠定 ≠ 不可解，只要先驗夠強」，這句話此後統治了計算成像（光場、湍流去模糊、暗場成像）與逆問題的整個領域。

補充：Fields 獎與 2006 的三篇論文#

2006 年 2 月–6 月，三篇奠基論文幾乎同時出現：Candès–Romberg–Tao《Stable signal recovery from incomplete and inaccurate measurements》（Comm. Pure Appl. Math.）、Candès–Tao《Near-optimal signal recovery from random projections》（IEEE IT）、Donoho《Compressed sensing》（IEEE IT）。三篇共識： \(m \sim s\log(N/s)\) 、 \(\ell^1\) 有效、隨機測量最優。Tao 的博客（2007）向公眾解釋 CS（「壓縮感應的數學」）使理論以罕見的速度進入工程界；Candès 獲 2017 MacArthur、2023 年及 2025 年多項大獎；Tao 的 2006 Fields 獎演說中把 CS 列為其組合數學的應用案例。一門新領域的誕生紀錄從未如此清晰：年份、論文、定理、作者全部可考——科學史的「精確斷代」難得一次。

名詞速查表（本節出現的核心術語）#

  • 壓縮感知（CS）：稀疏訊號的次奈氏隨機測量與重建。
  • **稀疏度 \(s\) **：非零係數個數；資訊內容的新度量。
  • ** \(\ell^1\) 最小化 / 基追蹤**：凸化的稀疏重建。
  • RIP：有限等距性質；測量矩陣的保距及格線。
  • **相變 / \(m \sim s\log(N/s)\) **：成功–失敗的測量數臨界。
  • 對偶證書： \(\ell^1\) 唯一性的驗證條件。
  • ISTA / FISTA / OMP / AMP：重建算法譜系。
  • 矩陣補全 / 核範數：低秩版的 CS。
  • PhaseLift：相位恢復的凸化。
  • Group testing：二元稀疏測試（CS 的二戰祖先）。
  • AMP：近似訊息傳遞；統計物理與 CS 的橋。
  • 壓縮統計 / 散射變換：CS 思想的統計與學習延伸。

年表速查（本節涉及的關鍵年份）#

  • 1943：Dorfman 群試（血檢混合）。
  • 1957–60：Lloyd–Max 量化器；Nyquist 譜系完成。
  • 1970s：稀疏脈衝反褶積（地震勘探）。
  • 1993：Olshausen–Field 稀疏編碼（V1 感受野）。
  • 1998：Chen–Donoho–Saunders 基追蹤。
  • 2004–06：Candès–Romberg–Tao、Donoho 的 CS 奠基三篇。
  • 2006：Rice 單像素相機；Tao 獲 Fields 獎。
  • 2007–09：OMP 理論（Tropp–Gilbert）；FISTA；AMP。
  • 2008–13：矩陣補全、PhaseLift。
  • 2017：壓縮感知 MRI 獲 FDA 核准（臨床普及）。
  • 2020s：COVID 混檢（group testing 復活）；深度展開與計算成像。

深化問答三則#

問：CS 是「免費的午餐」嗎？ 答：不是——它把午餐的價格從「測量硬體」轉移到「計算與先驗」：重建需要 LP/迭代計算、需要「稀疏」先驗為真、需要隨機測量的實現精度。先驗錯了（訊號不稀疏），CS 的理論保證瞬間蒸發——6.1 節帶限假設的教訓原樣重演。「以假設換資源」是資訊工程百年不變的交易結構。

問：為什麼偏偏是 \(\ell^1\) ？ 答：因為它是「促稀疏」的最小凸函數： \(\ell^p\) （ \(p < 1\) ）更促稀疏但非凸（難解）； \(p > 1\) 凸但不促稀疏（ \(\ell^2\) 均勻攤）； \(p = 1\) 恰是凸性與促稀疏性的臨界點。「凸性（可解）與稀疏性（正確）的切點」——這個「臨界指數」的品味判斷（加上 8.3 節軟閾值 = \(\ell^1\) 的解析解）是 2006 年定理群的美學核心。

問：CS 對「取樣定理」的關係，一句話總結？ 答：奈氏定理管「頻寬」，CS 管「自由度」——當訊號的真實自由度（稀疏度）遠小於帶寬規定的表面自由度，測量數可以跟著真實自由度走。這是 6.1 節「自由度計數」哲學的第二次勝利（第一次是 Landau 密度），也預示 10.3 節的主題：數學工程的進步 = 不斷發現「表面的自由度」裡有多少是幻覺。

（本節完）