On efficiency of Orthogonal Matching Pursuit

Abstract: We show that if a matrix

P h i

satisfies the RIP of order

[C K^{1.2}]

with isometry constant

d t = c K^{- 0.2}

and has coherence less than

1 / (20 K^{0.8})

, then Orthogonal Matching Pursuit (OMP) will recover

K

-sparse signal

x

from

y = P h i x

in at most

[C K^{1.2}]

iterations. This result implies that

K

-sparse signal can be recovered via OMP by

M = O (K^{1.6} l o g N)

measurements.

This page was built for publication: On efficiency of Orthogonal Matching Pursuit