匹配追求過程

匹配追求，是一個將高複雜度的信號以較簡單的訊號來近似的過程，也就是在多維空間中，將高維度的資訊投影到較低維度的生成空間，藉此降低一個信號所需的展開項目。

簡單來說，就是用盡可能少的基元，進行線性組合來逼近原訊號。

一個有N個基元的近似訊號為

f(t)\approx {\hat {f}}_{N}(t)=\sum _{n=1}^{N}a_{n}b_{n}(t)

其 $a_{n}$ 為各基元的權重。而與原訊號 $f$ 的近似誤差為 $R$ ，表示為

R=f(t)-{\hat {f}}(t)

匹配追求並不會賦予子空間 $D$ 的每個基元一個權重 $a_{n}$ ，意即有些基底會捨棄不用，藉此降低所需空間，相反的，匹配追求會基於貪婪演算法，盡可能的用較少的基元，來降低誤差 $R$ 。核心思想為自子空間 $D$ 中選擇一個和訊號 $f$ 內積值最大的基元 $b_{i}$ ，將基元乘上適當的權重 $a_{i}$ 並從原訊號中減去，接著再次進行以上二步驟。以此往復實行運算，直到原訊號被解析，也就是近似誤差 $R$ 趨近於0。

壓縮感知

現假設有一組基元 $b_{0}(t),b_{1}(t),b_{2}(t),b_{3}(t)......b_{N}(t)$ 源自於字典 $D$ ，這組 $b_{n}(t)$ 組成一個過完備性(Over-complete)、非正交集合。

壓縮感知的問題在此即為：

問題1：完全相等

能不能找到最小的 $||a||_{0}$ ( $a_{k}$ 不為0的個數， $\forall k=\{1,2,...,N\}$ )，使得近似訊號 ${\hat {f}}$ 等於 $f$ 。

f(t)=\sum _{m}a_{m}b_{m}(t)

問題2：近似問題

很明顯的，自然界中訊號大多只能以近似方式逼近，因此改為求

\min _{||a||_{0}}\int ||f(t)-\sum _{m}a_{m}b_{m}(t)||^{2}dt<threshold

然而，這個最佳化問題是NP困難，無法在線性多項式時間內找到解答，因此使用匹配追求的近似解來求解。

問題3：匹配追求

\min \int ||f(t)-\sum _{m}a_{m}b_{m}(t)||^{2}dt{\text{ , such that }}||a||_{0}\leq N

演算法

匹配追求(貪婪演算法)

 輸入： 原訊號  $f(t)$ 
 輸出： 所需權重  $a_{n}$  與其對應的基元  $b_{n}$ 
 初始化：
    $n\leftarrow 0$ 
    ${\hat {f}}(t)\leftarrow f(t)$ 
 反覆：
   尋找  $m$  使得內積  $\int {\hat {f}}(t)b_{m}^{*}(t)dt$  最大
   令  $\phi _{n}(t)\leftarrow b_{m}(t)$ 
   令  $\mu _{n}\leftarrow \int {\hat {f}}(t)b_{m}^{*}(t)dt$ 
    ${\hat {f}}(t)\leftarrow {\hat {f}}(t)-\mu _{n}\phi _{n}(t)$ 
    $n\leftarrow n+1$ 
 直到中止條件發生：
   問題一：   ${\hat {f}}(t)=0$ 
   問題二：   $\int {\hat {f}}(t)^{2}(t)dt<threshold$ 
   問題三：   $n=N$ 
 結束

基底追求(Basis Pursuit)

有鑑於匹配追求的限制條件以及貪婪演算法在特定情況上造成不適當的基元選擇，S.S.Chen等人於1998年提出的基底追求。^[1]若將匹配追求想成，從一個"空"的集合中，在每次迭代中慢慢增加一個基元來構成近似訊號，基底追求則可以想成，從一個完整的基元集合，慢慢減少基元數量。

現假設有一組基元 $b_{0}(t),b_{1}(t),b_{2}(t),b_{3}(t)......b_{N}(t)$ 源自於字典 $D$ ，這組 $b_{n}(t)$ 組成一個過完備性(Over-complete)、非正交集合。不同於匹配追求，將原先所求的0級範數( $||a||_{0}$ )，改為求其絕對值 $||a||_{1}=|a_{0}|+|a_{1}|+|a_{2}|+|a_{3}|+......+|a_{N}|$ 。

在此情況下，基底追求對於壓縮感知問題的解法亦能細分為三大問題：