A Performance Guarantee for Orthogonal Matching Pursuit Using Mutual Coherence

Mohammad Emadi, Ehsan Miandji, Jonas Unger
Circuits, Systems, and Signal Processing, Volume 37, Number 4, page 1562--1574 - April 2017
Download the publication : main.pdf [478Ko]  
In this paper we present a new performance guarantee for the Orthogonal Matching Pursuit (OMP) algorithm. We use mutual coherence as a metric for determining the suitability of an arbitrary overcomplete dictionary for exact recovery. Specifically, a lower bound for the probability of correctly identifying the support of a sparse signal with additive white Gaussian noise and an upper bound for the mean square error is derived. Compared to previous work, the new bound takes into account the signal parameters such as dynamic range, noise variance, and sparsity. Numerical simulations show significant improvements over previous work and a much closer correlation to empirical results of OMP.

Images and movies


See also

MATLAB source code for generating results is here . The code relies on Ron Rubinstein's OMP toolbox. We have included the toolbox (or you can download it from here )

BibTex references

  author       = "Emadi, Mohammad and Miandji, Ehsan and Unger, Jonas",
  title        = "A Performance Guarantee for Orthogonal Matching Pursuit Using Mutual Coherence",
  journal      = "Circuits, Systems, and Signal Processing",
  number       = "4",
  volume       = "37",
  pages        = "1562--1574",
  month        = "April",
  year         = "2017"

Author publication list