Almost optimality of orthogonal super greedy algorithms for incoherent dictionaries

作者：Shao, Chunfang; Ye, Peixin^*

来源：International Journal of Wavelets, Multiresolution and Information Processing, 2017, 15(4): 1750029.

DOI：10.1142/S0219691317500291

• Best n-term approximation
• weak orthogonal super greedy algorithm
• incoherent properties
• almost optimality

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.

• 出版日期2017-7
• 单位南开大学