匹配追求过程

匹配追求，是一个将高复杂度的信号以较简单的讯号来近似的过程，也就是在多维空间中，将高维度的资讯投影到较低维度的生成空间，借此降低一个信号所需的展开项目。

简单来说，就是用尽可能少的基元，进行线性组合来逼近原讯号。

一个有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}|$ 。

在此情况下，基底追求对于压缩感知问题的解法亦能细分为三大问题：