2006-壓縮感知#

案件檔案
案發年份	2006（Emmanuel Candès–Justin Romberg–Terence Tao 與 David Donoho）
主嫌	欠定線性系統 \(y=\Phi x\) 的稀疏恢復
受害者	Shannon–Nyquist 採樣定理：「樣本要夠多」的金科玉律
關鍵證人	Candès–Romberg–Tao（2006 論文）、Donoho（2006 論文）
結案結果	RIP 條件與 \(l^1\) 極小化問世，欠定系統的奇蹟

案發現場#

2006 年之前，信號處理的第一定律是 Shannon–Nyquist 採樣定理：帶寬 \(B\) 的信號要以至少 \(2B\) 的速率採樣才能完全重構。但一樁大案在實務中浮現：

MRI（核磁共振）採樣太慢：病人要忍受長時間掃描；MR 影像在小波域稀疏，但沒人敢少採樣。
欠定系統沒有唯一解：測量數 \(m\ll n\) （未知數）時， \(y=\Phi x\) 有無窮多解，線性代數束手無策。
** \(l^2\) 極小化的失敗**：取 \(\min\|x\|_2\) 會把能量抹平到所有座標，稀疏信號無法恢復。

謎題的核心：在什麼條件下，稀疏信號能從極少的測量中精確恢復？ 這是 Candès、Romberg、Tao 與 Donoho 在 2006 年要接的案子。

偵查過程#

偵查策略是：把「唯一性」由線性代數轉移到組合幾何——用稀疏性與 \(l^1\) 極小化接手。

第一步：稀疏性的定義#

信號 \(x\in\mathbb{R}^n\) 是 \(s\) -稀疏，若 \(\|x\|_0:=\#\{i:\ x_i\ne 0\}\le s\) 。壓縮感知的設定：

\[ y=\Phi x,\qquad \Phi\in\mathbb{R}^{m\times n},\qquad m\ll n,\qquad \|x\|_0\le s . \]

第二步：唯一性的組合條件#

線索一（組合論）：若 \(\Phi\) 的任意 \(2s\) 列都線性獨立（spark 條件： \(\mathrm{spark}(\Phi)>2s\) ），則 \(s\) -稀疏解唯一。但這是組合性質（需檢查 \(\binom{n}{2s}\) 個子集），無法直接檢驗。

線索二（機率論）：隨機矩陣（Gaussian、Bernoulli）以壓倒性機率滿足 spark 條件，只要

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

第三步：RIP 條件#

Candès–Tao 的高招：把 spark 條件放寬為可檢驗的「近似正交」。矩陣 \(\Phi\) 滿足階 \((s,\delta)\) 的有限等距性質（RIP），若對所有 \(s\) -稀疏 \(x\) ：

\[ (1-\delta)\|x\|_2^2\le\|\Phi x\|_2^2\le(1+\delta)\|x\|_2^2 . \]

RIP 等價於 \(\Phi\) 的任意 \(s\) 列子矩陣近似等距。隨機矩陣滿足 RIP 的機率界：

矩陣類型	RIP 條件	機率
Gaussian \(\frac{1}{\sqrt m}\Phi_{ij}\sim N(0,1)\)	\(m\ge C\,s\log(n/s)\)	\(1-e^{-cm}\)
Bernoulli \(\pm\frac{1}{\sqrt m}\)	同上	\(1-e^{-cm}\)
隨機部分 Fourier	\(m\ge C\,s\log^4 n\) 型	\(1-e^{-cm}\)

第四步： \(l^1\) 極小化的奇蹟#

恢復演算法（basis pursuit）：

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

Candès–Romberg–Tao 與 Donoho 證明核心定理：

若 \(\Phi\) 滿足 RIP 階 \((2s,\delta<\sqrt2-1)\) ，則 \(\min\|x\|_1\) 的解就是唯一的 \(s\) -稀疏解。

偵查的兩段式：

幾何直覺： \(l^1\) 球（八面體）在 \(n\) 維中的頂點落在座標軸上；隨機 \(m\) 維子空間與 \(l^1\) 球的接觸點以壓倒性機率是稀疏的頂點（射影幾何： \(m\ge C s\log(n/s)\) 時 \(l^1\) 球的 \(s\) -骨架在隨機投影下保持）。
解析論證：對任意稀疏對比向量 \(h=x-x^*\) ，用 RIP 與 \(\|\cdot\|_1\) 的稀疏化不等式（ \(\|h_{T^c}\|_1\le\|h_T\|_1\) 型）證 \(\|h\|_2\) 的壓縮，歸納得 \(h=0\) 。

第五步：偵查筆記本——Nyquist vs 壓縮感知#

對象	Shannon–Nyquist	壓縮感知
測量數	\(m\sim n\) （頻寬決定）	\(m\sim s\log(n/s)\) （稀疏度決定）
恢復	直接線性反演	\(\min\\|x\\|_1\)
條件	帶限	RIP ＋稀疏
稀疏基	Fourier	任意正交基／緊框

第六步：與泛函分析的血統#

壓縮感知是泛函分析百年探案的最後一幕：

Hilbert 空間幾何（1906）： \(l^2\) 的正交性、投影，是 RIP 的語言。
Banach 空間幾何（1920）： \(l^1\) 極小化的射影幾何證明（Figiel–Lindenstrauss–Milman 1981 的先聲）。
小波稀疏表示（1986）： \(dbN\) 的消失矩使自然影像在小波域稀疏——稀疏性的實務來源。
Grothendieck 的對偶視角（1958）：用對偶與張量解剖空間，壓縮感知的「幾何證明」是它的精神後裔。

結案報告#

2006 年 Candès–Romberg–Tao 與 Donoho 聯手結案：欠定系統 \(y=\Phi x\) 在 RIP ＋稀疏性下有唯一解，且 \(\min\|x\|_1\) 以凸優化（線性規劃）恢復。案件遺產如下：

Nyquist 定律的修正：採樣率由「頻寬」改為「稀疏度」； \(m\sim s\log(n/s)\) 取代 \(m\sim n\) 。
MRI 加速：壓縮感知成為 MRI 快速掃描的標準工具（FDA 認證 2017）；遙測、雷達、光譜學跟進。
凸優化的勝利：basis pursuit 是線性規劃（polynomial time），後續的貪心演算法（OMP、CoSaMP）與閾值迭代也有完整理論。
RIP 的工具化：隨機矩陣理論（Johnson–Lindenstrauss 引理、非漸近機率）成為高維幾何的新顯微鏡。
百年探案的完結：從 Hilbert 空間（1906）到壓縮感知（2006），「無窮維能否像歐氏空間一樣推理」的追問，最後以「高維稀疏幾何」的形式抵達應用的最前線。

證據與工具#

關鍵公式一覽表：

工具	公式／陳述	用途
稀疏性	\(\\|x\\|_0\le s\)	模型設定
測量模型	\(y=\Phi x\) ， \(m\ll n\)	欠定系統
RIP	\((1-\delta)\\|x\\|_2^2\le\\|\Phi x\\|_2^2\le(1+\delta)\\|x\\|_2^2\)	可檢驗條件
basis pursuit	\(\min\\|x\\|_1\) s.t. \(\Phi x=y\)	恢復演算法
測量界	\(m\ge C\,s\log(n/s)\)	隨機矩陣機率
spark 條件	\(\mathrm{spark}(\Phi)>2s\)	唯一性（組合）

證明骨架（ \(\min\|x\|_1\) 恢復）：

設 \(x^*\) 為 \(s\) -稀疏真解， \(h=\hat x-x^*\) 為任何對比向量。
由 \(l^1\) 極小化得稀疏化不等式 \(\|h_{T^c}\|_1\le\|h_T\|_1\) 。
用 RIP（ \(\delta<\sqrt2-1\) ）證 \(\|h_T\|_2\) 的壓縮遞推： \(\|h\|_2\) 每層衰減固定比例。
歸納得 \(h=0\) ，故 \(\hat x=x^*\) 。 \(\blacksquare\)

典型例子： \(n=1000\) 、 \(s=10\) 的稀疏信號：Nyquist 需 \(m\approx 1000\) 個測量；壓縮感知只需 \(m\approx 10\log_2(100)=70\) 個隨機測量（Gaussian \(\Phi\) ）。取 \(m=70\) 的 Gaussian 矩陣， \(\min\|x\|_1\) （線性規劃）以壓倒性機率精確恢復——十倍少的測量、同樣精確的重建，欠定系統的奇蹟在此現形。