Randomized approximation of Sobolev embeddings, II

We study the approximation of Sobolev embeddings by linear randomized algorithms based on function values. Both the source and the target space are Sobolev spaces of non-negative smoothness order, defined on a bounded Lipschitz domain. The optimal order of convergence is determined. We also study the deterministic setting. Using interpolation, we extend the results to other classes of function spaces. In this context a problem posed by Novak and Woźniakowski is solved. Finally, we present an application to the complexity of general elliptic PDE.     

Tractability through increasing smoothness

We prove that some multivariate linear tensor product problems are tractable in the worst case setting if they are defined as tensor products of univariate problems with logarithmically increasing smoothness. This is demonstrated for the approximation problem defined over Korobov spaces and for the approximation problem of certain diagonal operators. For these two problems we show necessary and sufficient conditions on the smoothness parameters of the univariate problems to obtain strong polynomial tractability. We prove that polynomial tractability is equivalent to strong polynomial tractability, and that weak tractability always holds for these problems. Under a mild assumption, the Korobov space consists of periodic functions. Periodicity is crucial since the approximation problem defined over Sobolev spaces of non-periodic functions with a special choice of the norm is not polynomially tractable for all smoothness parameters no matter how fast they go to infinity. Furthermore, depending on the choice of the norm we can even lose weak tractability.     

A new characterization of Sobolev spaces on $${\mathbb{R}^{n}}$$

In this paper we present a new characterization of Sobolev spaces on . Our characterizing condition is obtained via a quadratic multiscale expression which exploits the particular symmetry properties of Euclidean space. An interesting feature of our condition is that depends only on the metric of and the Lebesgue measure, so that one can define Sobolev spaces of any order of smoothness on any metric measure space.     

Wavelet decompositions of L 2-functionals

Based on distribution-theoretical definitions of L ₂ and Sobolev spaces given by Werner in [P. Werner (1970). A distribution-theoretical approach to certain Lebesgue and Sobolev spaces. J. Math. Anal. Appl., 29, 19–78.] real interpolation, Besov type spaces and approximation spaces with respect to multiresolution approximations are considered. The key for the investigation are generalized moduli of smoothness introduced by Haf in [H. Haf (1992). On the approximation of functionals in Sobolev spaces by singular integrals. Applicable Analysis, 45, 295–308.]. Those moduli of smoothness allow to connect the concept of L ₂-functionals with more recent developments in multiscale analysis, see e.g. [W. Dahmen (1995). Multiscale analysis, approximation, and interpolation spaces. In: C.K. Chui and L.L. Schumaker (Eds.), Approximation Theory VIII, Vol. 2: Wavelets and Multilevel Approximation, pp. 47–88.]. In particular, we derive wavelet characterizations for the Sobolev spaces introduced by Werner and establish stable wavelet decompositions of L ₂-functionals. Generalizations to more general spaces of functionals and applications are also mentioned.     

Function spaces on fractals

We construct function spaces, analogs of Hölder-Zygmund, Besov and Sobolev spaces, on a class of post-critically finite self-similar fractals in general, and the Sierpinski gasket in particular, based on the Laplacian and effective resistance metric of Kigami. This theory is unrelated to the usual embeddings of these fractals in Euclidean space, and so our spaces are distinct from the function spaces of Jonsson and Wallin, although there are some coincidences for small orders of smoothness. We show that the Laplacian acts as one would expect an elliptic pseudodifferential operator of order d+1 on a space of dimension d to act, where d is determined by the growth rate of the measure of metric balls. We establish some Sobolev embedding theorems and some results on complex interpolation on these spaces.     

Optimized Tensor-Product Approximation Spaces

This paper is concerned with the construction of optimized grids and approximation spaces for elliptic differential and integral equations. The main result is the analysis of the approximation of the embedding of the intersection of classes of functions with bounded mixed derivatives in standard Sobolev spaces. Based on the framework of tensor-product biorthogonal wavelet bases and stable subspace splittings, the problem is reduced to diagonal mappings between Hilbert sequence spaces. We construct operator adapted finite element subspaces with a lower dimension than the standard full-grid spaces. These new approximation spaces preserve the approximation order of the standard full-grid spaces, provided that certain additional regularity assumptions are fulfilled. The form of the approximation spaces is governed by the ratios of the smoothness exponents of the considered classes of functions. We show in which cases the so-called curse of dimensionality can be broken. The theory covers elliptic boundary value problems as well as boundary integral equations. September 17, 1998. Date revised: March 5, 1999. Date accepted: September 20, 1999.     

Characterization of Sobolev spaces of arbitrary smoothness using nonstationary tight wavelet frames

In this paper we shall characterize Sobolev spaces of an arbitrary order of smoothness using nonstationary tight wavelet frames for L ₂(ℝ). In particular, we show that a Sobolev space of an arbitrary fixed order of smoothness can be characterized in terms of the weighted ℓ₂-norm of the analysis wavelet coefficient sequences using a fixed compactly supported nonstationary tight wavelet frame in L ₂(ℝ) derived from masks of pseudosplines in [15]. This implies that any compactly supported nonstationary tight wavelet frame of L ₂(ℝ) in [15] can be properly normalized into a pair of dual frames in the corresponding pair of dual Sobolev spaces of an arbitrary fixed order of smoothness. Research supported in part by NSERC Canada under Grant RGP 228051. Research supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

Sobolev embedding theorems for a class of anisotropic irregular domains

Sufficient conditions for the embedding of a Sobolev space in Lebesgue spaces on a domain depend on the integrability and smoothness parameters of the spaces and on the geometric features of the domain. In the present paper, Sobolev embedding theorems are obtained for a class of domains with irregular boundary; this class includes the well-known classes of σ-John domains, domains with the flexible cone condition, and their anisotropic analogs.     

Continuous Algorithms in n-Term Approximation and Non-Linear Widths

In the present paper we investigate optimal continuous algorithms in n-term approximation based on various non-linear n-widths, and n-term approximation by the dictionary V formed from the integer translates of the mixed dyadic scales of the tensor product multivariate de la Vallée Poussin kernel, for the unit ball of Sobolev and Besov spaces of functions with common mixed smoothness. The asymptotic orders of these quantities are given. For each space the asymptotic orders of non-linear n-widths and n-term approximation coincide. Moreover, these asymptotic orders are achieved by a continuous algorithm of n-term approximation by V, which is explicitly constructed.     

Spaces of functions of positive smoothness on irregular domains

The paper is devoted to constructing and studying spaces of functions of positive smoothness on irregular domains of the n-dimensional Euclidean space. We prove embedding theorems that connect the spaces introduced with the Sobolev and Lebesgue spaces. The formulations of the theorems depend on geometric parameters of the domain of definition of functions.     

A note on adaptive approximation in Sobolev spaces

In this article, we consider the adaptive approximation in Sobolev spaces. After establishing some norm equivalences and inequalities in Besov spaces, we are able to prove that the best N terms approximation with wavelet‐like basis in Sobolev spaces exhibits the proper approximation order in terms of N^?1. This indicates that the computational load in adaptive approximation is proportional to the approximation accuracy. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Decomposition theorems and approximation by a ``floating" system of exponentials

The main problem considered in this paper is the approximation of a trigonometric polynomial by a trigonometric polynomial with a prescribed number of harmonics. The method proposed here gives an opportunity to consider approximation in different spaces, among them the space of continuous functions, the space of functions with uniformly convergent Fourier series, and the space of continuous analytic functions. Applications are given to approximation of the Sobolev classes by trigonometric polynomials with prescribed number of harmonics, and to the widths of the Sobolev classes. This work supplements investigations by Maiorov, Makovoz and the author where similar results were given in the integral metric.

     

On hyperbolic summation and hyperbolic moduli of smoothness

This paper deals with the method of hyperbolic summation of tensor product orthogonal spline functions onI ^d. The spaces, defined in terms of the order of the best approximation by the elements of the space spanned by the tensor product functions with indices from a given hyperbolic set, are described both in terms of the coefficients in some basis and as interpolation spaces. Moreover, the hyperbolic modulus of smoothness is studied, and some relations between hyperbolic summation and hyperbolic modulus of smoothness are established.     

Traces of weighted function spaces: Dyadic norms and Whitney extensions

The trace spaces of Sobolev spaces and related fractional smoothness spaces have been an active area of research since the work of Nikolskii, Aronszajn, Slobodetskii, Babich and Gagliardo among others in the 1950’s. In this paper, we review the literature concerning such results for a variety of weighted smoothness spaces. For this purpose, we present a characterization of the trace spaces (of fractional order of smoothness), based on integral averages on dyadic cubes, which is well-adapted to extending functions using the Whitney extension operator.     

Kernel based approximation in Sobolev spaces with radial basis functions

In this paper, we study several radial basis function approximation schemes in Sobolev spaces. We obtain an optional error estimate by using a class of smoothing operators. We also discussed sufficient conditions for the smoothing operators to attain the desired approximation order. We then construct the smoothing operators by some compactly supported radial kernels, and use them to approximate Sobolev space functions with optimal convergence order. These kernels can be simply constructed and readily applied to practical problems. The results show that the approximation power depends on the precision of the sampling instrument and the density of the available data.     

Bessel generalized translations and some problems of approximation theory for functions on the half-line

Approximation problems for functions on the half-line [0,+∞) in a weighted L _p -metric are studied with the use of Bessel generalized translation. A direct theorem of Jackson type is proven for the modulus of smoothness of arbitrary order which is constructed on the basis of Bessel generalized translation. Equivalence is stated between the modulus of smoothness and the K-functional constructed by the Sobolev space corresponding to the Bessel differential operator. A particular class of entire functions of exponential type is used for approximation. The problems under consideration are studied mostly by means of Fourier-Bessel harmonic analysis.     

Another note on the embedding of the Sobolev space for the limiting exponent

The embedding of the Sobolev spaces W _p ^s (? ⁿ ) in a Lizorkin-type space of locally summable functions of zero smoothness is established. This result is extended to the case of the embedding of Sobolev spaces on nonregular domains of n-dimensional Euclidean space. The formulation of the theorem depends on the geometric parameters of the domain of the functions.     

To the Sobolev embedding theorem for the limiting exponent

We establish embeddings of the Sobolev space W _p ^s and the space B _pq ^s (with the limiting exponent) in certain spaces of locally integrable functions of zero smoothness. This refines the embedding of the Sobolev space in the Lorentz and Lorentz-Zygmund spaces. Similar problems are considered for the case of irregular domains and for the potential space.     

Function spaces of variable smoothness and integrability

In this article we introduce Triebel-Lizorkin spaces with variable smoothness and integrability. Our new scale covers spaces with variable exponent as well as spaces of variable smoothness that have been studied in recent years. Vector-valued maximal inequalities do not work in the generality which we pursue, and an alternate approach is thus developed. Using it we derive molecular and atomic decomposition results and show that our space is well-defined, i.e., independent of the choice of basis functions. As in the classical case, a unified scale of spaces permits clearer results in cases where smoothness and integrability interact, such as Sobolev embedding and trace theorems. As an application of our decomposition we prove optimal trace theorem in the variable indices case.     

Discrete gevrey regularity attractors and uppers–semicontinuity for a finite difference approximation to the ginzburg–landau equation

A semi-discrete spatial finite difference approximation to the complex Ginzburg-Landau equation with cubic non-linearity is considered. Using the fractional powers of a sectorial operator, discrete versions of the Sobolev spaces H ⁵, and Gevrey classes of regularityG, are introduced.Discrete versions of some standard Sobolev space norm inequalities are proved.