Optimal adaptive sampling recovery

Abstract

We propose an approach to study optimal methods of adaptive sampling recovery of functions by sets of a finite capacity which is measured by their cardinality or pseudo-dimension. Let W ?? Lq, 0 < q ?? ??, be a class of functions on {Mathematical expression}. For B a subset in Lq, we define a sampling recovery method with the free choice of sample points and recovering functions from B as follows. For each f ?? W we choose n sample points. This choice defines n sampled values. Based on these sampled values, we choose a function from B for recovering f. The choice of n sample points and a recovering function from B for each f ?? W defines a sampling recovery method {Mathematical expression} by functions in B. An efficient sampling recovery method should be adaptive to f. Given a family {Mathematical expression} of subsets in Lq, we consider optimal methods of adaptive sampling recovery of functions in W by B from {Mathematical expression} in terms of the quantity {Mathematical expression}Denote {Mathematical expression} by en(W)q if {Mathematical expression} is the family of all subsets B of Lq such that the cardinality of B does not exceed 2n, and by rn(W)q if {Mathematical expression} is the family of all subsets B in Lq of pseudo-dimension at most n. Let 0 < p, q, ?? ?? ?? and ? satisfy one of the following conditions: (i) ? > d/p; (ii) ? = d/p, ?? ?? min (1, q), p, q < ?? . Then for the d-variable Besov class {Mathematical expression} (defined as the unit ball of the Besov space {Mathematical expression}), there is the following asymptotic order {Mathematical expression}To construct asymptotically optimal adaptive sampling recovery methods for {Mathematical expression} and {Mathematical expression} we use a quasi-interpolant wavelet representation of functions in Besov spaces associated with some equivalent discrete quasi-norm. ?? 2009 Springer Science+Business Media, LLC.