Lower bounds for multivariate approximation by affine-invariant dictionaries

The problem of approximating locally smooth multivariate functions by linea r combinations of elements from an affine-invariant redundant dictionary is considered. Augmenting recent upper bound results for approximation, we es tablish lower bounds on the performance of such schemes. The lower bounds a re tight to within a logarithmic factor in the number of elements used in t he approximation. Using a recently introduced notion of nonlinear approxima tion, we show that the approximation ability may be completely characterize d by the pseudodimension of the approximation space with respect to a finit e set of points. This result establishes a useful link between the problems of approximation and estimation, or learning, the latter often being conve niently characterized, at least in terms of upper bounds, by the pseudodime nsion.