匹配追踪

匹配追踪(matching pursuit, MP)最早是时频分析的分析工具，目的是要将一已知讯号拆解成由许多被称作为原子讯号的加权总和，而且企图找到与原来讯号最接近的解。其中原子讯号为一极大的原子库中的元素。以数学式子表示可以得到：

其中，${\displaystyle a_n}$是权重，${\displaystyle g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_n}}$是由字典${\displaystyle D}$中获得的原子讯号。

如同傅立叶级数将一讯号拆解成一系列的正弦波的相加，其中每个成分拥有不同的系数作为权重，其数学式子如下：

而匹配追踪也具有将讯号拆解成一系列原子相加的意涵，甚至可以使用匹配追踪去描述傅立叶级数，也就是原子库对应到的所有正弦函数的集合。

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

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

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

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

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

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

其中${\displaystyle \mathrm{\gamma <!--\; \gamma \; -->}}$是集合${\displaystyle \mathrm{\Gamma <!--\; \Gamma \; -->}=R^{+}\times <!--\; \times \; -->R^2}$中的元素，${\displaystyle \frac{1}{\sqrt{s}}}$使得${\displaystyle \Vert <!--\; \Vert \; -->g\Vert <!--\; \Vert \; -->=1}$。

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

${\displaystyle f(t)=\underset{n=-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{a}_n{g}_{{\mathrm{\gamma <!--\; \gamma \; -->}}_n}(t)}$

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

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

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

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

令${\displaystyle H}$代表一个希尔伯特空间，则将“字典”定义为${\displaystyle H}$中的一个向量群${\displaystyle D={(g_{\mathrm{\gamma <!--\; \gamma \; -->}})}_{\mathrm{\gamma <!--\; \gamma \; -->}\in <!--\; \in \; -->\mathrm{\Gamma <!--\; \Gamma \; -->}}}$，满足${\displaystyle \Vert <!--\; \Vert \; -->g_{\mathrm{\gamma <!--\; \gamma \; -->}}\Vert <!--\; \Vert \; -->=1}$，其中${\displaystyle \mathrm{\gamma <!--\; \gamma \; -->}}$是集合${\displaystyle \mathrm{\Gamma <!--\; \Gamma \; -->}=R^{+}\times <!--\; \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 <!--\; \in \; -->H}$，欲将其线性展开到由集合${\displaystyle D}$中选出的一组向量上，使得结果最匹配原来的信号结构。匹配追踪的方法是连续地将${\displaystyle f}$以其在集合${\displaystyle D}$中元素的正交投影(orthogonal projection)近似。

令${\displaystyle g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}\in <!--\; \in \; -->D}$，向量${\displaystyle f}$可以被分解为

${\displaystyle f=⟨<!--\; ⟨\; -->f,g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}⟩<!--\; ⟩\; -->g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}+Rf}$

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

${\displaystyle {\Vert <!--\; \Vert \; -->f\Vert <!--\; \Vert \; -->}^2={|⟨<!--\; ⟨\; -->f,g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}⟩<!--\; ⟩\; -->|}^2+{\Vert <!--\; \Vert \; -->Rf\Vert <!--\; \Vert \; -->}^2}$

为了最小化${\displaystyle \Vert <!--\; \Vert \; -->Rf\Vert <!--\; \Vert \; -->}$，必须选取${\displaystyle g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}\in <!--\; \in \; -->D}$使得${\displaystyle |⟨<!--\; ⟨\; -->f,g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}⟩<!--\; ⟩\; -->|}$最大化。在某些情况下，只能找到近似最佳的向量${\displaystyle g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}}$，符合

${\displaystyle |⟨<!--\; ⟨\; -->f,g_{{\mathrm{\gamma <!--\; \gamma \; -->}}_0}⟩<!--\; ⟩\; -->|\ge <!--\; \ge \; -->\mathrm{\alpha <!--\; \alpha \; -->}\underset{\mathrm{\gamma <!--\; \gamma \; -->}\in <!--\; \in \; -->\mathrm{\Gamma <!--\; \Gamma \; -->}}{sup}|⟨<!--\; ⟨\; -->f,g_{\mathrm{\gamma <!--\; \gamma \; -->}}⟩<!--\; ⟩\; -->|}$