The main goal of this paper is to understand which properties of a basis are important for certain direct and inverse theorems in nonlinear approximation. We study greedy approximation with regard to bases with different properties. We consider bases that are tensor products of univariate greedy bases. Some results known for unconditional bases are extended to the case of quasi-greedy bases.

We study the approximation of the imbedding of functions from anisotropic and generalized Sobolev classes into Lq([0, 1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from LNp to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wrp ([0, 1]d)) to Lq([0, 1]d) space for all 1 6 q; p 6 1 and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.

In this paper we investigate the probabilistic linear (n, δ)-widths and paverage linear n-widths of the Sobolev space Wr 2 equipped with the Gaussian measure μ in the L∞-norm, and determine the asymptotic equalities λn,δ(Wr 2,μ, L∞) =开方( ln(n/δ)/ nr+(s−1)/2 , λ(a) n (Wr 2,μ, L∞)p=开方ln n/ nr+(s−1)/2 , 0 < p < ∞.

Let B := (B, || · ||b) be a Banach space and H := (H, || · ||h) a dense subspace of B. We are interested in the rate at which the distance of a given x∈ B from the ball of radius t in H tends to zero as t →1. This problem has numerous applications and its recent importance in the Cucker Smale theory of learning renewed our interest in this subject. We study two aspects of this problem. First, we obtain general results on the relation between the CS-functional and the Peetre K-functional. Secondly, we estimate it in the concrete case of Besov spaces by using functions of exponential type.

We determine the exact order of ε-complexity of the numerical integration problem for the anisotropic class Wr∞ (I d ) and Hr∞ (I d ) with respect to the worst case randomized methods and the average case deterministic methods. We prove this result by developing a decomposition technique of Borel measure on unit cube of d-dimensional Euclidean space. Moreover by the imbedding relationship between function classes we extend our results to the classes of functions W^ p (I d ) and H^ p (I d ). By the way we highlight some typical results and stress the importance of some open problems related to the complexity of numerical integration.