在壓縮感知、信號處理、機器學習特徵選擇等領域,匹配追蹤(Matching Pursuit, MP)與正交匹配追蹤(Orthogonal Matching Pursuit, OMP)是構建稀疏表示的兩大經典貪婪算法。本文從數學原理、迭代細節、收斂保證、工程優化四個維度深度剖析。
問題建模:過完備字典下的稀疏編碼
給定信號 y ∈ ℝⁿ,過完備字典 D ∈ ℝⁿˣᵏ (n ≪ k),尋找稀疏係數向量 x ∈ ℝᵏ 使 y ≈ Dx,且 ‖x‖₀ ≤ T(L0 范數約束非零元個數)。NP-hard 問題,貪婪算法給出近似解。
MP 算法:殘差投影的貪婪選擇
- 初始化:殘差 r⁰ = y,索引集 Λ⁰ = ∅,近似解 x⁰ = 0。
- 迭代 t = 1..T:
- 計算相關性:c = Dᵀ rᵗ⁻¹,選擇 λₜ = argmaxⱼ |cⱼ|(與殘差相關性最大的原子)。
- 更新索引集:Λᵗ = Λᵗ⁻¹ ∪ {λₜ}。
- 係數更新:xₜ = Dₜ⁺ y(Dₜ 為選中原子子矩陣,⁺ 為偽逆)。MP 僅更新新選原子係數:αₜ = ⟨d_{λₜ}, rᵗ⁻¹⟩,xₜ[λₜ] = αₘ,其餘保持。
- 殘差更新:rᵗ = y - Dₜ xₜ(或 rᵗ = rᵗ⁻¹ - αₜ d_{λₜ})。
- 停止條件:迭代次數達 T、殘差範數 < ε、或最大相關性 < 閾值。
缺陷: 同一原子可能被重複選擇;係數非正交投影,殘差不保證與已選子空間正交,收斂較慢。
OMP 算法:正交投影保證最優係數
關鍵改進:每輪重新計算所有已選原子的最優係數,使殘差與已選子空間正交。
- 選原子同 MP:λₜ = argmaxⱼ |⟨dⱼ, rᵗ⁻¹⟩|。
- 擴展索引集 Λᵗ。
- 最小二乘求解:xₜ = argmin ‖y - Dₜ x‖₂ = (Dₜᵀ Dₜ)⁻¹ Dₜᵀ y(或 QR 更新避免矩陣求逆)。
- 殘差 rᵗ = y - Dₜ xₜ,保證 rᵗ ⟂ span(Dₜ)。
優勢: 同一原子不會被重複選;有限步(≤ k)精確恢復 k-稀疏信號;滿足 RIP(Restricted Isometry Property)條件下有理論恢復保證。
收斂性與復原條件
- 相干係數 μ(D):μ < 1/(2k-1) 時 OMP 可精確恢復 k-稀疏信號(Tropp 2004)。
- RIP 條件:δ_{k+1} < 1/√(k+1) 保證 OMP 成功(Zhang 2011)。
- MP 收斂速度:指數級收斂,但需字典不可約、信號在閉包中。
工程優化與變體
- Batch OMP / GOMP:每輪選多個原子,加速大規模問題。
- OMP with QR 分解:增量更新 QR,避免重複矩陣求逆,O(nk²) → O(nk)。
- 正則化 OMP (ROMP)、Subspace Pursuit (SP)、CoSaMP:引入反向剪枝、子空間擴展,接近凸優化精度。
- 硬體加速:FPGA/GPU 並行計算內積與 QR 分解。
MP/OMP 以「貪婪+正交」的優雅數學結構,成為稀疏編碼領域的基石。理解其幾何直覺——每步在殘差方向「貪婪地」抓取最相關原子,OMP 更進一步「正交化」已選子空間——是通往壓縮感知、字典學習、深度網絡剪枝等前沿應用的必經之路。