Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries

摘要

We investigate the efficiency of weak orthogonal super greedy algorithm (WOSGA) for n-term approximation with respect to dictionaries which are (n, D)-unconditional in arbitrary Hilbert space H. For an element f is an element of H, let fAn be the output of WOSGA after An steps for some constant A. We show that the residual parallel to f-f(An)parallel to can be bounded by a constant multiplying the error of best n-term approximation to f. Moreover, we get an element f*(n), through a simple postprocessing of f(An) by retaining its n largest components in absolute value, which realizes near best n-term approximation for f. Our results are obtained for dictionaries in H which satisfies the weaker assumption than the RIP condition.