匹配追踪

为了找到最符合原讯号的一组原子加权总合，如果对原子库进行所有组合的尝试过于耗费时间。在1993年由Mallat S和Zhang Z的论文[1]中，提出了一个贪婪算法（Greedy Algorithm），并大幅降低找出近似解的时间。其作法首先在原子库中寻找与原讯号内积结果最大的原子${\displaystyle g_{\gamma _{n}}}$ ，找到此讯号以及其内积结果${\displaystyle a_{n}}$ 之后再将原讯号减掉${\displaystyle a_{n}g_{\gamma _{n}}}$ 作为下一次重复运算的原始讯号，如此反复做下去即可得到一系列的${\displaystyle a_{n}}$ 以及原子${\displaystyle g_{\gamma _{n}}}$ ，直到达到停止条件为止，其详细的算法如下：

输入：Signal: ${\displaystyle f(t)}$ , dictionary ${\displaystyle D}$ .

输出：List of coefficients: ${\displaystyle \left(a_{n},g_{\gamma _{n}}\right)}$ .

初始化：

${\displaystyle R_{1}\,\leftarrow \,f(t)}$ ;

${\displaystyle n\,\leftarrow \,1}$ ;

重复：

寻找 ${\displaystyle g_{\gamma _{n}}\in D}$  具有最大内积 ${\displaystyle |\langle R_{n},g_{\gamma _{n}}\rangle |}$ ;

${\displaystyle a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle }$ ;

${\displaystyle R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}}$ ;

${\displaystyle n\,\leftarrow \,n+1}$ ;

直到达到停止条件（例如：${\displaystyle \|R_{n}\|<threshold}$ ）

在信号处理的许多应用中，需要将信号分解为一群在时域和频域都具有良好局部性(集中在某一范围)的函数，这些函数称为时频原子(time-frequency atom)。

选择不同的时频原子时，分解方式的特性会有很大的差异。窗函数傅立叶转换(window Fourier transform)和小波转换(wavelet transform)都是时频信号分解的方法。

通常一个时频原子群可以由单一的窗函数${\displaystyle g(t)\in L^{2}(R)}$ 经过scale、translation和modulation产生，令${\displaystyle g(t)\in O({\frac {1}{t^{2}+1}})}$ 为一个实数的连续可微函数，且限制${\displaystyle \|g\|=1}$ 、${\displaystyle g(t)}$ 的积分不为零、${\displaystyle g(0)\neq 0}$ 。

以${\displaystyle \gamma =(s,u,\xi )}$ 表示scale参数${\displaystyle s(s>0)}$ 、translation参数${\displaystyle u}$ 和modulation参数${\displaystyle \xi }$ ，定义${\displaystyle g_{\gamma }(t)}$ 为

${\displaystyle g_{\gamma }(t)={\frac {1}{\sqrt {s}}}g({\frac {t-u}{s}})e^{i\xi t}}$ 

其中${\displaystyle \gamma }$ 是集合${\displaystyle \Gamma =R^{+}\times R^{2}}$ 中的元素，${\displaystyle {\frac {1}{\sqrt {s}}}}$ 使得${\displaystyle \|g\|=1}$ 。

事实上，函数群${\displaystyle D={(g_{\gamma }(t))}_{\gamma \in \Gamma }}$ 含有许多冗余的元素，对于任何函数${\displaystyle f(t)}$ ，更有效率的表示方法是，在原子${\displaystyle {(g_{\gamma _{n}}(t))}_{n\in N}}$ 中，只选取适当数量的子集合，其中${\displaystyle \gamma _{n}=(s_{n},u_{n},\xi _{n})}$ ，则${\displaystyle f(t)}$ 可以表示为

${\displaystyle f(t)=\sum _{n=-\infty }^{+\infty }a_{n}g_{\gamma _{n}}(t)}$ 

在窗函数傅立叶转换中，所有原子${\displaystyle g_{\gamma _{n}}}$ 具有相同的scale参数${\displaystyle s_{n}=s_{0}}$ ，因此主要分布在一个大小为${\displaystyle s_{0}}$ 倍数的区间内，由于上述特性，窗函数傅立叶转换无法准确地描述比${\displaystyle s_{0}}$ 大许多或小许多的函数结构。

小波转换将信号分解为不同尺度的时频原子，称为小波(wavelet)，小波群${\displaystyle {(g_{\gamma _{n}}(t))}_{n\in N}}$ 的建构方法是令${\displaystyle \xi _{n}=\xi _{0}/s_{n}}$  ，其中${\displaystyle \xi _{0}}$ 是一个常数。小波转换可以分析不同尺寸的信号成分，然而，受限于参数${\displaystyle \xi _{n}}$ 和${\displaystyle s_{n}}$ 必须成反比的条件，小波转换的系数无法精准估计傅立叶转换后具有良好局部性的频率成分。

自适应时频分解(adaptive time-frequency decomposition)的目的是将信号展开到一组波形(waveform)上，这些波形选自一个数量庞大的冗余字典，而匹配追踪是能达到自适应分解的一种方法。

一个希尔伯特空间可表示为${\displaystyle L^{2}(R)}$ ，其组成的复数函数${\displaystyle f}$ 必须满足

${\displaystyle \|f\|=\int _{-\infty }^{+\infty }{|f(t)|}^{2}dt<+\infty }$ 

令${\displaystyle H}$ 代表一个希尔伯特空间，则将“字典”定义为${\displaystyle H}$ 中的一个向量群${\displaystyle D={(g_{\gamma })}_{\gamma \in \Gamma }}$ ，满足${\displaystyle \|g_{\gamma }\|=1}$ ，其中${\displaystyle \gamma }$ 是集合${\displaystyle \Gamma =R^{+}\times R^{2}}$ 中的元素。${\displaystyle V}$ 代表字典向量的封闭线性生成空间(closed linear span)，在空间${\displaystyle V}$ 中，集合${\displaystyle D}$ 之向量的有限线性展开(finite linear expansion)是稠密(dense)的，如果${\displaystyle V=H}$ ，则称此字典具有完备性(completeness)。对于“时频原子分解”段落所描述的字典，${\displaystyle H=L^{2}(R)}$ ，在空间${\displaystyle L^{2}(R)}$ 中，时频分子的有限线性展开是稠密的，因此该字典具有完备性。

假设有一信号${\displaystyle f\in H}$ ，欲将其线性展开到由集合${\displaystyle D}$ 中选出的一组向量上，使得结果最匹配原来的信号结构。匹配追踪的方法是连续地将${\displaystyle f}$ 以其在集合${\displaystyle D}$ 中元素的正交投影(orthogonal projection)近似。

令${\displaystyle g_{\gamma _{0}}\in D}$ ，向量${\displaystyle f}$ 可以被分解为

${\displaystyle f=\langle f,g_{\gamma _{0}}\rangle g_{\gamma _{0}}+Rf}$ 

其中${\displaystyle Rf}$ 是将${\displaystyle f}$ 以${\displaystyle g_{\gamma _{0}}}$ 的方向近似后的剩余向量(residual vector)，由于${\displaystyle g_{\gamma _{0}}}$ 和${\displaystyle Rf}$ 正交，可得下式

${\displaystyle {\|f\|}^{2}={|\langle f,g_{\gamma _{0}}\rangle |}^{2}+{\|Rf\|}^{2}}$ 

为了最小化${\displaystyle \|Rf\|}$ ，必须选取${\displaystyle g_{\gamma _{0}}\in D}$ 使得${\displaystyle |\langle f,g_{\gamma _{0}}\rangle |}$ 最大化。在某些情况下，只能找到近似最佳的向量${\displaystyle g_{\gamma _{0}}}$ ，符合

${\displaystyle |\langle f,g_{\gamma _{0}}\rangle |\geq \alpha \ {\underset {\gamma \in \Gamma }{\sup }}|\langle f,g_{\gamma }\rangle |}$ 

其中${\displaystyle 0<\alpha \leq 1}$ ，在选择向量${\displaystyle g_{\gamma _{0}}}$ 时，并非随机选择，而是由一个选择函数${\displaystyle C}$ 决定。

重复上述步骤，迭代地将剩余向量${\displaystyle Rf}$ 投影到集合${\displaystyle D}$ 中最匹配${\displaystyle Rf}$ 的向量，并将${\displaystyle Rf}$ 分解。

匹配追踪的步骤可以由数学归纳法来表示

1. 令${\displaystyle R^{0}f=f}$ 
2. 假设已经计算第${\displaystyle n}$ 次的剩余向量${\displaystyle R^{n}f}$ ，${\displaystyle n\geq 0}$ 
3. 根据选择函数${\displaystyle C}$ ，选取一个最匹配${\displaystyle R^{n}f}$ 的元素${\displaystyle g_{\gamma _{n}}\in D}$ 

${\displaystyle |\langle R^{n}f,g_{\gamma _{n}}\rangle |\geq \alpha \ {\underset {\gamma \in \Gamma }{\sup }}|\langle R^{n}f,g_{\gamma }\rangle |}$ 

剩余向量${\displaystyle R^{n}f}$ 被分解为

${\displaystyle R^{n}f=\langle R^{n}f,g_{\gamma _{n}}\rangle g_{\gamma _{n}}+R^{n+1}f}$ 

由于${\displaystyle g_{\gamma _{n}}}$ 和${\displaystyle R^{n+1}f}$ 正交，可得下式

${\displaystyle {\|R^{n}f\|}^{2}={|\langle R^{n}f,g_{\gamma _{n}}\rangle |}^{2}+{\|R^{n+1}f\|}^{2}}$ 

当分解到第${\displaystyle m}$ 次时，${\displaystyle f}$ 被分解为

${\displaystyle {\begin{aligned}f&=\sum _{n=0}^{m-1}(R^{n}f-R^{n+1}f)+R^{m}f\\&=\sum _{n=0}^{m-1}\langle R^{n}f,g_{\gamma _{n}}\rangle g_{\gamma _{n}}+R^{m}f\\\end{aligned}}}$ 

${\displaystyle {\|f\|}^{2}}$ 被分解为

${\displaystyle {\begin{aligned}{\|f\|}^{2}&=\sum _{n=0}^{m-1}({\|R^{n}f\|}^{2}-{\|R^{n+1}f\|}^{2})+{\|R^{m}f\|}^{2}\\&=\sum _{n=0}^{m-1}{|\langle R^{n}f,g_{\gamma _{n}}\rangle |}^{2}+{\|R^{m}f\|}^{2}\\\end{aligned}}}$ 

此公式具有能量守恒的意义，原来的向量${\displaystyle f}$ 被分解为许多字典中元素的总和。

当信号存在的空间${\displaystyle H}$ 具有有限的维度${\displaystyle N}$ 时，匹配追踪方法会有特殊的特性。在字典${\displaystyle D}$ 中，可能含有无限多的元素，假设此字典具有完备性，此时可以用一种有效率的匹配追踪方法，剩余向量的范数(norm)会以指数方式下降。

当字典含有非常多冗余的元素时，要寻找和剩余向量最匹配的向量，通常可以只限制在一个子字典${\displaystyle D_{\alpha }={(g_{\gamma })}_{\gamma \in {\Gamma _{\alpha }}}\subset D}$ 中寻找，假设${\displaystyle \Gamma _{\alpha }}$ 是一个包含于${\displaystyle \Gamma }$ 的有限索引集，使得对于所有信号${\displaystyle f\in H}$ ，满足

${\displaystyle {\underset {\gamma \in \Gamma _{\alpha }}{\sup }}|\langle f,g_{\gamma }\rangle |\geq \alpha \ {\underset {\gamma \in \Gamma }{\sup }}|\langle f,g_{\gamma }\rangle |}$ 

依据${\displaystyle \Gamma _{\alpha }}$ 的大小和字典${\displaystyle D}$ 的冗余程度，集合${\displaystyle \Gamma _{\alpha }}$ 可以比${\displaystyle \Gamma }$ 小许多。

以数学归纳法表示此处的匹配追踪方法

1. 计算内积${\displaystyle {(\langle f,g_{\gamma }\rangle )}_{\gamma \in \Gamma _{\alpha }}}$ 
2. 假设已经计算${\displaystyle {(\langle R^{n}f,g_{\gamma }\rangle )}_{\gamma \in \Gamma _{\alpha }}}$ ，${\displaystyle n\geq 0}$ 
3. 从子字典${\displaystyle D_{\alpha }}$ 中找出一个元素${\displaystyle g_{\tilde {\gamma _{n}}}}$ ，使得

${\displaystyle |\langle R^{n}f,g_{\tilde {\gamma _{n}}}\rangle |={\underset {\gamma \in \Gamma _{\alpha }}{\sup }}|\langle R^{n}f,g_{\gamma }\rangle |}$ 

为了从字典中找到一个比${\displaystyle g_{\tilde {\gamma _{n}}}}$ 更匹配${\displaystyle f}$ 的元素，可以利用牛顿法(Newton’s method)，在${\displaystyle \Gamma }$ 中寻找${\displaystyle {\tilde {\gamma _{n}}}}$ 的邻近索引${\displaystyle \gamma _{n}}$ ，使得内积达到局部最大值，在此情况下，可以得出下式

${\displaystyle |\langle R^{n}f,g_{\gamma _{n}}\rangle |\geq |\langle R^{n}f,g_{\tilde {\gamma _{n}}}\rangle |\geq \alpha \ {\underset {\gamma \in \Gamma }{\sup }}|\langle R^{n}f,g_{\gamma }\rangle |}$ 

在此处，选择函数${\displaystyle C}$ 与希尔伯特空间中的匹配追踪不同，必须进行二次搜寻。

在选出一个${\displaystyle g_{\tilde {\gamma _{n}}}}$ 后，必须计算新的剩余向量${\displaystyle R^{n+1}f}$ 和任何${\displaystyle g_{\gamma }\in D_{\alpha }}$ 的内积，更新公式如下

${\displaystyle \langle R^{n+1}f,g_{\gamma }\rangle =\langle R^{n}f,g_{\gamma }\rangle -\langle R^{n}f,g_{\gamma _{n}}\rangle \langle g_{\gamma _{n}},g_{\gamma }\rangle }$ 

由于先前的计算已经得到${\displaystyle \langle R^{n}f,g_{\gamma }\rangle }$ 和${\displaystyle \langle R^{n}f,g_{\gamma _{n}}\rangle }$ ，因此上式的更新只需要计算${\displaystyle \langle g_{\gamma _{n}},g_{\gamma }\rangle }$ 。

对于一个给定的信号${\displaystyle f}$ ，要对其剩余向量分解多少次，决定于要求的精准度${\displaystyle \epsilon }$ ，重复的次数为能够满足下式的最小值${\displaystyle p}$ 

${\displaystyle \|R^{p}f\|=\|f-\sum _{n=0}^{p-1}\langle R^{n}f,g_{\gamma _{n}}\rangle g_{\gamma _{n}}\|\leq \epsilon \|f\|}$ 

根据能量守恒，此公式等价于

${\displaystyle \|f\|-\sum _{n=0}^{p-1}{|\langle R^{n}f,g_{\gamma _{n}}\rangle |}^{2}\leq \epsilon ^{2}\|f\|}$ 

由于在此方法中，每一次重复计算时，并没有计算剩余向量${\displaystyle R^{n}f}$ ，因此只根据上式来判断是否达到停止分解的条件。

重复次数${\displaystyle p}$ 决定于${\displaystyle \|R^{n}f\|}$ 的下降速率，依据信号的不同，${\displaystyle p}$ 可以有很大的变化，但在一般情况下，${\displaystyle p}$ 会比空间${\displaystyle H}$ 的维度${\displaystyle N}$ 小很多。

• 任何讯号${\displaystyle f}$ 都会在由原子库所张的空间中找到收敛的解。
• 稀疏性：当原子库很大的时候，MP算法找出来的最佳吻合解，其中的大部分原子讯号的系数可能都是0，只有少部分的系数不为0，此性质称为稀疏代表性，而此特性对于影像或视讯编码和压缩很有帮助。

匹配追踪算法的灵活性和效率在讯号处理领域中越来越重要，尤其在以下几种领域中更有其重要的应用：

在视讯编码和影像压缩上，对于运动的影像估计和补偿，在提出新的原子库或是扩展的算法之后，有相当的改良。在影像辨识和形状辨认上，匹配追踪算法的稀疏性对于同样具有稀疏性的图像提供新的研究方向。另外在音乐、语音方面，最早即在时频分析上作为MP算法研究对象。

压缩感知

[1] S. G. Mallat and Z. Zhang, "Matching pursuits with time-frequency dictionaries," in IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3397-3415, Dec 1993.

[2] Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2012.

[3] B. Torresani, "Wavelets associated with representations of the affine Weyl-Heisenberg group," 1. Math. Physics, vol. 32, pp. 1273-1279, May 1991.