## 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

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

 Fund supported: the NSFC.  62071262

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

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 引言

$\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}$的伪逆.

## 2 主要结果

OMP算法步骤如下

$$$\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} .$$$

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

$k+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}$

$\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}$

$\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}$

(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}$

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

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

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

要证的式子可以转化成

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

$$$\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}}},$$$

$\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$ -稀疏噪声向量

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

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

${\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

 输入: 样本${\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}$

 输入: 样本${\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}$

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

## 参考文献 原文顺序 文献年度倒序 文中引用次数倒序 被引期刊影响因子

Dnoho D L .

Compressed sensing

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

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

Candés E J , Tao T .

The power of convex relaxation: Near-optimal matrix completion

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

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

Improved pediatric MR imaging with compressed sensing

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

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

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

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

Needell D , Tropp J A .

Iterative signal recovery from incomplete and inaccurate samples

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

Dai W , Milenkovic O .

Subspace pursuit for compressive sensing signal reconstruction

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

Wang J , Kwon S , Shim B .

Generalized orthogonal matching pursuit

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

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

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

Davenport A M , Wakin B M .

Analysis of orthogonal matching pursuit using restricted isometry property

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

Liu E , Temlyakov V .

The orthogonal super greedy algorithm and applications in compressed sensing

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

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

Wang J , Shim B .

On the recovery limit of sparse signals using orthogonal matching pursuit

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

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

Maleh R .

Improved RIP analysis of orthogonal matching pursuit

Computer Science, 2011, 3, 782- 794

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

Mo Q .

A sharp restricted isometry constant bound of orthogonal matching pursuit

Mathematics, 2015, 2, 249- 262

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

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

/

 〈 〉