# Sufficient conditions for exact signal recovery using OMP?

For a compressive sensing model : $$y_{_{MXN}}=A_{_{MXN}}x_{_{NX1}}$$
where $x$ is $K$ sparse, what is the sufficient condition for Orthogonal matching Pursuit (OMP) to exactly recover the data for both noisy and noiseless case ?

There are multiple statements, like

• $M>Klog(N-K)$ ;
• $M>Klog(N/K)$ ;
• $M>2Klog(N-K)$ ;
• somewhere it's $M>4Klog(N-K)$.

Should there be some constant ratio between $M$ and $N$?