【摘要】Exact recovery of a sparse signal from a linear model arises from many applications. The orthogonal matching pursuit (OMP) algorithm is a widely used sparse signal recovery algorithm due to its excellent recovery performance and high efficiency. A fundamental question regarding the exact sparse signal recovery with OMP is what is the probability that the OMP algorithm can exactly recover the sparse signal and also what is the minimal number of measurements to guarantee a satisfactory recovery performance. This paper points out that although in practical applications, in addition to the sparsity, the $K$-sparse signal $x$ usually has some additional property (for example, the nonzero entries of $\x$ independently and identically follow the Gaussian distribution, and $\x$ has exponential decaying property), as far as we know, none of existing analysis uses these properties to answer the above questions. In this paper, based on the distribution of $\x$, we develop an upper bound on $\|\x\|_2^2/\|\x\|_1^2$. Then, we explore this upper bound to develop a lower bound on the probability of exact recovery with OMP in $K$ iterations. Furthermore, we develop a lower bound on $m$ to guarantee that the exact recovery probability of $K$ iterations of OMP is not lower than a given probability. 

【报告人简介】温金明，2015年6月毕业于加拿大麦吉尔大学数学与统计学院，获哲学博士学位。现为暨南大学信息科学技术学院的教授。他的研究方向主要是整数信号和稀疏信号恢复的算法设计与理论分析。他以第一作者在IEEE Communications Magazine、Applied and Computational Harmonic Analysis (中科院数学一区期刊)、IEEE Transactions on Information Theory、 IEEE Transactions on Signal Processing等顶级期刊和会议发表35篇学术论文，其中第一作者的论文24篇。目前他担任IEEE Access（SCI检索）期刊的编辑。