学术报告(温金明 11.12)

Exact Sparse Signal Recovery via Orthogonal Matching Pursuit with Prior Information

发布人:周妍 发布日期:2018-10-17
主题
Exact Sparse Signal Recovery via Orthogonal Matching Pursuit with Prior Information
活动时间
-
活动地址
新数学楼416
主讲人
温金明 教授(暨南大学)

摘要:

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.

 

数学学院

2018年10月17日