数学物理学报, 2021, 41(5): 1555-1565 doi:

论文

压缩感知OMP算法下信号重建方法研究

付敏,, 郝嘉骏,, 解烈军,, 王金平,

宁波大学数学与统计学院 浙江宁波 315211

Exact Support Recovery of Sparse Signals from Noisy Measurements

Fu Min,, Hao Jiajun,, Xie Liejun,, Wang Jinping,

School of Mathematics and Statistics, Ningbo University, Zhejiang Ningbo 315211

通讯作者: 王金平, E-mail: wangjinping@nbu.edu.cn

收稿日期: 2020-03-9  

基金资助: 国家自然科学基金.  62071262

Received: 2020-03-9  

Fund supported: the NSFC.  62071262

作者简介 About authors

付敏,E-mail:2818391447@qq.com , E-mail:2818391447@qq.com

郝嘉骏,E-mail:825821801@qq.com , E-mail:825821801@qq.com

解烈军,E-mail:xieliejun@nbu.edu.cn , E-mail:xieliejun@nbu.edu.cn

Abstract

In this paper, we presents an improved OMP algorithm. Then the sparse reconstruction problem of OMP algorithm under the influence of the noise is studied. The conditions of SNR parameters for sparse reconstruction are obtained. Finnally, numerical simulation is used to verify the above conclusions.

Keywords: CS OMP algorithm ; Sparse reconstruction ; Signal-to-Noise Ratio

PDF (627KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

付敏, 郝嘉骏, 解烈军, 王金平. 压缩感知OMP算法下信号重建方法研究. 数学物理学报[J], 2021, 41(5): 1555-1565 doi:

Fu Min, Hao Jiajun, Xie Liejun, Wang Jinping. Exact Support Recovery of Sparse Signals from Noisy Measurements. Acta Mathematica Scientia[J], 2021, 41(5): 1555-1565 doi:

1 引言

压缩感知(Compressed Sensing, CS)[1]理论是一种新型信号采样理论. CS理论指出: 在信号是稀疏的的前提下, 重构算法能够从满足一定条件的少量线性测量中高概率地重建出高维稀疏信号. 基于自然信号中的大多数信号是稀疏的, CS理论被广泛应用到各个领域, 比如单像素相机、低秩矩阵恢复、核磁共振成像等[2-4]. 令$ {\bf x} = [x_1, x_2, \cdots , x_N]^{T}\in {{\Bbb R}} ^{N} $$ K $维稀疏信号(即$ \Vert {\bf x}\Vert_0\leq K $), $ \Gamma = {\rm supp}({\bf x}) = \{i\mid \vert x_i\vert\neq0\} $表示信号$ {\bf x} $的支撑. 假设测量过程中含有噪声, 相应的测量值$ {\bf y}\in {{\Bbb R}} ^n $满足以下线性模型

$ \begin{equation} {\bf y} = {\Phi}{\bf x}+{\bf w}, \end{equation} $

其中, 感知矩阵$ \Phi\in {{\Bbb R}} ^{n\times N} $, ($ n\ll N $), $ K $维稀疏信号$ {\bf x} $是确定的, $ {\bf w}\in {{\Bbb R}} ^{n} $是噪声, $ \Phi_{i} $表示$ \Phi $的第$ i $列(即$ \Phi = [\Phi_{1}, \Phi_{2}, \cdots, \Phi_{N}] $). 在下文中, 假设$ \Phi $的每一列(通常称为一个原子)是归一化的(即$ \parallel \Phi_{i}\parallel_{2} = 1 $, $ i = 1, 2, \cdots, N $).

重建稀疏信号是CS理论的首要目标. 因为$ n\ll N $, 欠定系统(1.1)的解通常是不唯一的. 然而, 由于稀疏的先验知识, CS理论[5]表明: 在采样矩阵$ \Phi $满足一定条件下, 求解$ l_{0} $-范数最小化问题能够高概率地重建信号$ {\bf x} $, 即

众所周知, 寻找最优的解需要穷尽一切可能的搜索, 这是NP -难的. 因此, 需要寻找一种有效率的重建算法取代穷尽的搜索. 此时, 正交匹配追踪(Orthogonal Matching Pursuit, OMP)算法由于它易操作和高效率而引起关注. OMP算法[6]是一种迭代型贪婪算法. 其原理为: 在每次迭代中, 选择与当前残差内积绝对值最大的矩阵的一个列来逐步逼近原始信号. 许多学者研究OMP算法的改进形式. 比如分段正交匹配追踪(Stagewise OMP, StOMP)[7]算法, 压缩采样匹配追踪(Compressive Sampling MP, CoSamp)[8]算法, 子空间追踪(Suspace Pursuit, SP) [9]算法, 广义正交匹配追踪(generalised OMP, gOMP)[10]算法等. 本文提出OMP算法的一种改进方法来重建稀疏信号. 相比于标准的OMP算法, 唯一的区别是加入系数阈值判断机制.

测量矩阵$ \Phi $的两个特性经常用于保证OMP算法的精确重建.

定义1.1[11]  测量矩阵$ \Phi $的相关性质: 测量矩阵$ \Phi $的每一列是归一化的$ (\parallel \Phi_{i}\parallel_{2} = 1, \Phi_{i} $$ \Phi $的第$ i $列向量, $ i\in[N]) \Phi $的相关系数$ \mu(\Phi) $

定义1.2[12]  测量矩阵$ \Phi $$ K $ -阶约束等距性质(Restricted Isometry Property, RIP): 如果存在$ \delta_{K}\in(0, 1) $, 使得

对任意$ K $-稀疏向量x都成立.满足上式的最小常数$ \delta_{K} $称为矩阵$ \Phi $$ K $-阶约束等距常数(Restricted Isometry Constant, RIC).

考虑到一些矩阵满足限制等距性, 但不满足相干性条件的情况, 许多学者研究了重建算法下采样矩阵的限制等距性. 在无噪声情况下(即, $ w = 0 $), Davenport和Wakin[13]证得$ \delta_{K+1}<\frac{1}{\sqrt{3K}} $是OMP算法精确重建输入信号的一个充分条件. 随后条件逐步改进为$ \delta_{K+1}<\frac{1}{(1+\sqrt{2})\sqrt{K}}, \delta_{K}<\frac{\sqrt{K-1}}{\sqrt{K-1+K}}, \delta_{K+1}<\frac{1}{1+\sqrt{K}} $ (参见文献[14-16]). 在有噪声情况下(即, $ w\neq0 $), 我们往往关注于重建信号$ {\bf x} $的支撑(即, supp$ ({\bf x}) $). 一旦supp$ ({\bf x}) $准确找出, 信号$ {\bf x} $可由最小二乘估计得出. 在文献[17] 中已经证明: 当测量矩阵满足一定的MCSNR和$ \delta_{K+1}<\frac{1}{2+\sqrt{K}} $条件时, OMP算法能从噪声测量中准确重建信号的支撑. 随后条件逐步改进为$ \delta_{K+1}<\frac{1}{\sqrt{K}+1} $ (参见文献[18]), $ \delta_{K+1}<\frac{\sqrt{4K+1}-1}{2K} $ (参见文献[19]). 最近, 已经证得$ \delta_{K+1}<\frac{1}{\sqrt{K+1}} $ (参见文献[20])是一个尖锐充分条件.

本文的主要内容如下.

$ \bullet $  提出OMP算法的一种改进方法, 通过加入一个系数阈值机制来提高重建信号的精确度.

$ \bullet $  基于矩阵的RIP的一定条件下, 本文给出OMP算法重建信号支撑的一个关于SNR的条件. 接着, 关于SNR和不同噪声水平下的数据仿真来证明理论结果.

首先, 基于这篇文章的框架有以下假设与引理

(A1) $ \mid S\mid $表示集合$ S $的元素的个数.

(A2) $ \Phi_{\Gamma}\in {{\Bbb R}} ^{n\times \mid\Gamma\mid} $是其列索引是属于集合$ \Gamma $里的子矩阵.

(A3) $ {\bf x}_{\Gamma}\in R^{\mid\Gamma\mid} $表示$ {\bf x} $非零分量下脚标限制在集合$ \Gamma $.

(A4) $ \Phi^{T} $表示矩阵$ \Phi $的转置.

(A5) $ \Phi^{\dagger}_{\Gamma} = {(\Phi^{T}_{\Gamma}\Phi_{\Gamma})^{-1}}\Phi^{T}_{\Gamma} $表示矩阵$ \Phi_{\Gamma} $的伪逆.

引理1.1[12]  对于$ 0<p<q\leq\infty $, 有$ \parallel {\bf x}\parallel_{q} \leq\parallel {\bf x}\parallel_{p}, $特别地, $ \parallel {\bf x}\parallel_{\infty} \leq\parallel {\bf x}\parallel_{2} $.

引理1.2[12]  令$ \Phi\in {{\Bbb R}} ^{n\times N} $满足$ k_{1}, k_{2} $阶RIP性质, 以下不等式成立: 对于任意整数$ k_{1}\leq k_{2} $, 有$ \delta_{k_{1}}\leq\delta_{k_2} $.

引理1.3[12]  令$ \Phi\in {{\Bbb R}} ^{n\times N} $满足$ K+1 $阶的RIP性质, 并且$ S\subset\{1, 2, \cdot\cdot\cdot , N\} $, $ \mid S\mid\leq K $, 接着对于任意的$ {\bf z}\in {{\Bbb R}} ^{n} $, 有

定义1.3  信号$ {\bf x} $经过测量矩阵$ \Phi $线性观测后, 得到测量值$ {\bf y} = \Phi {\bf x}+{\bf w} $, 信号$ {\bf x} $的信噪比(Signal to Noise Ratio, SNR)定义为

定义1.4  信号$ {\bf x} $经过测量矩阵$ \Phi $线性观测后, 得到测量值$ {\bf y} = \Phi {\bf x}+{\bf w} $, 信号$ {\bf x} $的最小平均分量比(Minimum to Average Rato, NAR)定义为

2 主要结果

OMP算法步骤如下

在搜寻过程中, 如果有一个原子选错了, OMP算法的输出将不正确. 为了改进OMP算法的重建性能, 引入一个阈值判断机制.

为了确保每次迭代中选择一个正确的原子, 我们分析第$ k $次($ 1\leq k\leq K $) 迭代, 在前面$ k-1 $次迭代中正确识别的假设下, 当第$ k $$ {\bf x} $的支撑已经被OMP算法识别, 有

噪声下, OMP算法求解的最优化问题为

$ \begin{equation} \min\parallel{\bf x}\parallel_{0} \quad \rm subject \quad to \quad \parallel{\bf y}-\Phi {\bf x}\parallel_{2}<\varepsilon. \end{equation} $

引理2.1  假设$ \Phi $具有$ k+1 $阶限制等距性质, 索引集$ \Lambda, \Gamma\subset[N] $, 则

在文献[21]的引理$ 1 $中, 假设(1)中$ \Phi $具有$ k+1 $阶限制等距性质, 集合$ S $$ \Omega $的真子集(即, $ S\subsetneqq\Omega $), 则

引理2.1的证明实际上是文献[21]引理$ 1 $的推广. 注意到文献[21]中引理$ 1 $只考虑了情况: $ S $$ \Omega $的真子集(即, $ S\subsetneqq \Omega $). 我们的贡献是将这种情况推广到$ \Omega\cap S\neq \emptyset $ (即, 在本文中$ \Gamma\cap \Lambda\neq \emptyset $). 而且, 容易想到: 当$ \Lambda = \emptyset $ (因为$ \Lambda = \emptyset $满足引理2.1条件的), 则

定理2.1  假设感知矩阵$ \Phi $具有$ k+1 $阶限制等距性质且$ \delta_{k+1}<\frac{1}{\sqrt{k+1}} $, 则$ \rm OMP $算法能够在$ k $次迭代之内, 精确恢复supp$ ({\bf x}) $, 如果有下面的等式成立

   证明包括两个步骤. 首先分别给出OMP算法在第$ 1 $次, 第$ k $次迭代中选择正确原子的两个条件. 接着建立OMP算法的全局性条件.

由算法的步骤$ 3 $, 对于任意$ k<K $, $ K $-稀疏信号$ {\bf x} $, OMP算法将在第$ (k+1) $次迭代选择正确的原子, 如果

$ \begin{equation} \max\limits_{i\in\Gamma}\mid \Phi^{T}_{i}{\bf r}^{k}\mid>\max\limits_{j\in\Gamma^{c}}\mid \Phi^{T}_{j}{\bf r}^{k}\mid. \end{equation} $

为了证明式(2.2), 等价于证明

$ \begin{equation} \max\limits_{i\in \Gamma\setminus \Lambda^{k}}\mid \langle {\bf r}^{k}, \Phi_{i}\rangle \mid>\max\limits_{j\in \Gamma^{c}}\mid \langle {\bf r}^{k}, \Phi_{j}\rangle \mid. \end{equation} $

由算法的步骤$ 5 $可得

第一次迭代选择正确的原子.

在第一次迭代, OMP算法选中的一个原子$ \Phi_{\Lambda^{1}} $是与测量向量$ {\bf y} $最大程度地相关. 由范数的性质得

$ \begin{eqnarray} \mid \langle {\bf y}, \Phi_{\Lambda^{1}}\rangle\mid& = &\max\limits_{i\in\Gamma}\mid \langle {\bf y}, \Phi_{i}\rangle\mid = \parallel{\Phi^{T}_{\Gamma}}{\bf y}\parallel_{\infty} = \parallel{\Phi^{T}_{\Gamma}}(\Phi {\bf x}+{\bf w})\parallel_{\infty}\\ &\geq &\parallel{\Phi^{T}_{\Gamma}}\Phi {\bf x}\parallel_{\infty}-\parallel{\Phi^{T}_{\Gamma}}{\bf w}\parallel_{\infty} \geq \parallel{\Phi^{T}_{\Gamma}}\Phi {\bf x}\parallel_{\infty}-\parallel{\Phi^{T}_{\Gamma}}{\bf w}\parallel_{2}. \end{eqnarray} $

另一方面, 如果在第一次迭代, OMP算法选错了一个原子$ \Phi_{j_{0}} $ (即, $ j_{0}\in \Gamma^{c} $), 得

$ \begin{eqnarray} \mid \langle {\bf y}, \Phi_{j_{0}}\rangle\mid& = &\max\limits_{j\in\Gamma^c}\mid \langle {\bf y}, \Phi_{j}\rangle\mid = \parallel{\Phi^{T}_{\Gamma^c}}{\bf y}\parallel_{\infty} = \parallel{\Phi^{T}_{\Gamma^c}}(\Phi {\bf x}+{\bf w})\parallel_{\infty}\\ &\leq & \parallel{\Phi^{T}_{\Gamma^c}}\Phi {\bf x}\parallel_{\infty}+\parallel{\Phi^{T}_{\Gamma^c}}{\bf w}\parallel_{\infty}. \end{eqnarray} $

由式(2.4)和式(2.5), 为证式(2.3), 需证

$ \begin{equation} \parallel{\Phi^{T}_{\Gamma}}\Phi {\bf x}\parallel_{\infty}-\parallel{\Phi^{T}_{\Gamma^c}}\Phi {\bf x}\parallel_{\infty} >\parallel{\Phi^{T}_{\Gamma}}{\bf w}\parallel_{2}+\parallel{\Phi^{T}_{\Gamma^c}}{\bf w}\parallel_{\infty}. \end{equation} $

由引理2.1, 得

接下来给出不等式(2.6)右边的上界. 明显地, 存在$ j^{'}\in\Gamma^{c} $使得

(a): $ {\Phi^{T}_{j^{'}}}w $$ 1\times1 $向量. 由引理1.3得

因此, 式(2.6)可由下式保证

$ \begin{equation} \frac{1-\sqrt{K+1}{\delta_{K+1}}}{\sqrt{K}}\parallel {\bf x}\parallel_{2}>2(\sqrt{1+\delta_{K+1}})\parallel {\bf w}\parallel_{2} . \end{equation} $

进一步地

可证式(2.7)成立如果

成立, 即

$ \begin{equation} \ \sqrt{{\rm SNR}} > \frac {2\sqrt{K}(1+\delta_{K+1})}{1-\sqrt{K+1}\delta_{K+1}} \end{equation} $

成立.

$ k+1 $次迭代选择正确的原子.

假设OMP算法在前面$ k $次迭代中选择正确的原子, 则需要证明OMP算法在第$ (k+1) $次迭代中也选择了正确的原子(即$ \Lambda_{k}\subset\Gamma $). 只要证明式(2.2)成立即可. 由引理1.1得

$ \begin{eqnarray} \max\limits_{i\in\Gamma\setminus\Lambda_{k}}\mid \langle {\bf r}^{k}, \Phi_{i}\rangle\mid& = &\parallel \Phi^{T}_{\Gamma\setminus\Lambda_{k}}(P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}} +P^{\perp}_{\Lambda_{k}}{\bf w})\parallel_{\infty}\\ &\geq &\parallel \Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_{\infty} - \parallel \Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{\infty}\\ &\geq & \Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_{\infty} -\parallel \Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2} \end{eqnarray} $

$ \begin{eqnarray} \max\limits_{j\in\Gamma^{c}}\mid \langle {\bf r}^{k}, \Phi_{j}\rangle\mid& = &\parallel \Phi^{T}_{\Gamma^{c}}(P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}} +P^{\perp}_{\Lambda_{k}}{\bf w})\parallel_{\infty}\\ &\leq &\parallel \Phi^{T}_{\Gamma^{c}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_{\infty} + \parallel \Phi^{T}_{\Gamma^{c}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{\infty}. \end{eqnarray} $

由式(2.9)和式(2.10), 要证式(2.3), 只需证

$ \begin{eqnarray} &&\parallel\Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_{\infty}- \parallel \Phi^{T}_{\Gamma^{c}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_{\infty}\\ & > & \parallel \Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2}+ \parallel \Phi^{T}_{\Gamma^{c}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{\infty}. \end{eqnarray} $

接下来, 给出式(2.11)左边的一个下界. 由假设$ \Lambda_{k}\subset\Gamma $和引理2.1, 有

$ \begin{eqnarray} &&\parallel\Phi^{T}_{{\Gamma}\Lambda_{k}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_\infty -\parallel\Phi^{T}_{{\Gamma}^{c}}P^{\perp}_{\Lambda_{k}}\Phi_{\Gamma\setminus\Lambda_{k}}{\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_\infty\\ &\geq&\frac{1-\sqrt{\mid\Gamma\mid-\mid\Lambda_{k}\mid+1}{\delta_{\mid\Gamma\mid+1}}}{\sqrt{\mid\Gamma\mid-\mid\Lambda_{k}\mid}}\parallel {\bf x}_{\Gamma\setminus\Lambda_{k}}\parallel_{2}\\ &\geq&(1-\sqrt{K+1}\delta_{K+1})\min\limits_{i\in\Omega}\mid x_{i}\mid\geq((1-\sqrt{K+1}\delta_{K+1})(\frac{\sqrt{{\rm MAR}}\parallel \Phi {\bf x}\parallel_{2}}{\sqrt{K}})\\ & = &(\frac{1-\sqrt{K+1}\delta_{K+1}}{\sqrt{K}})(\sqrt{{\rm MAR}}\sqrt{{\rm SNR}})\parallel {\bf w}\parallel_{2}. \end{eqnarray} $

接下来, 给出式(2.11)右边的一个上界. 由假设$ \Lambda_{k}\subset\Gamma $, 明显地, 存在$ j_{1}\in\Gamma^{c} $使得

(b): $ \Phi^{T}_{j_{1}}P^{\perp}_{\Lambda_{k}}{\bf w} $$ 1\times1 $向量. 由引理1.1, 有

$ \begin{eqnarray} \parallel \Phi^{T}_{\Gamma\setminus\Lambda_{k}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2}+\parallel \Phi^{T}_{\Gamma^{c}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{\infty} & = &\parallel \Phi^{T}_{\Gamma}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2}+\parallel\Phi^{T}_{j_{1}}P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2}\\ &\leq& \sqrt{1+\delta_{K+1}}\parallel P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2}+\sqrt{1+\delta_{1}}\parallel P^{\perp}_{\Lambda_{k}}{\bf w}\parallel_{2}\\ &\leq& 2\sqrt{1+\delta_{K+1}}\parallel {\bf w}\parallel_{2}. \end{eqnarray} $

联立式(2.12)和式(2.13), 式(2.11)可由下式保证

进一步地, 观察到

要证式(2.11)也可由下式保证

$ \begin{equation} \ \sqrt{{\rm SNR}} > \frac {2\sqrt{K}(1+\delta_{K+1})}{(1-\sqrt{K+1}\delta_{K+1})\sqrt{{\rm MAR}}}. \end{equation} $

定理2.1证毕.

注2.1  由式(2.13), 在$ (k+1) $次迭代, OMP算法能够选择正确的原子, 有

(a): 由引理1.3可得. 由$ \delta_{K+1}<\frac{1}{\sqrt{K+1}} $, 可得原始信号和恢复信号的$ l_2 $-范数误差理论上界.

引理2.2  如果矩阵$ \Phi $满足的$ K+1 $阶约束等距常数是$ \delta_{K+1}<\frac{1}{\sqrt{K+1}} $.

$ \begin{equation} (1-\sqrt{K+1}\delta_{k+1})^{2}<1-\delta^{2}_{K+1}. \end{equation} $

   要证的式子可以转化成

$ \begin{equation} (K+2)\delta^{2}_{K+1}-2\sqrt{K+1}\delta_{K+1}\leq0, \end{equation} $

这时$ \delta_{K+1} = 0 $, 式(2.16)显然满足, 这时$ \delta_{K+1}\neq 0 $, 式(2.16)等价于

对任意正整数$ K $, 有

得到$ \delta_{K+1}<\frac{1}{\sqrt{K+1}} $是充分条件, 因此不等式(2.14)成立.

定理2.2   假设$ \Phi $满足$ K+1 $阶约束等距性质, 且$ \delta_{K+1}<\frac{1}{\sqrt{K+1}} $. 存在$\{ \Phi, {\bf x}, {\bf w} \}$, 有

$ \begin{equation} \sqrt{{\rm SNR}}<\frac{\sqrt{K}\sqrt{1-\delta_{K+1}}\sqrt{1+\delta_{K+1}}}{(1-\sqrt{K+1}\delta_{K+1})\sqrt{{\rm MAR}}}, \end{equation} $

使得OMP算法在$ k $次迭代内未能从$ {\bf y} = \Phi {\bf x}+{\bf w} $中精确恢复$ \rm supp({\bf x}) $.

$ \rm RIC $的限制下, $ \rm OMP $算法关于$ \rm SNR $的支撑恢复的一个最差的必要条件

   要证存在线性模型$ \{\Phi, {\bf x}, {\bf w}\} $, 满足定理的条件, 但是OMP算法未能在第$ k $次迭代内精确恢复$ \rm supp({\bf x}) $. 首先构建一个线性模型. 令$ \Phi\in {{\Bbb R}} ^{n\times n} $是个单位阵, $ {\bf x}\in {{\Bbb R}} ^{n} $是一个$ K $-稀疏信号, 且$ {\bf w}\in {{\Bbb R}} ^{n} $是个$ 1 $ -稀疏噪声向量

接着得到$ {\bf y} = [1, \cdots, 1, 0, \cdots, 1]^{T}. $这种情况有

由式(2.15), 有

可见该模型满足定理2.2的条件, 然而, OMP算法未能精确恢复信号$ {\bf x} $的支撑. 特别地, 在第一次迭代中

OMP算法不能保证在第一次迭代中选择正确的原子.

3 数值模拟

3.1 不同SNR程度下的信号恢复

很难设计出采样矩阵的任意阶都满足定理2.1中RIC的界. 该实验借助文献[13]的矩阵, 其RIC常数小于0.2.

$ {\bf x} = [0.5, -1.5, 0.5, -2, -1, 0, -0.8, 0.1, 1.7, 1]^{T} $.通过调节噪声来得到值为3.38的SNR. OMP算法用于从噪声测量$ {\bf y} = \Phi {\bf x}+{\bf w} $重建稀疏信号x. 原始和重建信号可从图 1读出.

图 1

图 1   原始信号和重建信号


图 1中看出, 重建信号不能识别原始信号$ {\bf x} $的第8个分量.

保持9 -稀疏信号$ {\bf x} $不变, MAR显然未改变. 用不同的噪声来控制SNR值. 模拟结果被以下表格展示.

表 3证明定理2.1的结论: 如果SNR值满足定理2.1的充分条件, 并且矩阵满足RIC条件, 支撑可以被准确的识别.

表 1   OMP算法

输入: 样本${\bf y}$, 采样矩阵$\Phi$, 稀疏度K
步骤1(识别): $\Lambda^{k} = \mathop{\arg\max}\limits _{\Upsilon\in\Gamma\setminus \Lambda_{k-1}}\mid \langle \Phi_{\Upsilon}, r^{k-1}\rangle\mid$
步骤2(增加): $\Lambda_{k} = \Lambda_{k-1}\cup\Lambda^{k}$
步骤3(估计): ${\bf x}^{(k)} = \mathop{\arg\min}\limits_{{\rm supp}({\bf u}) = \Lambda_{k}}\parallel {\bf y}-\Phi {\bf u}\parallel_{2}$
步骤4(更新): ${\bf r}_{k} = {\bf y}-\Phi {\bf x}^{(k)}$
输出: 重建信号${\bf x}^{(K)}$, 最优原子集$\Lambda_{K}$

新窗口打开| 下载CSV


表 2   改进的OMP算法

输入: 样本${\bf y}$, 采样矩阵$\Phi$, 稀疏度K
步骤1(识别): $\Lambda^{k} = \mathop{\arg\max}\limits_{\Upsilon\in\Gamma\setminus \Lambda_{k-1}}\mid \langle \Phi_{\Upsilon}, r^{k-1}\rangle\mid$
步骤2(增加): $\Lambda_{k} = \Lambda_{k-1}\cup\Lambda^{k}$
步骤3(估计): ${\bf x}^{(k)} = \mathop{\arg\min}\limits_{{\rm supp}({\bf u}) = \Lambda_{k}}\parallel {\bf y}-\Phi {\bf u}\parallel_{2}$
步骤4(筛选): 若$\parallel {\bf x}^{(k)}-{\bf x}^{(k-1)}\parallel_{2}\leq \parallel {\bf y}\parallel_{2}$,
是, 接着步骤5, 否则, 步骤1.
步骤5(更新): ${\bf r}_{k} = {\bf y}-\Phi {\bf x}^{(k)}$
输出: 输出信号$x^{K}$, 最优原子集$\Lambda_{K}$

新窗口打开| 下载CSV


表 3   不同SNR值下的信号恢复

SNR支撑的识别
337.85成功
187.69成功
112.62成功
93.85成功
80.44成功
3.38失败

新窗口打开| 下载CSV


3.2 不同噪声水平的信号恢复

根据前面的分析, 即使原始信号的支撑被准确识别, 原始稀疏信号由于存在的噪声仍然不能精确的重建. 该实验的噪声范围在0到0.1并每隔0.01取一次, 接着, 对于每个噪声水平, 采取一个新的测量矩阵服从随机独立分布, 测量信号由$ {\bf y} = \Phi {\bf x}+{\bf w} $计算得出. 最后, 改进算法重复1000次左右, 最大的误差余平均误差如图 2.

图 2

图 2   不同噪声水平的重建误差


图 3

图 3   OMP和改进算法下的图像去噪


图 2证明了理论上界的误差范围: 当稀疏度$ K $固定时, 误差几乎与噪声成线性关系. 明显的是$ K $越大, 与理论上仿真的结果越接近.

3.3 改进算法下的图像去噪

当噪声是Gaussian噪声时. 原始清晰图像是$ 256\times256 $ CT图像[22].

在本次实验中, 模糊的图像在改进OMP算法的重建下图像较清晰.

参考文献

Dnoho D L .

Compressed sensing

IEEE Trans Inf Theory, 2006, 52 (4): 1289- 1306

DOI:10.1109/TIT.2006.871582      [本文引用: 1]

Duarte M F , Davenport M A , Takhar D , et al.

Single-pixel imaging via compressive sampling

IEEE Signal Processing Magazine, 2008, 25 (2): 83- 91

DOI:10.1109/MSP.2007.914730      [本文引用: 1]

Candés E J , Tao T .

The power of convex relaxation: Near-optimal matrix completion

IEEE Trans Inf Theory, 2010, 56 (5): 2053- 2080

DOI:10.1109/TIT.2010.2044061     

Vasanawala S , Alley M , Hargresves B , et al.

Improved pediatric MR imaging with compressed sensing

Radiology, 2010, 256 (2): 607- 616

DOI:10.1148/radiol.10091218      [本文引用: 1]

Candes E J , Romberg J , Tao T .

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

IEEE Trans Inf Theory, 2006, 52 (2): 489- 509

DOI:10.1109/TIT.2005.862083      [本文引用: 1]

Rezaiifar Y, Krishnaprasad P S. Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition[C]//Proceedings of 27th Asilomar Conference on Signals, Systems & Computers. Pacific Grove, CA: IEEE, 2002

[本文引用: 1]

Dnoho D L , Tsaig Y , Drori I , et al.

Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit

IEEE Trans Inf Theory, 2012, 58 (2): 1094- 1121

DOI:10.1109/TIT.2011.2173241      [本文引用: 1]

Needell D , Tropp J A .

Iterative signal recovery from incomplete and inaccurate samples

Appl Comput Harmon Anal, 2009, 26 (3): 301- 321

DOI:10.1016/j.acha.2008.07.002      [本文引用: 1]

Dai W , Milenkovic O .

Subspace pursuit for compressive sensing signal reconstruction

IEEE Trans Inf Theory, 2009, 55 (5): 4316- 4332

URL     [本文引用: 1]

Wang J , Kwon S , Shim B .

Generalized orthogonal matching pursuit

IEEE Trans Signal Processing, 2012, 60 (12): 6202- 6216

DOI:10.1109/TSP.2012.2218810      [本文引用: 1]

李峰, 郭毅. 压缩感知浅析. 北京: 科学出版社, 2015

[本文引用: 1]

Li F , Guo Y . Compression Perception Analysed. Beijing: Science Press, 2015

[本文引用: 1]

Foucart S, Rauhut H. A Mathematical Introduction to Compressive Sensing. Berlin: Springer-Verlag, 2013

[本文引用: 4]

Davenport A M , Wakin B M .

Analysis of orthogonal matching pursuit using restricted isometry property

IEEE Trans Inf Theory. Theory, 2010, 56, 4395- 4401

DOI:10.1109/TIT.2010.2054653      [本文引用: 2]

Liu E , Temlyakov V .

The orthogonal super greedy algorithm and applications in compressed sensing

IEEE Trans Inf Theory, 2012, 58 (4): 2040- 2047

DOI:10.1109/TIT.2011.2177632      [本文引用: 1]

Wang J , Kwon S , Shim B .

Near optimal bound of orthogonal matching pursuit using restricted isometric constant

Eur J Adv Signal Processing, 2012, 8, 1874- 1890

URL    

Wang J , Shim B .

On the recovery limit of sparse signals using orthogonal matching pursuit

IEEE Trans Signal Processing, 2012, 60 (9): 4973- 4976

DOI:10.1109/TSP.2012.2203124      [本文引用: 1]

Li J , Wang Q , Shen Y .

Near optimal condition of OMP algorithm in recovering sparse siganl from noisy measuurement

Systems Engineering and Electronics, 2014, 25 (4): 547- 553

DOI:10.1109/JSEE.2014.00063      [本文引用: 1]

Maleh R .

Improved RIP analysis of orthogonal matching pursuit

Computer Science, 2011, 3, 782- 794

URL     [本文引用: 1]

Chang L H , Wu J Y .

An improved RIP-based performance guarantee for the sparse signal recovery via orthogonal matching pursuit

IEEE Trans Inf Theory, 2014, 60 (9): 4973- 4976

URL     [本文引用: 1]

Mo Q .

A sharp restricted isometry constant bound of orthogonal matching pursuit

Mathematics, 2015, 2, 249- 262

URL     [本文引用: 1]

Wen J , Zhou Z , Wang J , et al.

A sharp condition for exact support recovery with orthogonal matching pursuit

IEEE Trans Signal Processing, 2017, 65 (6): 1370- 1382

DOI:10.1109/TSP.2016.2634550      [本文引用: 3]

叶丽颖, 李静, 王金平.

具均匀衰减投影数据下发射型SPECT图像重建方法研究

数学物理学报, 2018, 38A (3): 613- 624

URL     [本文引用: 1]

Ye L Y , Li J , Wang J P .

Emission SPECT image reconstruction methods with uniformly attenuated projection data

Acta Math Sci, 2018, 38A (613): 624

URL     [本文引用: 1]

/