2006 — 壓縮感知#

案件摘要#

2006 年，Emmanuel Candès、Justin Romberg、Terence Tao 與 David Donoho 兩組人幾乎同時公布一個違反直覺的結論：一個稀疏訊號 \(x \in \mathbb{R}^n\) ，即使只測得遠少於 \(n\) 個線性測量 \(y = Ax\) （ \(m \ll n\) ），只要矩陣 \(A\) 滿足「受限等距性質（RIP）」，就能透過解一個凸優化問題 \(\min \|x\|_1\) 完美恢復原訊號。Nyquist–Shannon 取樣定理近八十年的統治，被撕開了一道縫。

前因 -- 為什麼會有這個案子#

1949 年定型的 Nyquist–Shannon 取樣定理：訊號頻寬 \(B\) ，取樣率必須 \(\geq 2B\) ，否則無法重建。這成為所有感測系統的鐵律。
但自然與工程訊號在某個變換域往往是稀疏的：影像在 wavelet 域、音訊在 Fourier 域、MRI 的 \(k\) -space 大部分接近零。JPEG、MP3 早就在利用這一點——只是先取滿樣本再丟棄係數，浪費在前端。
1990 年代稀疏表示理論（matching pursuit、basis pursuit 1993–1999，Chen–Donoho–Saunders 的 \(\ell_1\) 去雜訊）累積了「 \(\ell_1\) 能促稀疏」的經驗。
Candès 在做雷達雜訊實驗時意外發現：隨機丟掉一部分 Fourier 資料，用 \(\ell_1\) 最小化竟能完美還原影像。Tao 一看，說「這需要數學證明」——兩人（加上 Romberg）在 2006 年交出證明；同年 Donoho 獨立發表壓縮感知的系統理論。

線索與推理 -- 數學式、程式、理論#

線索一：欠定系統的無窮多解#

線性系統 \(y = Ax\) ， \(A \in \mathbb{R}^{m \times n}\) ， \(m < n\) 時是欠定的：解空間是 \((n-m)\) 維的仿射子空間，傳統最小平方 \(\min\|x\|_2\) 無法挑出「真解」—— \(\ell_2\) 球的最小點落在解空間與球的切點，通常是稠密向量。

線索二： \(\ell_1\) 的魔法——促稀疏#

改用 \(\min \|x\|_1 \text{ s.t. } Ax = y\) 。幾何上， \(\ell_1\) 球（cross-polytope、菱形）有「尖角」，解空間撞上菱形的機率高於撞上球面，而撞上尖角意味著大量分量為零——解是稀疏的。這個「basis pursuit」是凸問題（ \(\ell_1\) 是 \(\ell_0\) 計數的最近凸鬆弛），可用線性規劃、ISTA/FISTA 或 LASSO 型軟門檻迭代求解。

線索三：RIP——何時可恢復？#

矩陣 \(A\) 滿足 \(s\) -階受限等距性質（RIP），若存在 \(\delta_s \in (0,1)\) 使所有 \(s\) -稀疏向量 \(v\) 滿足：

\[ (1-\delta_s)\|v\|_2^2 \leq \|Av\|_2^2 \leq (1+\delta_s)\|v\|_2^2 \]

Candès–Tao（2005–2006）與 Candès–Romberg–Tao（2006）證明：若 \(A\) 的 RIP 常數 \(\delta_{2s} < \delta^* \approx 0.414\) （精確常數隨證明方式而異， \(\sqrt{2}-1\) 是經典門檻），則 basis pursuit 唯一且精確恢復所有 \(s\) -稀疏訊號。關鍵測量數：

\[ m \gtrsim C\, s \log(n/s) \]

隨機 Gaussian、Bernoulli、部分 Fourier 矩陣皆以壓倒性機率滿足 RIP。物理直覺： \(A\) 必須「對所有稀疏方向都不偏心」——不能讓任何稀疏向量被壓扁或放大。

線索四：對照實驗—— \(\ell_1\) vs \(\ell_2\)#

在同一組欠定測量下， \(\ell_2\) 最小平方給出糊成一片的解， \(\ell_1\) 給出乾淨的稀疏解。差別不在取樣多寡，而在懲罰範數的幾何形狀。

程式碼範例： \(\ell_1\) 最小化 vs \(\ell_2\) 對照（numpy 迭代軟門檻 ISTA）#

import numpy as np

np.random.seed(0)
n, m, s = 256, 80, 12          # 原訊號長 256，只測 80 點，稀疏度 12

# 稀疏訊號：只有 s 個非零尖峰
x_true = np.zeros(n)
idx = np.random.choice(n, s, replace=False)
x_true[idx] = np.random.randn(s)

A = np.random.randn(m, n) / np.sqrt(m)   # 隨機測量矩陣（近似滿足 RIP）
y = A @ x_true

# --- $\ell_2$ 最小平方（欠定 => 不可辨識，取偽逆最小範數解）---
x_l2 = np.linalg.pinv(A) @ y

# --- $\ell_1$ 最小化：ISTA 迭代軟門檻 ---
def soft_threshold(v, t):
    return np.sign(v) * np.maximum(np.abs(v) - t, 0)

L = np.linalg.norm(A, 2) ** 2          # Lipschitz 常數
x_l1 = np.zeros(n)
for _ in range(2000):
    x_l1 = soft_threshold(x_l1 + A.T @ (y - A @ x_l1) / L, 1.0 / L)

print("非零個數  真解:%2d  ℓ1:%2d  ℓ2:%3d" % (s, np.sum(np.abs(x_l1) > 1e-6), np.sum(np.abs(x_l2) > 1e-6)))
print("相對誤差  ℓ1: %.2e   ℓ2: %.2e" % (
      np.linalg.norm(x_l1 - x_true) / np.linalg.norm(x_true),
      np.linalg.norm(x_l2 - x_true) / np.linalg.norm(x_true)))

典型輸出： \(\ell_1\) 的解非零個數 \(\approx s\) 、相對誤差接近 \(10^{-15}\) （完美恢復）； \(\ell_2\) 的解有上百個非零、誤差 \(10^{-1}\) 級——同一組測量，判決天差地遠。

結案 -- 後果與影響#

MRI 加速：壓縮感知已進入臨床（FDA 2017 核准相關產品），MRI 掃描時間縮短數倍，兒童與幽閉恐懼症患者受惠最深。
雷達與通訊：A/D 轉換可低於 Nyquist 率（analog-to-information）；單像素相機（Rice 大學 2006）是概念驗證。
數學面：帶動稀疏恢復、相位恢復（phase retrieval）、矩陣完成（matrix completion，Netflix 獎）等整個「非漸近隨機矩陣理論」學派；Tao 由此奠定組合與機率方法在應用數學的地位。
稀疏線性代數成為顯學： \(\ell_1\) 正則化（LASSO 1996 Tibshirani）從統計學工具升格為普適原理。
教科書與課程：Foucart & Rauhut《A Mathematical Introduction to Compressive Sensing》(2013) 成為標準參考。

關鍵人物與文獻#

人物	角色
Emmanuel Candès	雷達實驗意外發現，理論奠基
Terence Tao	提供嚴格數學證明，2006 Fields 級方法
Justin Romberg	與 Candès–Tao 合作首篇論文
David Donoho	2006 獨立系統理論，「壓縮感知」命名者
David Nyquist / Claude Shannon	被部分改寫的取樣定理（前案）

E. J. Candès, J. Romberg, T. Tao, "Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information", IEEE Trans. Inform. Theory 52(2), 489–509 (2006)。
E. J. Candès, T. Tao, "Near-Optimal Signal Recovery from Random Projections...", IEEE Trans. Inform. Theory 52(12), 5406–5425 (2006)。
D. L. Donoho, "Compressed Sensing", IEEE Trans. Inform. Theory 52(4), 1289–1306 (2006)。
S. S. Chen, D. L. Donoho, M. A. Saunders, "Atomic Decomposition by Basis Pursuit", SIAM J. Sci. Comput. (1998)。