Information Technology Journal

Year: 2014 | Volume: 13 | Issue: 6 | Page No.: 1262-1266
DOI: 10.3923/itj.2014.1262.1266

The Exact Bounds of Randomized Widths for Generalized Besov Classes

Duan Liqin and Ye Peixin

Abstract: We reformulate the widths problem in the framework of information-based complexity theory and study the Kolmogorov width and linear width for the generalized Besov classes in the randomized setting. Applying the discretization technique and some properties of pseudo-s-scale, we determine the exact asymptotic orders of these widths on these classes for certain values of the parameters p, q, θ. Our results show that the Monte Carlo methods lead to a better convergence rate than that of the deterministic ones for some parameters p, q. The maximal gain can reach a factor n^-1/2 roughly.

Keywords: information-based complexity, Randomized widths, generalized besov class and asymp-totic order

INTRODUCTION

In approximation theory, an important problem is to find for a fixed class of functions a system of functions which is well adapted for approximating the functions from the class involved. It is natural to ask how to compare methods of approximation and how to determine an optimal method. This led to the notions of various widths. The idea of width was originally due to A.N. Kolmogorov. Subsequently, V.M. Tikhomirov’s work made this direction active. The main task of widths is to construct the best approximations and determine the asymptotic orders of optimal errors for various classes of functions. It is well known that the calculation of widths plays a dominant role in numerical analysis, information-based complexity and approximation theory. Moreover, widths have close relations to many optimal problems such as ε-complexity of approximation and integration, optimal differentiation and optimal approximate solutions of the classes of operator equations. The extensive literature devoted to the calculation of the widths on some important classes of non-periodic or periodic functions, such as the Sobolev classes, the Besov classes and the classes of analytic functions etc., For the details about the history, applications and the results of n-widths on various classes, one can refer to Temlyakov (1994) and Pinkus (1985) and the references therein. While one of most intensively disputed questions of computational mathematics is the following: What is the superiority of Monte Carlo methods compared with deterministic methods, i.e., can it be of help to involve randomness into numerical processes and if yes, in which situations is this advisable? The first results about the analysis of efficiency of randomized (Monte Carlo) methods were due to Bakhvalov , while an intensive wider research started only after the theory of information-based complexity (Traub et al., 1988) was established. The theory of information-based complexity has created notions and tools to understand the efficiency issues both for deterministic and Monte Carlo methods. In this way some comparison between the deterministic and the Monte Carlo settings becomes possible. So, many authors have investigated the complexity of problems on function approximation. In particular, Mathe (1994) and Heinrich (1994) studied the approximation problems on the classical multivariate Sobolev space in the norm of L_p ([0.1]^d) by different methods in the deterministic and the Monte Carlo settings. Fang and Duan (2008) studied the approximation for the Sobolev classes with bounded mixed derivative by linear randomized methods.

Motivated by the above results we consider the approximation on Besov class which is much more general than Sobolev class. It is also well-known that the Besov classes of functions play an important role in the approximation theory and solutions of differential and integral equations and many other fields of applied mathematics. Exploiting the work of Mathe on finite randomized widths, we obtain the exact orders for Kolmogorov and linear widths on these classes in the randomized setting. Comparing our results with the known results on deterministic widths, (Xu, 2005), one can see that the Monte Carlo methods outperform the deterministic ones for some parameters p, q.

NOTIONS OF INFORMATION-BASED COMPLEXITY AND WIDTHS

Let X, Y be Banach spaces and X₀ be the unit ball of X. Let S be a continuous operator from X₀ to Y. Let R^d be the d-dimensional Euclidean space. We seek to approximate S by mappings of the form μ = N, where N: X₀→Rⁿ, φ: N(X₀)→Y. N and φ describe a numerical method. We mainly consider the following classes of methods. For fixed k∈N, a rule μ: X₀→Y of the form μ = φ°N is said to be a Kolmogorov method, if the information operator N is an arbitrary mapping from to X₀ to R^k and φ extends to a linear mapping from R^k to Y, a linear method, if the information operator N is the restriction of a continuous linear mapping from X₀ to R^k and φ extends to a linear mapping from R^k to Y.

Let D_k(X₀, Y), A_k(X₀, Y) denote the sets of all Kolmogorov and linear methods which have cardinality equal to k, respectively and put:

such that:

give rise to the respective classes of Kolmogorov and linear methods. Denote by any of the classes of Kolmogorov and linear methods in this study.

The worst case error of any method is measured by:

Minimizing the errors with respect to the choice of methods within the given class, we get the n-th minimal error defined by:

Denote:

Next, we pass to the randomized setting. We assume that both X₀ and Y are equipped with their respective Borel σ-algebras and i.e., the σ-algebras generated by the open sets.

Definition 1: (Mathe, 1994). Given a class of methods , a triple is called an -monte Carlo method, if :

The error of a Monte Carlo method is defined as:

with the cardinality:

The n-th Monte Carlo error is defined as:

Denote:

RESULTS

We first recall the definition of generalized Besov class from Xu (2005). Denote by L_p(T^d), 1≤p≤∞, the space of p-th powers Lebesgue integrable functions defined on the torus T^d = [0, 2π]^d, which are 2π-periodic in each variable with the usual norm ||.||_p. For k∈N and h∈R^d, define the k-th difference of f as:

The k-th modulus of smoothness Ω_k (f, t)_p of f is defined by:

Definition 2: Let Ω denote a non-negative function on R⁺ = {t: t≥0}. We say that Ω(t)∈Φ^*_k if it satisfies:

Definition 3: Let, k∈N, Ω(t)∈Φ^*_k, 1≤θ≤∞ and 1≤p≤∞. We say if f satisfies the following conditions:

where:

The space is a normed linear space with the norm:

When Ω(t) = t^α, is the usual Besov space .

Let l denote the identical imbedding operator from the unit ball of to L_q(T^d). For two nonnegative sequences {α_n}_n∈N and {b_n}_n∈N, α_n<<b_n and α_n>>b_n mean that there are positive number c_1, c₂ which may depend on p,q,Ω,d independent of n such that α_n≤c₁b_n and α_n≤c₂b_n for all n. The relation α_n><b_n means that α_n<<b_n and α_n>>b_n. So the results of Xu Guiqiao about the deterministic widths can be stated as follows:

Theorem 1 (Xu, 2005): Suppose that k∈N, Ω(t)∈Φ^*_k , 1≤θ≤∞, Ω(t)/t^a is almost increasing and a>d max(7/12-3/p, 1/2+3/q,1/p-1/q). Then:

Our main result is the following theorem.

Theorem 2: Suppose that k∈N, Ω(t)∈Φ^*_k, 1≤θ≤∞, Ω(t)/t^a is almost increasing and a>d(7/2-3/p, 1/2+3/q,1/p-1/q). Then:

Comparing Theorem 2 with Theorem 1, one can see that the randomized methods lead to considerably better rates than those of the deterministic ones in some cases. Quantitatively, the maximal gain can reach a factor n^-1/2 roughly.

PROOF OF MAIN RESULT

Our proof of main result is based on the discretization technique and some properties of pseudo-s-scale. So we first recall the definition of pseudo-s-scale.

Definition 4 (Pietsch, 1978): A map s assigning to every S∈L (X,Y) a sequence {sn(S)}_n∈N is called a pseudo-s-scale if the following properties are satisfied:

for all Banach spaces X’,Y’ and operators U∈L(X’, X), V∈L(Y, Y’).

It is easy to check that the quantities and are pseudo-s-scales. To prove Theorem 2, we will use the discretization technique to reduce the estimates of the widths of the class to those of finite-dimensional Euclidean spaces. We first recall some notations and lemmas.

We recall a representation theorem for which is essentially due to Nikolskii. This theorem plays a cruel role in our analysis. For m∈N, let:

be the one-dimensional de la Vallee Poussin kernel and define the d-dimensional de la Vallee Poussin kernel by:

For , recall its de la Vallee Poussin sum which is defined by , where * is the convolution operator. The differences of successive de la Vallee Poussin sums are defined by:

Theorem 3: If , and , then f can be represented in the form of a series:

convergencing to it in the norm of and:

Let denote the space of all vectors x∈R^m equipped with the usual norm. Let to denote the identical imbedding mapping from the unit ball of to . Based on Theorem 3, using the technique by Mathe (1994) and (Xu, 2005), it is not difficult to prove the following lemmas. Here we will omit the details of proofs.

Lemma 1: Let p<q, Ω(t)/t^a be almost increasing a>d(1/p-1/q)and s_n denote any of quantities:

Then:

where, the n_k are non-negative integers with:

Lemma 2: Let Ω(t)/t^a be almost increasing and s_n denote any of quantities . Then:

To proceed the process of the discretization, we need the following results about the randomized widths of the finite-dimension space lⁿ_p.

Lemma 3 (Mathe, 1994): For 1≤p≤2 and 1≤n≤m , we have the estimate:

Lemma 4 (Mathe, 1994): For any n∈N, there exist a constant c>0 and r’∈Nfor which:

Where:

Lemma 5 (Temlyakov, 1994): Let 1<p<q≤∞ and f∈L_p. Then:

Proof of theorem 2: It is clear that:

So, it suffices to prove the upper bound for and the lower bound for .

We start with the upper estimate. By the relation

and Theorem 1, we only need to estimate the upper bounds for 2≤p<q<∞ and 1<p<2≤q<∞, p'≤q

First, we consider 2≤q<p<∞. In this case, it suffices to estimate the upper bounds for .

By Lemma 1, we have:

For a given nεN, we choose mεM such that 2^mxn^Vd and set:

where, 0<β<2α/d-1. Thus, we have:

By lemma 3 and the n_k defined above, we can obtain from Eq. 1 at:

We get the required estimates for 2≤p<q<∞.

Second, we consider 1<p<2≤q<∞, p'≤q. By the relation, (Xu, 2005) and the above result, we can obtain the desired upper bounds.

Now we pass to the lower estimates. According to lemma 2, we have:

For r' in lemma 4, we choose a number m such that 2n^md≥r' n. We continue to estimate the lower bounds. First, let 1<q≤p<∞. Obviously, it suffices to prove the lower bounds for 1<q≤2≤p<∞. By Eq. 2 and Lemma 4, we get:

Next, let 1<p<q<∞. We will divide three cases to estimate the lower bounds. For 1<p<2≤q<∞, we only need to consider the case 1<p<2 and q = 2. Equation 2 and lemma 4 again give that:

For 2≤p<q<∞, the relation , where and (3) imply the required lower bounds. It remains to estimate the lower bounds for 1<p<q<2. In fact, we have already proved that:

By lemma 5 and Eq. 4, we obtain:

The proof of theorem 2 is complete.

ACKNOWLEDGMENTS

The authors are grateful to the referees for their valuable suggestions. This work was supported in part by the Natural Science Foundation of China (Grant No. 11201104, 10971251 and 11271199).

REFERENCES