快速正交匹配追踪算法在稀疏信号恢复与逼近中的应用

《Pattern Recognition Letters》：Fast Orthogonal Matching Pursuit for Sparse Signal Recovery and Approximation

　　余慧媛|何佳|程曼琪
美国伊利诺伊理工学院应用数学系，芝加哥，60616，IL

**摘要**
当信号包含许多非零元素时，正交匹配追踪（OMP）面临计算挑战。OMP涉及一个正交投影步骤，该步骤在每次迭代中解决最小二乘问题。随着非零元素数量的增加，这一步骤变得极其缓慢且计算成本高昂。先前的工作[11]提出了通过连续回归的正交匹配追踪（OMP-SR）和分块连续回归（BSR）算法来降低正交投影的复杂性，并为信号具有稀疏表示时精确恢复建立了充分条件。本文扩展了该研究，以检验这些算法对含噪声且可能不具有稀疏表示的一般信号的恢复条件。同时，本文还提供了含噪声信号的近似误差界限。

**引言**
从低维测量中恢复稀疏信号的问题已被广泛研究。信号可以通过测量矩阵线性压缩以获得低维测量值。设y=Φx为N维测量值，Φ∈RN×d为测量矩阵，x为具有k个非零元素的d维信号。在稀疏恢复问题中，k ? d，因此x被称为k-稀疏信号。通常，N < d，因此从y中恢复x需要解决一个欠定系统。一个方便的表述是：
min_x∥x∥0 ≤ y=Φx
这个?0范数最小化问题是一个NP难问题。基追踪（BP）[1]、[2]、[3]提供了?1松弛，而框架方法（MOF）[4]提供了?2松弛，将?0范数最小化问题转化为凸优化问题。然而，它们并不能提供最稀疏的解，使用?1和?2最小化混合的方法（例如[5]、[6]）也是如此。

OMP [7]、[8]是一种广泛使用的稀疏恢复方法。OMP通过迭代选择与当前残差相关性最大的原子，并通过在每次迭代中添加正交投影来改进标准MP [9]。尽管正交投影提高了恢复效果，但随着选择更多原子，它也可能增加计算负担。广义OMP（gOMP）[10]在每次迭代中选择多个原子，从而减少了迭代次数，但仍无法摆脱正交投影引入的复杂性。

**通过连续回归的正交匹配追踪（OMP-SR）[11]**通过使用单个原子的连续回归来更快地实现正交投影，从而避免了在整个支持集Γ上计算Φ的伪逆。OMP-SR每次迭代所需的时间明显少于OMP。同样，OMP-SR的分块版本——分块连续回归（BSR）[11]由于其更高效的正交投影实现，每次迭代所需的时间也显著少于gOMP。

**先前的工作**[11]提出了针对y=Φx的精确稀疏恢复算法和理论结果。本文关注含噪声的一般信号的稀疏近似问题，其中?y=Φx+?。一般信号可能没有精确的稀疏表示。为了找到含噪声y的最佳近似值，可以使用原子的线性组合来表述这个问题：
min_x∥y?Φx∥2 ≤ ∥x∥0 ≤ k

**第2节**说明了OMP-SR相对于OMP的计算优势。**第3节**回顾了BSR在精确恢复方面的收敛结果。**第4节**为BSR算法应用于一般信号时建立了充分条件。**第5节**分析了算法终止时的近似误差。**第6节**展示了实验结果。

**代码片段**
OMP-SR和OMP都通过迭代选择与当前残差相关性最大的原子来进行匹配追踪（第4行）。然而，OMP-SR使用了不同的正交投影方法。
正交投影需要解决最小二乘最小化问题（OMP的第6行）。可以通过计算^st=(ΦΓ?ΦΓ)?1ΦΓ?y来完成。使用QR分解可以避免计算伪逆的复杂性（例如[12]、[13]、[14]、[15]、[16]、[17]），从而提高效率。

**BSR的精确恢复条件**
标准匹配追踪一次只选择一个原子。这将增加解决最小二乘问题的次数。一次选择c个（c ≥ 1）原子可以直接解决这个问题。这就是gOMP的动机。
我们现在通过应用连续回归的思想来改进gOMP，以避免昂贵的正交投影步骤，从而得到了BSR算法。当块大小c=1时，OMP-SR可以被视为BSR的一个特例。

**BSR对一般信号的恢复条件**
[7]将OMP讨论为恢复一般信号的近似算法。我们知道，OMP一次选择一个原子。类似地，我们可以确定BSR对一般信号的恢复条件。
假设对于任意输入信号y，存在一个k项最优稀疏近似sopt，即?y=sopt+?，且sopt=∑j∈Λoptajφj，其中|Λopt|=k。y与其最优近似sopt之间的差异是不可约误差ε。

**BSR的近似误差**
设sκ表示BSR算法在κ次迭代后找到的近似解。我们关注∥y?sκ∥2的上界。如果算法在终止时找到了所有k个最优原子，则近似误差被限制在∥y?sopt∥2范围内。我们只考虑算法在κ次迭代后未找到所有最优原子的情况。
我们首先考虑一个仅使用Φopt中的最优原子的基线解s，即s=∑j∈Λoptbjφj。方程（11）等价于∥sopt?s∥2 > k。

**实验**
我们在测量值y中添加人工噪声ε，并报告归一化近似误差∥y?sκ∥2/∥y∥2，其中sκ=∑φj∈Φbjφj是算法在κ次迭代后找到的稀疏表示。假设噪声是加性的且呈正态分布，即?y=Φx+?，其中εi～N(0,σ2/N)对于i=1,…,N。
我们使用MNIST手写数字和Phantom图像作为真实图像x。首先将图像展平为向量x∈Rd，然后对x应用不同的测量矩阵。

**结论**
随着k的增加，OMP的迭代方法需要多次迭代来恢复信号，且随着向信号支持中添加更多原子，正交投影的成本也会增加。OMP-SR提供了一种无需在每次迭代中计算矩阵伪逆的成本效益高的正交投影解决方案。由于正交投影是OMP中的关键步骤，所提出的连续回归技术也改进了其他OMP变体，如[10]、[23]、[24]、CRedi。

**作者贡献声明**
余慧媛：撰写——审阅与编辑、撰写——原始草稿、可视化、验证、软件、方法论。
何佳：软件、数据管理。
程曼琪：撰写——审阅与编辑、撰写——原始草稿、可视化、验证、监督、资源管理、项目管理、方法论、形式分析、概念化。

**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。