萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 網路安全 >  >> 網路基礎知識

稀疏表示核心算法:匹配追蹤(MP)與正交匹配追蹤(OMP)原理、迭代流程與收斂性分析

在壓縮感知、信號處理、機器學習特徵選擇等領域,匹配追蹤(Matching Pursuit, MP)與正交匹配追蹤(Orthogonal Matching Pursuit, OMP)是構建稀疏表示的兩大經典貪婪算法。本文從數學原理、迭代細節、收斂保證、工程優化四個維度深度剖析。

問題建模:過完備字典下的稀疏編碼

給定信號 y ∈ ℝⁿ,過完備字典 D ∈ ℝⁿˣᵏ (n ≪ k),尋找稀疏係數向量 x ∈ ℝᵏ 使 y ≈ Dx,且 ‖x‖₀ ≤ T(L0 范數約束非零元個數)。NP-hard 問題,貪婪算法給出近似解。

MP 算法:殘差投影的貪婪選擇

  1. 初始化:殘差 r⁰ = y,索引集 Λ⁰ = ∅,近似解 x⁰ = 0。
  2. 迭代 t = 1..T:
    • 計算相關性:c = Dᵀ rᵗ⁻¹,選擇 λₜ = argmaxⱼ |cⱼ|(與殘差相關性最大的原子)。
    • 更新索引集:Λᵗ = Λᵗ⁻¹ ∪ {λₜ}。
    • 係數更新:xₜ = Dₜ⁺ y(Dₜ 為選中原子子矩陣,⁺ 為偽逆)。MP 僅更新新選原子係數:αₜ = ⟨d_{λₜ}, rᵗ⁻¹⟩,xₜ[λₜ] = αₘ,其餘保持。
    • 殘差更新:rᵗ = y - Dₜ xₜ(或 rᵗ = rᵗ⁻¹ - αₜ d_{λₜ})。
  3. 停止條件:迭代次數達 T、殘差範數 < ε、或最大相關性 < 閾值。

缺陷: 同一原子可能被重複選擇;係數非正交投影,殘差不保證與已選子空間正交,收斂較慢。

OMP 算法:正交投影保證最優係數

關鍵改進:每輪重新計算所有已選原子的最優係數,使殘差與已選子空間正交。

  1. 選原子同 MP:λₜ = argmaxⱼ |⟨dⱼ, rᵗ⁻¹⟩|。
  2. 擴展索引集 Λᵗ。
  3. 最小二乘求解:xₜ = argmin ‖y - Dₜ x‖₂ = (Dₜᵀ Dₜ)⁻¹ Dₜᵀ y(或 QR 更新避免矩陣求逆)。
  4. 殘差 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 更進一步「正交化」已選子空間——是通往壓縮感知、字典學習、深度網絡剪枝等前沿應用的必經之路。

copyright © 萬盛學電腦網 all rights reserved