匹配追求，是一個將高複雜度的信號以較簡單的訊號來近似的過程，也就是在多維空間中，將高維度的資訊投影到較低維度的生成空間，藉此降低一個信號所需的展開項目。
簡單來說，就是用盡可能少的基元，進行線性組合來逼近原訊號。
一個有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
然而，這個最佳化問題是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
問題三： n = N
結束
基底追求(Basis Pursuit)
有鑑於匹配追求的限制條件以及貪婪演算法在特定情況上造成不適當的基元選擇，S.S.Chen等人於1998年提出的基底追求。若將匹配追求想成，從一個"空"的集合中，在每次迭代中慢慢增加一個基元來構成近似訊號，基底追求則可以想成，從一個完整的基元集合，慢慢減少基元數量。
現假設有一組基元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|。
在此情況下，基底追求對於壓縮感知問題的解法亦能細分為三大問題：
問題1：完全相等
能不能找到最小的||a||_1，使得近似訊號\hat f等於f。
: f(t) = \sum_m a_m b_m(t)
問題2：近似問題
同理，自然界中訊號大多只能以近似方式逼近，因此改為求
: \min_{||a||_1} \int || f(t) - \sum_m a_m b_m(t) || ^2 dt
這個最佳化問題依舊是NP困難，因此可使用基底追求的近似解來求解。
問題3：基底追求
: \min \int || f(t) - \sum_m a_m b_m(t) || ^2 dt \text{ , such that } ||a||_1 \leq N
相關型態
Three-Parameter Atoms
:f(t) \approx \hat f(t) = \sum a_{t_0,f_0,\sigma} \varphi_{t_0,f_0,\sigma}(t)
: where \varphi_{t_0,f_0,\sigma}(t) = \frac{2^{1/4}}{\sigma^{1/2}} e^{j2\pi f_0 t- \frac{\pi (t-t_0)^2}{\sigma^2} }
近似訊號\hat f是N = 3的特例，由三個基元組合而成，每個基元由t_0 決定在時間軸上的中心位置，f_0決定在頻率軸上的中心位置，以及由\sigma選擇縮放尺度的大小。
由於\varphi_{t_0,f_0,\sigma} 是非正交集合，a_{t_0, f_0, \sigma} 需要透過匹配追求來求得。
Four-Parameter Atoms(Chirplet)
:f(t) \approx \hat f(t) = \sum a_{t_0,f_0, \sigma, \eta}\cdot \varphi_{t_0, f_0, \sigma, \eta}(t)
: where \varphi_{t_0, f_0, \sigma, \eta}(t) = \frac{2^{1/4}}{\sigma^{1/2}}e^{j2\pi(f_0t + \frac{\eta}{2t^2})- \frac{\pi (t-t_0)^2}{\sigma^2} }
近似訊號\hat f是N = 4的特例，由四個基元組合而成，每個基元由t_0 決定在時間軸上的中心位置，f_0決定在頻率軸上的中心位置，以及\sigma選擇縮放尺度的大小和\eta控制啁啾率。
同理，由於\varphi_{t_0,f_0,\sigma, \eta} 是非正交集合，a_{t_0, f_0, \sigma, \eta} 需要透過匹配追求來求得。
參考資料
- Jian-Jiun Ding, Time frequency analysis and wavelet transform class note, Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2017.
外部連結
评论 (0)