Sparse approximation and recovery by greedy algorithms in Banach spaces
This work addresses sparse approximation problems for researchers in approximation theory and signal processing by extending greedy algorithms from Hilbert to Banach spaces, though it is incremental as it builds on existing methods in a new setting.
The paper tackles sparse approximation in Banach spaces by analyzing the Weak Chebyshev Greedy Algorithm (WCGA), proving Lebesgue-type inequalities for redundant dictionaries and applying them to bases, showing that WCGA provides almost optimal sparse approximation for the trigonometric system in L_p spaces with 2 ≤ p < ∞.
We study sparse approximation by greedy algorithms. We prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm (WCGA), 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. The results are proved for redundant dictionaries satisfying certain conditions. Then we apply these general results to the case of bases. In particular, we prove that the WCGA provides almost optimal sparse approximation for the trigonometric system in $L_p$, $2\le p<\infty$.