0 前情提要

0.1 数学模型和总体框图如下

给定输入信号$\mathbf{X}\in {\mathbb{R}}^{N\times 1}$，最终想要得到压缩信号$\mathbf{A}\in {\mathbb{R}}^{M\times 1}$，$K<<N$

0.2 压缩过程图例分析如下

整个压缩过程也可以被称为感知过程
$$\mathbf{A}=\mathbf{\Phi }\mathbf{X}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{Y}=\mathbf{\Theta }\mathbf{Y}$$

$\mathbf{\Theta }$即为感知过程的核心命名为感知矩阵

符号	含义	维度	属性
$\mathbf{X}$	输入信号；待压缩信号	${\mathbb{R}}^{N\times 1}$	未知，需要恢复
$\mathbf{\Phi }$	观测矩阵；测量矩阵	${\mathbb{R}}^{M\times N}$	已知（非自适应性）
$\mathbf{\Psi }$	变换矩阵；变换基矩阵；稀疏基矩阵；稀疏矩阵；正交基字典矩阵	${\mathbb{R}}^{N\times N}$	已知（非自适应性）
$\mathbf{Y}$	正交基变换后的稀疏表示	${\mathbb{R}}^{N\times 1}$	未知，需要恢复
$\mathbf{\Theta }$	感知矩阵，传感矩阵	${\mathbb{R}}^{M\times N}$	已知（非自适应性）
$\mathbf{A}$	观测压缩所得到压缩信号	${\mathbb{R}}^{M\times 1}$	已知

0.3 算法重构恢复过程如下

在得到已经压缩完的采样信号 $\mathbf{A}$ 后，根据确定的固定性观测矩阵 $\mathbf{\Phi }$ 和稀疏矩阵 $\mathbf{\Psi }$ 的先验信息进行恢复，数学表达如下
$$\check{\mathbf{X}}=f(\mathbf{A},\mathbf{\Theta })$$
给定被压缩的信号 $\mathbf{A}$ 和感知矩阵 $\mathbf{\Theta }$，求解输入原始信号 $\check{\mathbf{X}}$ 的过程称为重构。

重构问题相较于压缩问题来说是一个更加困难的一个任务。

由于$M<<N$， 已知条件所能构成的方程是欠定的，无法轻易求出数值解的，幸运的是，如果原始信号是稀疏的，那么这个问题可以被很好地解决。

解释一下为什么是欠定的：（ $\mathbf{X}$ 满足的约束如下）
$$\begin{gathered} \mathbf{A}=\mathbf{\Psi }\mathbf{X} \\ \left[\begin{array}{c}{a}_1\\ ⋮\\ a_M\end{array}\right]=\left[\begin{array}{cccc}{\psi }_{11}& {\psi }_{12}& ...& {\psi }_{1N}\\ {\psi }_{2N}& {\psi }_{2N}& ...& {\psi }_{2N}\\ ⋮& ⋮& ⋮& ⋮\\ {\psi }_{M1}& {\psi }_{M2}& ...& {\psi }_{MN}\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_N\end{array}\right] \end{gathered}$$
实际使用过程中需要求解出 $N$ 个未知数，但是只有 $M$ 个方程，未知数的个数远远大于方程的个数。

若$N=M$，则可轻松由$\mathbf{A}$解出$\mathbf{X}$和$\mathbf{Y}$

而$M<<N$，可根据稀疏表示下的信号$\mathbf{Y}$和矩阵所具有的RIP性质重构

一般可以抽象为如下求解任务
$$\begin{gathered} \min {\Vert {\mathbf{\Psi }}^T\mathbf{X}\Vert }_0 \\ s.t.\mathbf{\Theta }\mathbf{X}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{X}=\mathbf{A} \end{gathered}$$

1 概述

• 匹配追踪算法（Matching Pursuits，MP）

提出时间：90年代初

国内文献都仅描述了算法步骤和简单的应用，并未对其进行详尽的分析

国外的文献还是分析的很透彻，所以我结合自己的理解，来分析一下写到博客里

2 MP算法

2.0 主要的思路

如果选择与信号最匹配的原子？

如何构建稀疏逼近并求残差？

如何进行迭代？

2.1 算法思想描述

作为对信号进行稀疏分解的方法之一，将信号在完备字典库上进行分解。

假定被表示的信号为 $\mathbf{X}$，其长度为 $N$。假定 $\mathbb{H}$ 表示Hilbert空间，在空间 $\mathbb{H}$ 里，由一组向量 { d 1 , d 2 , . . . , d J } \{\boldsymbol{d}_1,\boldsymbol{d}_2,...,\boldsymbol{d}_J\} {d1​,d2​,...,dJ​} 构成字典矩阵 $\mathbf{D}$，其中每个向量 ${\mathbf{d}}_{\mathbf{i}}$ 可以称为原子（atom），每个原子其长度与被表示信号 $\mathbf{X}$ 的长度 $N$ 相同，而且这些向量已作为归一化处理，即$\Vert {\mathbf{d}}_{\mathbf{i}}\Vert =1$，也就是单位向量长度为1。

MP算法的基本思想：从字典矩阵 $\mathbf{D}$（也称为过完备原子库，过完备字典就是表示字典的原子数量大于信息维度 $J>N$ 中），选择一个与信号 $\mathbf{X}$ 最匹配的原子（也就是某列），构建一个只针对这个列向量有线性表示系数的稀疏逼近，并求出信号残差，然后继续选择与信号残差最匹配的原子，反复迭代，信号 $\mathbf{X}$ 可以由这些原子线性和，同时再加上最后的残差值来表示。很显然，如果残差值在可以忽略的范围内，则信号 $\mathbf{X}$ 就是这些原子的线性组合。

匹配追踪的中心问题是你如何选择信号在字典中最优的若干个展开项。

2.2 分解步骤实现

2.2.1 第一步

计算被压缩的信号 $\mathbf{A}$ 与字典矩阵中每列原子 ${\mathbf{d}}_i$ 的内积，选择绝对值最大的一个原子，它就是过完备字典 $\mathbf{D}$ 中与信号 $\mathbf{A}$ 在本次迭代运算中最匹配的atom。

用数学语言来描述：令信号 $\mathbf{A}\in \mathbb{H}$ ，从字典矩阵 $\mathbf{D}$ 中选择一个最为匹配的原子 ${\mathbf{d}}_i$ ，满足
$$|<\mathbf{A},{\mathbf{d}}_{r_0}>|=su{p}_{i\in (1,..,N)}|<\mathbf{A},{\mathbf{d}}_i>|$$
$su{p}_{i\in (1,..,N)}f(i)$ 表示函数$f(i)$ 的上确界

$r_0$ 表示一个字典矩阵的列索引，是所有列中能得到最大内积的索引，$r_{\ast }$ 下标表示第几次迭代的含义。

这样，信号 $\mathbf{A}$ 就被分解或者理解为被表示为两个部分，即：

第一部分：在最匹配原子 ${\mathbf{d}}_{r_0}$ 的投影分量（${\mathbf{d}}_{r_0}$ 乘上一个线性表示的系数）

第二部分：残差的垂直分量 （$R_1$ 表示第一次的迭代剩余的残差的系数 ，${\mathbf{f}}_1$ 表示第一次迭代剩余的垂直分量）

$$\begin{gathered} \mathbf{A}=<\mathbf{A},{\mathbf{d}}_{r_0}>{\mathbf{d}}_{r_0}+R_1{\mathbf{f}}_1 \\ \text{也可以写作（统一以点的形式）} \\ {R}_0{\mathbf{f}}_0=<R_0{\mathbf{f}}_0,{\mathbf{d}}_{r_0}>{\mathbf{d}}_{r_0}+R_1{\mathbf{f}}_1 \end{gathered}$$

2.2.2 第二步

对残值 $R_1{\mathbf{f}}_1$ 进行第一步同样的分解，那么第 $k$ 步可以得到：
$$R_k{\mathbf{f}}_k=<R_k{\mathbf{f}}_k,{\mathbf{d}}_{r_{k+1}}>{\mathbf{d}}_{r_{k+1}}+R_{k+1}{\mathbf{f}}_{k+1}$$
其中 ${\mathbf{d}}_{r_{k+1}}$ 满足 $|<R_k{\mathbf{f}}_k,{\mathbf{d}}_{r_k+1}>|=su{p}_{i\in (1,..,J)}|<R_k{\mathbf{f}}_k,{\mathbf{d}}_i>|$。可见，经过 $k$ 步分解后，信号 $\mathbf{A}$ 被分解为：
$$\begin{array}{rl}\mathbf{A}& =R_0{\mathbf{f}}_0\\ & =\sum _{n=0}^k<{\mathbf{R}}_n{\mathbf{f}}_n,{\mathbf{d}}_{r_n}>{\mathbf{d}}_{r_n}+R_{k+1}{\mathbf{f}}_{k+1}\end{array}$$

2.3 讨论以及个人想法

2.3.1 讨论1：为什么要假定在Hilbert空间中？

Hilbert空间就是定义了完备的内积空间（可以简单的理解为属于完备内积空间的向量在任意内积操作的情况下，所得结果都属于本内积空间）。很显然，MP中的获得总重要原子的比较计算使用向量的内积运算，所以在 Hilbert空间 中进行信号分解理所当然了。

2.3.2 讨论2：为什么原子要先被归一化处理

即上面的描述 $\Vert {\mathbf{d}}_i\Vert =1$ 。MP中选择最匹配的原子是选择内积最大的一个。也就是信号（或是迭代中残差值）在原子（单位的）投影长度最长的一个，比如第一次分解过程中，投影长度就 $<\mathbf{A},{\mathbf{d}}_{r_0}>$。

内积常用于计算一个矢量在一个方向上的投影长度，这时方向的矢量必须是单位矢量，如果不把所有的原子归一化为相同的模长，会出现前面系数受到模长干扰的问题。

2.3.3 讨论3：为什么这种方法可以实现恢复的效果

从数学公式角度出发讲述为什么能恢复

$$\begin{array}{rl}\mathbf{A}& =\mathbf{D}\mathbf{X}\\ & =[\begin{array}{cccc}{\mathbf{d}}_1& {\mathbf{d}}_2& \cdots & {\mathbf{d}}_N\end{array}]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_N\end{array}\right]\\ & =\left[\begin{array}{cccc}{d}_{11}& d_{12}& ...& d_{1N}\\ ⋮& ⋮& ⋮& ⋮\\ d_{M1}& d_{M2}& ...& d_{MN}\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_N\end{array}\right]\\ \left[\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_M\end{array}\right]& =\left[\begin{array}{c}{d}_{11}\ast x_1+\cdots d_{1i}\ast x_1\cdots +d_{1N}\ast x_N\\ d_{21}\ast x_1+\cdots d_{2i}\ast x_2\cdots +d_{2N}\ast x_N\\ ⋮⋮⋮\\ d_{M1}\ast x_1+\cdots d_{Mi}\ast x_M\cdots +d_{MN}\ast x_N\end{array}\right]\end{array}$$

数学任务：已知 $\mathbf{A}$ 和 $\mathbf{D}$ ，猜测 $\mathbf{X}$

如果说 $\mathbf{A}$ 表示的向量和原子字典的某一个原子有着非常强的相关性，代表在构成这个 $\mathbf{A}$ 的时候原子字典所用来对应表示 ${\mathbf{d}}_i$ 的系数 $x_i$ 比较大，主要都是由 ${\mathbf{d}}_i$ 构成的，具体表现如下
$$\begin{array}{rl}& \\ \left[\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_M\end{array}\right]\cdot {\mathbf{d}}_i& =\left[\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_M\end{array}\right]\cdot \left[\begin{array}{c}{d}_{1i}\\ d_{2i}\\ ⋮\\ d_{Mi}\end{array}\right]\\ & =\left[\begin{array}{c}{d}_{11}\ast x_1+\cdots d_{1i}\ast x_1\cdots +d_{1N}\ast x_N\\ d_{21}\ast x_1+\cdots d_{2i}\ast x_2\cdots +d_{2N}\ast x_N\\ ⋮⋮⋮\\ d_{M1}\ast x_1+\cdots d_{Mi}\ast x_M\cdots +d_{MN}\ast x_N\end{array}\right]\cdot {\mathbf{d}}_i\\ & =\left(\begin{array}{c}{\mathbf{d}}_1\ast x_1+\cdots {\mathbf{d}}_i\ast x_2\cdots +{\mathbf{d}}_N\ast x_N\end{array}\right)\cdot {\mathbf{d}}_i\\ & =x_1{\mathbf{d}}_1\cdot {\mathbf{d}}_i+\cdots x_2{\mathbf{d}}_i\cdot {\mathbf{d}}_i\cdots +x_N{\mathbf{d}}_N\cdot {\mathbf{d}}_i\end{array}$$
很明显字典原子间的点乘取值最大的是 ${\mathbf{d}}_i\cdot {\mathbf{d}}_i$ ，

因为不是正定方程所以不可能完全正交，即为不能保证 $\boldsymbol{d}_j\cdot \boldsymbol{d}_i = 0, i \neq j $，所以只有在$x_i$ 也足够突出的情况下可以在迭代中显示出来，并被MP算法追踪出来。

从向量角度出发讲述为什么能收敛

每次迭代通过公式 $R_k{\mathbf{f}}_k=<R_k{\mathbf{f}}_k,{\mathbf{d}}_{r_{k+1}}>{\mathbf{d}}_{r_{k+1}}+R_{k+1}{\mathbf{f}}_{k+1}$ 可以看出三个向量构成一个三角形，${\mathbf{d}}_{r_{k+1}}$ 与 $R_{k+1}{\mathbf{f}}_{k+1}$ 正交（不能说垂直，但是可以想象二维空间这两个矢量是垂直的）。

这结论可以得出
$${\Vert R_{k}f\Vert }^2={\Vert R_{k+1}f\Vert }^2+\Vert <R_k{\mathbf{f}}_k,{\mathbf{d}}_{r_{k+1}}>{\mathbf{d}}_{r_{k+1}}{\Vert }^2$$
所以得出每一个残值比上一次的小，故而收敛。

2.4 MP算法的缺点

如上所述，信号在迭代过程中产生逐渐变小的残值 $R_k{\mathbf{f}}_k$ ，但是这个残值不能保证满足和已选择的原子是正交的

这会使得每次迭代的结果并不是最优的而是次最优的，收敛需要很多次迭代。数学表示：在第 $k$ 次迭代过程中
$$R_k{\mathbf{f}}_k=<R_k{\mathbf{f}}_k,{\mathbf{d}}_{r_{k+1}}>{\mathbf{d}}_{r_{k+1}}+R_{k+1}{\mathbf{f}}_{k+1}$$
产生的残差 $R_{k+1}{\mathbf{f}}_{k+1}$ ，虽然与 ${\mathbf{d}}_{r_{k+1}}$ 是正交的，但是他与前面的$\boldsymbol{d}{r{0 \sim k}} $不是正交的。

举个例子说明一下：

在二维空间上，有一个信号 $\mathbf{X}$ 被 D = { d 1 , d 2 } \boldsymbol{D}=\{\boldsymbol{d}_1, \boldsymbol{d}_2\} D={d1​,d2​} 来表达，MP算法迭代会发现总是在 ${\mathbf{d}}_1$ 和 ${\mathbf{d}}_2$ 上反复迭代，即
$$\mathbf{A}=x_1{\mathbf{d}}_1+x_2{\mathbf{d}}_2+x_3{\mathbf{d}}_1+x_4{\mathbf{d}}_2\cdots$$
这个就是因为残差值与已选择的原子的非正交性导致的。

再用严谨的方式描述，可能容易理解：在Hilbert空间 $\mathbb{H}$ 中， D = { d 1 , d 2 , ⋯   , d N } \boldsymbol{D} = \{\boldsymbol{d}_1,\boldsymbol{d}_2,\cdots,\boldsymbol{d}_N\} D={d1​,d2​,⋯,dN​} ，$\mathbf{D}\in {\mathbb{R}}^{M\times N}$，定义一个向量 V k = span ⁡ { d r 0 , d r 1 , ⋯   , d r k − 1 } ‾ \boldsymbol{V}_{k}=\overline{\operatorname{span}\left\{\boldsymbol{d}_{r_0}, \boldsymbol{d}_{r_1}, \cdots, \boldsymbol{d}_{r_{k-1}}\right\}} Vk​=span{dr0​​,dr1​​,⋯,drk−1​​}​ ， ${\mathbf{V}}_k$ 就是这些向量的张成中的一个，（在数学中span是扩张空间的意思。就是若干个向量通过线性组合得到的一个向量空间，满足向量空间的所有要求。Span列向量是矩阵中所有的列span成的空间。）

MP迭代到第 $k$ 次的压缩信号 $\mathbf{A}$ 可以表示为：
$$\begin{array}{rl}\mathbf{A}& =R_0{\mathbf{f}}_0\\ & =\sum _{n=0}^k<{\mathbf{R}}_n{\mathbf{f}}_n,{\mathbf{d}}_{r_n}>{\mathbf{d}}_{r_n}+R_{k+1}{\mathbf{f}}_{k+1}\end{array}$$

为了便于表示设置 $\check{{\mathbf{A}}_k}={\sum }_{n=0}^k<{\mathbf{R}}_n{\mathbf{f}}_n,{\mathbf{d}}_{r_n}>{\mathbf{d}}_{r_n}$ ，可以写成如下表达式

$$\begin{array}{rl}\mathbf{A}& =\check{{\mathbf{A}}_k}+R_{k+1}{\mathbf{f}}_{k+1}\end{array}$$

此时 $\check{{\mathbf{A}}_k}$ 是 $k$ 个项的线性表示，MP算法迭代过程中都是保证 ${\mathbf{d}}_{r_k}$ 和 ${\mathbf{f}}_{k+1}$ 正交，但是如果不能保证 $\check{{\mathbf{A}}_k}$ 和 ${\mathbf{f}}_{k+1}$ 正交的话， ${\mathbf{f}}_{k+1}$ 就会含有一些成分分量蕴含于 ${\check{\mathbf{A}}}_k$ ，也就是说会含有 ${\sum }_{n=0}^k<R_n{\mathbf{f}}_n,{\mathbf{d}}_{r_n}>{\mathbf{d}}_{r_n}$ 的分量，会含有 ${\mathbf{d}}_{r_{0\sim k}}$ 的分量，前面的迭代就都不是最优的不能一次性找到最合适的系数表达。

只有当 $\check{{\mathbf{A}}_k}\perp {\mathbf{f}}_{k+1}$ 那么第 $k+1$ 个残值在后面的分解过程中，才不可能出现 $\check{{\mathbf{A}}_k}$ 中已经出现的项，这才是最优的。而一般情况下，不能满足这个条件，MP一般只能满足第 $k+1$ 个残差和 ${\mathbf{d}}_{r_k}$ 正交，也就是残差值在已选择的原子进行垂直投影是非正交性的。

如果第 $k+1$ 个残差 ${\mathbf{f}}_{k+1}$ 和 $\check{{\mathbf{A}}_k}$ 不正交，那么后面的迭代还会出现 $\check{{\mathbf{A}}_k}$ 中已经出现的项，很显然本次得到的残差就不是最优的，这也就是为什么说MP收敛就需要更多次迭代的原因。不是说MP一定得到不到最优解，而且其前面描述的特性导致一般得到不到最优解而是次优解。

LAST、参考文献

正交匹配追踪_给永远比拿愉快-CSDN博客

匹配追踪算法（MP）简介 - 子孑 - 博客园

压缩感知重构算法之正交匹配追踪(OMP)_彬彬有礼的专栏-CSDN博客_omp

MP算法和OMP算法及其思想_逍遥剑客的专栏-CSDN博客_omp算法

压缩感知重构算法之压缩采样匹配追踪(CoSaMP)_彬彬有礼的专栏-CSDN博客

稀疏分解中的MP与OMP算法 - 云+社区 - 腾讯云