Saturday, February 23, 2008

Compressed Sensing: Faster is Good, but now Greedier is Better.


Another paper from the Rice repository that was not mentioned before. It was written by Anna Gilbert and Joel Tropp, and touches on an on-going concern that greedy reconstruction algorithms need more measurements than traditional l1 based or basis pursuit methods in order to obtain the same results. In Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit, it seems the problem has been solved.
This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with m nonzero entries in dimension d given O(mln d) random linear measurements of that signal. This is a massive improvement over previous results, which require O(m2) measurements. The new results for OMP are comparable with recent results for another approach called Basis Pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.
In other words, we now seem to have a fast greedy algorithm that requires as many measurements to obtain the same result. This is good news and seems an improvement on the already excellent results of Deanna Needell and Roman Vershynin in Signal recovery from incomplete and inaccurate measurements via Regularized Orthogonal Matching Pursuit.

Credit photo: NASA/JPL/Space Science Institute, Dione, a moon of Saturn photographed the day before yesterday by the Cassini probe.

2 comments:

Anonymous said...

Hi Igor,

I think that the result of Tropp and Gilbert is somewhat different from the result of Needell and Vershynin qualitatively.
More precisely, for a given s-sparse signal, OMP will recover it with high probability under certain conditions ... but can never recover all s-sparse signals. On the other hand ROMP can under some conditions.

Also, if I recall, the required dimensions of the matrix are different.

In other words, the ROMP result is of the flavor of the basis pursuit results of Candes, Romberg and Tao (possibly with a price paid in the dimensions), which is not the case for the OMP result; it does not provide a uniform guarantee.

Igor said...

Thanks Rayan. I guess at some point somebody will make all these statements clearer so that newcomers have a small learning curve about what to expect or not from these results.


Igor.

Printfriendly