信号处理-稀疏分解：MP, OMP and BP

本文主要介绍了稀疏分解的基本概念，匹配追踪（MP），正交匹配追踪（OMP）和基追踪（BP）的原理和算法流程。

[[2021-03-19稀疏分解.pdf]]

稀疏分解的基本概念

稀疏分解，又称为稀疏近似、稀疏表示（Sparse Decomposition / Sparse Approximation / Sparse Representation of Signals）

假定信号为$f$，其长度为$n$，Hilbert空间记为$H$，在希尔伯特空间$H$里，由一组向量${x_1, x_2, ⋯, x_m}$构成字典矩阵$D$，其中每个列向量为一个原子，其长度与被表示的信号$f$的长度相同，并且这些向量已经经过归一化处理，即每一个列向量都是单位向量，其模长为 1.

如果字典的原子张成了整个信号空间，那么字典就是完全的。如果有原子之间线性相关，那么字典就是冗余的。在大多数稀疏分解的应用中，字典都是完全且冗余的。

用数学语言表示为：$|x_i| = 1, 1 ≤ i ≤ m$，

信号可以被表示成为这些原子的稀疏表示，也就是信号  f  可以被表示为$f = Dβ$，或者是$f ≈ Dβ, ∥f − Dβ∥p ≤ ε$。

字典矩阵中所谓的过完备性（有时也称作冗余，over-complete/redundant），指的是原子的个数远远大于信号的长度，即为：$n ≪ m$.

信号的稀疏分解，也就是需要求出$β$。由于字典矩阵是冗余的，原子之间存在相关关系，所以信号的稀疏表示不唯一，问题的关键在于如何找到一个最优表示（Optimal Representation）。最直观的方式就是找到一个内积最大的表示，这也就是后面说到的匹配追踪的思想。

匹配追踪（Matching Pursuit）

匹配追踪概述

匹配追踪是对信号进行稀疏分解的经典方法，它将信号在完备字典库上进行分解。

MP 算法的基本思想是：从字典矩阵$D$（也称为过完备字典库）里选择一个与信号$f$最为匹配的原子，也就是选择某一个列向量，构建一个稀疏近似，并求出信号的残差，然后继续选择与信号残差最匹配的原子，反复迭代该过程，直至达到终止条件。最终信号$f$便可以由选择的这些原子表示出来(由于选择的字典矩阵是完备的，其中的某一个原子可能可以由其他的原子线性表示出来，所以这个表示不一定的线性的。)有以下几个问题需要回答：

• （1）如何选择与信号$f$最为匹配的原子呢？
• （2）如何构建稀疏近似并求出残差呢？
• （3）如何进行迭代呢？

（1）计算信号f与字典矩阵$D$里的每一个原子的内积（也就是和字典矩阵的每一列作内积），内积绝对值最大的一个原子即为本次迭代中与信号$f$最为匹配的原子。 用数学语言描述就是：

$$
f ∈ H, R_0f = f |⟨f, x_{r_0}⟩| = sup_{i ∈ {1, ⋯, k}}|⟨f, x_{r_i}⟩|
$$

$r_i$表示字典矩阵$D$的列索引。

(2) 这样，信号$f$就可以被分解为在最匹配原子$x_{r_0}$的投影分量和残差两部分：

$$
R_nf=\langle R_jf,x_{r_j} \rangle x_{r_j} + R_{j+1}f \tag{1}
$$

在这里的残差和投影分量之间是正交的：$⟨R_{j + 1}f, x_{r_j}⟩ = 0$（类似于欧几里得空间的垂直投影的效果，Hilbert空间是欧氏空间的推广）。

(3) 对残差$R_1f$进行上述分解，经过$j$次迭代之后，信号可以表示为:

$$
f=\sum_{n=0}^{j-1}\langle R_nf,x_{r_n} \rangle x_{r_n} + R_jf \tag{2}
$$

匹配追踪算法（English）

Matching pursuit is a greedy algorithm that computes the best nonlinear approximation to a signal in a complete, redundant dictionary. Matching pursuit builds a sequence of sparse approximations to the signal stepwise. Let $D = {x_{r_i}}_{i = 1}^m$ denote a dictionary of unit-norm atoms. Let $f$be your signal.

• Start by defining $R_0f = f$
• Begin the matching pursuit by selecting the atom from the dictionary that maximizes the absolute value of the inner product with $R_0f = f$. Denote that atom by $x_{r_0}$.
• Form the residual $R_1f$ by subtracting the orthogonal projection of R0f onto the space spanned by $x_{r_0}$.

$$
R_1f = R_0f − ⟨R_0f, x_{r_0}⟩x_{r_0}
$$

• Iterate by repeating steps 2 and 3 on the residual.

$$
R_{j+1}f=R_jf−\langle R_jf,x_{r_j} \rangle x_{r_j}
$$

• Stop the algorithm when you reach some specified stopping criterion. In nonorthogonal (or basic) matching pursuit, the dictionary atoms are not mutually orthogonal vectors. Therefore, subtracting subsequent residuals from the previous one can introduce components that are not orthogonal to the span of previously included atoms.

匹配追踪收敛性证明

The proof of convergence of MP relies essentially on the fact that:

$$
\langle R_{j+1}f,x_{r_j} \rangle = 0
$$

Together with $(2)$, this orthogonality of the residual to the last vector selected leads to the following “energy conservation” equation:

$$
|R_jf|^2 = |R_{j+1}f|^2 + 2\langle R_jf, x_{r_j} \rangle \langle R_{j+1}f, x_{r_j} \rangle + |\langle R_jf, x_{r_j} \rangle |^2 |x_{r_j}|^2
$$

And with $|x_{r_j}|^2 = 1$, we get:

$$
|R_jf|^2 = |R_{j+1}f|^2 + |\langle R_jf, x_{r_j} \rangle |^2
$$

It has been noted that MP algorithm may be derived as a special case of a technique known as Projection Pursuit in the statistics literature.

正交匹配追踪（Orthogonal Matching Pursuit）

正交匹配追踪概述

OMP 算法对 MP 的改进之处在于：在分解的每一步，对所选择的原子全部进行正交化处理，这使得精度要求相同的条件下，OMP 算法的收敛速度更快。

OMP 算法分解的每一步，残差与所有选择的原子正交，而 MP 算法只与最近一次选择的原子正交。

对于一个长度为$n$的信号来说，OMP 的收敛次数一定小于等于$n$次。这一点很好理解，因为 OMP 是把之前选择的原子进行正交化了，相当于由原来的选择的原子构建了一组正交基，一个有n维的向量，最多也用分解n次。

最多只需要构建出一个 n 维的 Hilbert 空间，这个空间里的所有元素都可以它的一组正交基表示出来。

对于 OMP，关键之处在于理解如何构造出这一组正交基，下面讲述其具体流程。

正交匹配追踪原理

假定$R_kf$和前面选择的原子都正交，然后推导出来怎么求。

假设$k$阶近似的时候有：

$$
f=\sum_{n=1}^k a_n^k x_n + R_kf, \quad with \quad \langle R_kf,x_n \rangle = 0, n={1,\cdots,k} \tag{1}
$$

在$k+1$阶近似的时候有：

$$
f=\sum_{n=1}^{k+1} a_n^{k+1} x_n + R_kf, \quad with \quad \langle R_{k+1}f,x_n \rangle = 0, n={1,\cdots,k+1} \tag{2}
$$

应用$k+1$阶模型减去$k$阶模型，则有：

$$
\sum_{n=1}^k(a_n^{k+1}-a_n^k)+a_{k+1}^{k+1}x_{k+1}+R_{k+1}f-R_kf=0 \tag{3}
$$

由于选择的非正交字典矩阵，于是引入一个辅助模型，表示$x_{k+1}$对前$k$项$x_n(n=1,\cdots,k)$的依赖：

$$
x_{k+1} = \sum_{n=1}^k b_n^k x_n + r_k \quad with \quad \langle r_k,x_n \rangle = 0,n=1,\cdots,k \tag{4}
$$

$x_{k+1}$在$span{x_1,\cdots,x_k }$上进行正交投影，后面的项是残差。注意这里的$a和b$表示的是第$k$步。如果$x_{k+1}$和前$k$项线性无关的话，$x_{k+1}=r_k$.

$$
\sum_{n=1}^k b_n^kx_n = P_{V_k} x_{k+1} \quad and \quad r_k = P_{V_k^+} x_{k+1}
$$

将$(4)$代入$(3)$中，有：

$$
\sum_{n=1}^k (a_n^{k+1}-a_n^k+a_{k+1}^{k+1} b_n^k)x_n + (a_{k+1}^{k+1} r_k + R_{k+1}f - R_kf) = 0 \tag{5}
$$

若$(5)$恒成立，则有：

$$
a_n^{k+1}-a_n^k+a_{k+1}^{k+1} b_n^k = 0 \tag{6}
$$

$$
a_{k+1}^{k+1} r_k + R_{k+1}f - R_kf = 0 \tag{7}
$$

令$a_{k+1}^{k+1} = \alpha_k$,由$(6)$得：

$$
a_n^{k+1} = a_n^k - \alpha_k b_n^k
$$

其中，

$$
\alpha_k = \frac{\langle R_kf, x_{k+1} \rangle}{\langle r_k, x_{k+1}\rangle} = \frac{\langle R_kf,x_{k+1} \rangle}{|r_k|^2}
$$

由$(7)$可得:

$$
\langle a_{k+1}^{k+1} r_k + R_{k+1}f - R_kf,x_{k+1}\rangle = 0
$$

于是：

$$
\langle a_{k+1}^{k+1} r_k,x_{k+1} \rangle = \langle R_{k+1}f,x_{k+1} \rangle - \langle R_kf,x_{k+1} \rangle
$$

则：

$$
\alpha_k = \frac{\langle R_kf, x_{k+1\rangle}}{\langle r_k, x_{k+1}\rangle}
$$

在$(4)$中与$r_k$做内积，可以求得$|r_k|^2$

$$
\langle x_{k+1},r_k \rangle = \sum_{n=1}^k \langle b_n^k x_n,r_k \rangle + \langle r_k,r_k \rangle
$$

对于$(4)$，可以求出$b_n^k$.

正交匹配追踪收敛性证明

由$(7)$式：$a_{k+1}^{k+1} r_k + R_{k+1}f - R_kf = 0$，有

$$
\alpha_k r_k + R_{k+1}f = R_kf
$$

由于$r_k$与$R_{k+1}f$正交，左右同时求$l_2$范数的平方，于是有：

$$
\alpha_k^2 r_k^2 + R_{k+1}f^2 + 2 \langle \alpha_k r_k,R_{k+1}f \rangle = R_kf^2
$$

将$\alpha_k$代入有：

$$
|R_{k+1}|^2 = |R_k|^2 - \frac{|\langle R_kf,x_{k+1} \rangle |^2}{|r_k|^2}
$$

可见随着迭代次数的增加，残差逐渐减小，迭代是收敛的。

证明$r_k$与$R_{k+1}$正交： $\langle R_{k=1}f,x_{k+1} \rangle =0$

$$
x_{k+1} = \sum_{n=1}^k b_n^k x_n + r_k\quad with \quad \langle r_k,x_n \rangle = 0,n=1,\cdots,k
$$

$$
\langle R_{k+1}, \sum_{n=1}^kb_n^k x_n + r_k \rangle =0
$$

$$
\langle R_{k+1}, \sum_{n=1}^kb_n^k x_n \rangle + \langle R_{k+1}, r_k \rangle =0
$$

算法循环过程说明

算法流程

• 第一步：计算残差与各原子的内积
• 第二步：寻找最匹配的原子
• 第三步：是否达到终止条件
• 第四步：原子重排 $k+0 \leftrightarrow n_{k+1}$，例如找到$\langle R_0f,x_{n_1} \rangle max$，放在第一列
• 第五步：计算${b_n^k}_{n=0}^k$，使其满足期待的正交条件
• 第六步：令$\alpha_k = a_{k+0}^{k+1}$，计算重新分配的系数，更新模型
• 第七步：循环

重新分配系数是为了保证残差和每一个选择的原子正交，加快收敛速度，和 MP 的差别就在这个$R_{k + 1}f$的更新上。

基追踪（Basic Pursuit)

基追踪的基本概念

Basic Pursuit (BP) is a principle (not an algorithm) for decomposing a signal into an ‘optimal’ superposition of dictionary elements, where optimal means having the smallest $l_1$ norm of coefficients among all such decompositions.

$$
min | \beta |_1, \quad s.t. \quad D \beta = f
$$

For dealing with data at noise level $\sigma >0$, they propose approximate decomposition as in:

$$
f=D \beta + r
$$

And solving:

$$
min|D \beta - f |_2 ^2 + \lambda_n| \beta |_1
$$

with $\lambda_n =\sigma \sqrt{2log(#D)}$ depending on the number $#D$ of distinct vectors in the dictionary.Advantages over MOF(the method of frames), MP, OMP, and BOB(the best orthogonal basis):

• better sparsity
• super-resolution

For all those methods mentioned above, nonuniqueness gives the possibility of adaption.

总结

匹配追踪（MP）和正交匹配追踪（OMP）都是让  $\beta$（也就是选择的一组参数）的$L_0$-norm 最小，BP 是让其$L_1$-norm 最小，这是这三个方法的区别。

MP 和 OMP 算法：

$$
min | \beta | _0, \quad s.t. \quad D \beta = f
$$

BP 方法：

$$
min | \beta |_1, \quad s.t. \quad D \beta = f
$$

稀疏分解方法把信号分解当成一个 ill-posed problem（不适定问题） 进行求解，这其实也是一个反问题，反问题本身大多数都是不适定问题。