匹配追踪

匹配追踪（MP）是一种稀疏的近似算法，它可以找到多维数据在超完整（即冗余）字典D {displaystyle D}上的最佳匹配投影。其基本思想是将希尔伯特空间H {{displaystyle H}中的信号f {{displaystyle f}近似为有限多个函数g γ n {{displaystyle g_{gamma _{n}}的加权和（称为原子），取自D {{displaystyle D}。

其中g γ n {displaystyle g_{gamma _{n}}是矩阵D {displaystyle D}的γ n {displaystyle γgamma _{n}列，a n {displaystyle a_{n}是原子g γ n {displaystyle g_{gamma _{n}}的标量加权系数（振幅）。通常情况下，D {{displaystyle D}中的每个原子都不会被用于这个和。相反，为了xxx限度地（贪婪地）减少近似误差，匹配追寻法一次选择一个原子。这是通过寻找与信号有最高内积的原子来实现的（假设原子是归一化的），从信号中减去只使用这一个原子的近似，并重复这个过程，直到信号被满意地分解，即残差的准则很小

如果R n {{displaystyle R_{n}}迅速收敛到零，那么只需要几个原子就可以得到对f {{displaystyle f}的良好近似。这样的稀疏表示对于信号编码和压缩是可取的。

其中 "x‖0 {displaystyle |x|_{0}}是L 0 {displaystyle L_{0}}的伪规范（即x的非零元素的数量 {displaystyle x} ）。在前面的符号中，x {displaystyle x}的非零项是x γ n = a n {{displaystyle x_{gamma _{n}}=a_{n}}。.准确解决稀疏性问题是NP-hard，这就是为什么使用MP这样的近似方法。

作为比较，考虑一下信号的傅里叶变换表示--这可以用上面给出的术语来描述，其中字典是由正弦波基函数（最小的完整字典）建立的。傅里叶分析在信号处理中的主要缺点是，它只提取信号的全局特征，不适应被分析的信号f { {displaystyle f}。通过采取极度冗余的字典，我们可以在其中寻找与信号f {displaystyle f}最匹配的原子（函数）。

如果D {displaystyle D}包含大量的向量，寻找f {displaystyle f}的最稀疏表示，对于实际应用来说，在计算上是不可接受的。对于任何信号f {displaystyle f}和任何字典D {displaystyle D}，算法都会迭代生成。对于任何信号f {displaystyle f}和任何字典D {displaystyle D}，该算法迭代生成一个原子指数和加权标量的排序列表，这构成了稀疏信号表示问题的次优解。

• ←表示分配。例如，maximum ← item表示maximum的值变为item的值。
• return终止算法并输出以下值。

在信号处理中，匹配追求的概念与统计投影追求有关，在这种情况下，有趣的投影被发现；那些偏离正常分布较多的投影是共同的。