Greedy algorithm in m-term approximation for periodic Besov class with mixed smoothness

Abstract

Nonlinear m-term approximation plays an important role in machine learning, signal processing and statistical estimating. In this paper by means of a nondecreasing dominated function, a greedy adaptive compression numerical algorithm in the best m-term approximation with regard to tensor product wavelet-type basis is proposed. The algorithm provides the asymptotically optimal approximation for the class of periodic functions with mixed Besov smoothness in the L _q norm. Moreover, it depends only on the expansion of function f by tensor product wavelet-type basis, but neither on q nor on any special features of f.

Keywords

greedy algorithm / m-term approximation / Besov space / mixed smoothness

References

[1] Barron A. R., Birgé L., Massart P. Risk bounds for model selection via penalization[J]. Probab Theory Related Fields, 1999, 113(3): 301 413

[2] Binev P., Cohen A., Dahmen W., et al. Universal algorithms for learning theory (Part I): Piecewise constant functions[J]. J Mach Learn Res, 2005, 6 1297 1321

[3] Binev P., DeVore R. Fast computation in adaptive tree approximation[J]. Numer Math, 2004, 97 193 217

[4] Birgé L., Massart P. An adaptive compresssion algrithm in Besov spaces[J]. Constr Approx, 2000, 16 1 36

[5] Wei W., Xu Y., Ye P. Adaptive algorithms of nonlinear approximation with finite terms[J]. Acta Mathematica Sinica: English Series, 2007, 23(9): 1663 1672

[6] Temlyakov V. N. Nonlinear methods of approximation[J]. Found Comput Math, 2003, 3(1): 33 107

[7] DeVore R. A., Jawerth B., Lucier B. J. Image compression through wavelet transform coding[J]. IEEE Trans Inform Theory, 1992, 38(2): 719 746

[8] DeVore R. A., Kerkyacharian G., Pard D., et al. Approximation methods for supervised learning[J]. Found Comput Math, 2006, 6(1): 3 58

[9] Dung D. Non-linear approximations using sets of finite cardinality or finite pseudo-dimension[J]. J Complexity, 2001, 17 467 492

[10] Temlyakov V. N. Greedy algorithm with regard to multivariate systems with special structure[J]. Constr Approx, 2000, 16 399 425