Sparse approximation and recovery by greedy algorithms
For researchers in sparse approximation and compressed sensing, the paper provides theoretical guarantees for greedy algorithms, extending results to Banach spaces and improving probabilistic recovery bounds.
The paper proves that Orthogonal Matching Pursuit (OMP) recovers random K-sparse signals exactly within K(1+ε) iterations with high probability, and establishes Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm in Banach spaces.
We study sparse approximation by greedy algorithms. Our contribution is two-fold. First, we prove exact recovery with high probability of random $K$-sparse signals within $\lceil K(1+\e)\rceil$ iterations of the Orthogonal Matching Pursuit (OMP). This result shows that in a probabilistic sense the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm, a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space our results add some new elements to known results on the Lebesque-type inequalities for the RIP dictionaries. Our technique is a development of the recent technique created by Zhang.