Sparse recovery aims to reconstruct high dimensional sparse signals from their low dimensional linear samples. In recent years, sparse recovery has attracted a lot of interest in electrical engineering, computer science, statistics and applied mathematics. This talk is about a classic greedy algorithm called orthogonal matching pursuit (OMP). For its simplicity, ease of implementation, and promising recovery performance, OMP has been widely used in practice. This talk will introduce the theoretical limit of OMP in the noiseless scenario and its performance for approximate sup- port recovery under constant signal-to-noise ratio (SNR). This talk will also introduce the generalized OMP (gOMP) algorithm.

海报