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.     

Sobolev embeddings, extensions and measure density condition

There are two main results in the paper. In the first one, Theorem 1, we prove that if the Sobolev embedding theorem holds in Ω, in any of all the possible cases, then Ω satisfies the measure density condition. The second main result, Theorem 5, provides several characterizations of the Wm,p-extension domains for 1<p<∞. As a corollary we prove that the property of being a W1,p-extension domain, 1<p?∞, is invariant under bi-Lipschitz mappings, Theorem 8.     

Optimal Gaussian Sobolev embeddings

A reduction theorem is established, showing that any Sobolev inequality, involving arbitrary rearrangement-invariant norms with respect to the Gauss measure in Rn, is equivalent to a one-dimensional inequality, for a suitable Hardy-type operator, involving the same norms with respect to the standard Lebesgue measure on the unit interval. This result is exploited to provide a general characterization of optimal range and domain norms in Gaussian Sobolev inequalities. Applications to special instances yield optimal Gaussian Sobolev inequalities in Orlicz and Lorentz(-Zygmund) spaces, point out new phenomena, such as the existence of self-optimal spaces, and provide further insight into classical results.     

Riesz potential and Sobolev embeddings on generalized Lebesgue and Sobolev spaces Lp(·) and Wk,p(·)

We study the Riesz potentials I_αf on the generalized Lebesgue spaces L^p(·)(?^d), where 0 < α < d and I_αf(x) ? ∫equation/tex2gif-inf-3.gif |f(y)| |x – y|^{α – d} dy. Under the assumptions that p locally satisfies |p(x) – p(x)| ≤ C/(– ln |x – y|) and is constant outside some large ball, we prove that I_α : L^p(·)(?^d) → L^p?(·)(?^d), where . If p is given only on a bounded domain Ω with Lipschitz boundary we show how to extend p to on ?^d such that there exists a bounded linear extension operator ? : W^1,p(·)(Ω) ? (?^d), while the bounds and the continuity condition of p are preserved. As an application of Riesz potentials we prove the optimal Sobolev embeddings W^k,p(·)(?^d) ?L^p*(·)(R^d) with and W^1,p(·)(Ω) ? L^p*(·)(Ω) for k = 1. We show compactness of the embeddings W^1,p(·)(Ω) ? L^q(·)(Ω), whenever q(x) ≤ p*(x) – ε for some ε > 0. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Uniform B-spline approximation in Sobolev spaces

A new method for approximating functions by uniform B-splines is presented. It is based on the orthogonality relations for uniform B-splines in weighted Sobolev spaces, as introduced in (Reif, 1997). The scheme is local and the approximation order is optimal. Moreover, also constrained approximation problems can be solved efficiently; the size of the linear system to be solved is given by the number of constraints. Applying the method to spline conversion problems specifies new weights for knot removal and degree reduction. This revised version was published online in August 2006 with corrections to the Cover Date.     

Symmetrization inequalities and Sobolev embeddings

We prove new extended forms of the Pólya-Szegö symmetrization principle. As a consequence new sharp embedding theorems for generalized Besov spaces are proved, including a sharpening of the limiting cases of the classical Sobolev embedding theorem. In particular, a surprising self-improving property of certain Sobolev embeddings is uncovered.

     

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     

A note on extreme cases of Sobolev embeddings

We study the spaces of functions on for which the generalized partial derivatives exist and belong to different Lorentz spaces L^p_k,s_k. For this kind of functions we prove a sharp version of the extreme case of the Sobolev embedding theorem using L(∞,s) spaces.     

Different degrees of non-compactness for optimal Sobolev embeddings

The structure of non-compactness of optimal Sobolev embeddings of m-th order into the class of Lebesgue spaces and into that of all rearrangement-invariant function spaces is quantitatively studied. Sharp two-sided estimates of Bernstein numbers of such embeddings are obtained. It is shown that, whereas the optimal Sobolev embedding within the class of Lebesgue spaces is finitely strictly singular, the optimal Sobolev embedding in the class of all rearrangement-invariant function spaces is not even strictly singular.     

An improved approximation algorithm for the partial Latin square extension problem

Previous work on the partial Latin square extension (PLSE) problem resulted in a 2-approximation algorithm based on the LP relaxation of a three-dimensional assignment IP formulation. We present an e/(e−1)-approximation algorithm that is based on the LP relaxation of a packing IP formulation of the PLSE problem.     

Approximation in Sobolev spaces by piecewise affine interpolation

Functions in a Sobolev space are approximated directly by piecewise affine interpolation in the norm of the space. The proof is based on estimates for interpolations and does not rely on the density of smooth functions.     

Stability Implies Convergence of Cascade Algorithms in Sobolev Space

This article proves that the stability of the shifts of a refinable function vector ensures the convergence of the corresponding cascade algorithm in Sobolev space to which the refinable function vector belongs. An example of Hermite interpolants is presented to illustrate the result.     

Best constants and minimizers for embeddings of second order Sobolev spaces

By considering the kernels of the first two traces, four different second order Sobolev spaces may be constructed. For these spaces, embeddings into Lebesgue spaces, the best embedding constant and the possible existence of minimizers are studied. The Euler equation corresponding to some of these minimization problems is a semilinear biharmonic equation with boundary conditions involving third order derivatives: it is shown that the complementing condition is satisfied.     

优化Sobolev体及其仿射性质

Sobolev不等式是联系分析和几何的基础不等式之一,而优化Sobolev体是优化Sobolev范数的临界几何核.首先,证明优化Sobolev体的一些仿射性质.然后,运用Barthe的优化迁移方法研究了凸体的特征函数和多胞形仿射函数的优化Sobolev体.     

On a rearrangement-invariant function set that appears in optimal Sobolev embeddings

We give necessary and sufficient conditions for the set of measurable functions to be a normable linear space. We also give a complete characterization of all spaces B that can be represented in the form B=Y(A) for some space A and of all spaces A that can appear in such representations.     

Gelfand and Kolmogorov numbers of Sobolev embeddings of weighted function spaces

In this paper we study the Gelfand and Kolmogorov numbers of Sobolev embeddings between weighted function spaces of Besov and Triebel–Lizorkin type with polynomial weights. The sharp asymptotic estimates are determined in the so-called non-limiting case.