Greedy algorithms with regard to multivariate systems with special structure

The question of finding an optimal dictionary for nonlinear m-term approxim ation is studied in this paper. We consider this problem in the periodic mu ltivariate (d variables) case for classes of functions with mixed smoothnes s. We prove that the well-known dictionary U-d which consists of trigonomet ric polynomials (shifts of the Dirichlet kernels) is nearly optimal among o rthonormal dictionaries. Next, it is established that for these classes nea r-best m-term approximation, with regard to Ud, can be achieved by simple g reedy-type (thresholding-type) algorithms. The univariate dictionary U is used to construct a dictionary which is opti mal among dictionaries with the tensor product structure.