Orthogonal Matching Pursuit: A Brownian Motion Analysis

摘要

A well-known analysis of Tropp and Gilbert shows that orthogonal matching pursuit (OMP) can recover a $k$-sparse $n$-dimensional real vector from $m=4klog(n)$ noise-free linear measurements obtained through a random Gaussian measurement matrix with a probability that approaches one as $nrightarrowinfty$. This work strengthens this result by showing that a lower number of measurements, $m=2klog(n-k)$ , is in fact sufficient for asymptotic recovery. More generally, when the sparsity level satisfies $k_{min}leq kleq k_{max}$ but is unknown, $m=2k_{max}log(n-k_{min})$ measurements is sufficient. Furthermore, this number of measurements is also sufficient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to infinity. The scaling $m=2klog(n-k)$ exactly matches the number of measurements required by the more complex lasso method for signal recovery with a similar SNR scaling.