Computer Science – Information Theory
Scientific paper
2011-05-30
Computer Science
Information Theory
11 pages, 2 figures
Scientific paper
A well-known analysis of Tropp and Gilbert shows that orthogonal matching pursuit (OMP) can recover a k-sparse n-dimensional real vector from 4 k log(n) noise-free linear measurements obtained through a random Gaussian measurement matrix with a probability that approaches one as n approaches infinity. This work strengthens this result by showing that a lower number of measurements, 2 k log(n - k), is in fact sufficient for asymptotic recovery. More generally, when the sparsity level satisfies kmin <= k <= kmax but is unknown, 2 kmax log(n - kmin) 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 2 k log(n - k) exactly matches the number of measurements required by the more complex lasso method for signal recovery with a similar SNR scaling.
Fletcher Alyson K.
Rangan Sundeep
No associations
LandOfFree
Orthogonal Matching Pursuit: A Brownian Motion Analysis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Orthogonal Matching Pursuit: A Brownian Motion Analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orthogonal Matching Pursuit: A Brownian Motion Analysis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-677333