学术报告（温金明 9.25）

Abstract ：

Exact recovery of a sparse signal x from linear measurements arises from many applications. The orthogonal matching pursuit (OMP) algorithm is a widely used algorithm for reconstructing x. A fundamental question in the performance analysis of OMP is the characterizations of the probability that it can exactly recover x for random sensing matrices and the necessary number of measurements to guarantee a satisfactory recovery performance. Although in many practical applications, in addition to the sparsity, x usually also has some additional properties (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 question. In this talk, we will use the prior information of x to refine the performance analysis of the OMP algorithm. Specifically, we develop a better lower bound on the probability of exact recovery with OMP and a better lower bound on the necessary number of measurements to guarantee a target recovery performance. The new bounds are significantly better than existing ones. This is joint work with Prof. Wei Yu from Toronto University and Dr. Rui Zhang from Huawei Technologies Company, Ltd