Moduli of smoothness andK-functionals inL p, 0<p<1

It is shown that forL _p, 0p<1, the=">K-functional betweenL _p andW _p ^r is identically zero. Useful measures that are equivalent to the moduli of smoothness are found. The equivalence results that are given are valid for 0p.Communicated by Vilmos Totik.     

Multivariate simultaneous approximation

Theorems of Jackson type are given, for the simultaneous approximation of a function of class C^m and its partial derivatives, by a polynomial and the corresponding partial derivatives.     

Rational approximation to Lipschitz and Zygmund classes

In this paper, characterizations for lim _n(R _n (f)/(n ^–1)=0 inH and for lim _n(n ^r+ R _n (f)=0 inW ^r Lip ,r1, are given, while, forZ, a generalization to a related result of Newman is established.Communicated by Ronald A. DeVore.     

On estimates of approximation numbers and best bilinear approximation

We obtain estimates of approximation numbers of integral operators, with the kernels belonging to Sobolev classes or classes of functions with bounded mixed derivatives. Along with the estimates of approximation numbers, we also obtain estimates of best bilinear approximation of such kernels.Communicated by Charles A. Micchelli.     

Weighted polynomial approximation with Freud weights

We show that ifw(x)=exp(–|x|), then in the case =1 for every continuousf that vanishes outside the support of the corresponding extremal measure there are polynomialsP _n of degree at mostn such thatw ⁿ P _n uniformly tends tof, and this is not true when <1. these=" are=" the=" missing=" cases=" concerning=" approximation=" by=" weighted=" polynomials=" of=" the=">w ⁿ P _n wherew is a Freud weight. Our second theorem shows that even if we are only interested in approximation off on the extremal support, the functionf must still vanish at the endpoints, and we actually determine the (sequence of) largest possible intervals where approximation is possible. We also briefly discuss approximation by weighted polynomials of the formW(a_nx)P _n (x).Communicated by Edward B. Saff.     

Best polynomial approximation in Sobolev-Laguerre and Sobolev-Legendre spaces

We investigate limiting behavior as γ tends to ∞ of the best polynomial approximations in the Sobolev-Laguerre space W^N,2([0, ∞); e^−x) and the Sobolev-Legendre space W^N,2([−1, 1]) with respect to the Sobolev-Laguerre inner product

Uniform rational approximation of functions with first derivative in the real hardy space ReH 1

The main result proved in the paper is: iff is absolutely continuous in (–, ) andf' is in the real Hardy space ReH ¹, then for everyn1, whereR _n(f) is the best uniform approximation off by rational functions of degreen. This estimate together with the corresponding inverse estimate of V. Russak [15] provides a characterization of uniform rational approximation.Communicated by Ronald A. DeVore.     

Convex polynomial and spline approximation in C[−1, 1]

We prove that a convex functionf C[–1, 1] can be approximated by convex polynomialsp _n of degreen at the rate of ₃(f, 1/n). We show this by proving that the error in approximatingf by C² convex cubic splines withn knots is bounded by ₃(f, 1/n) and that such a spline approximant has anL third derivative which is bounded by n³₃(f, 1/n). Also we prove that iff C²[–1, 1], then it is approximable at the rate ofn ^–2 (f, 1/n) and the two estimates yield the desired result.Communicated by Ronald A. DeVore.     

An upper bound on the approximation power of principal shift-invariant spaces

An upper bound on theL _p-approximation power (1 ≤p ≤ ∞) provided by principal shift-invariant spaces is derived with only very mild assumptions on the generator. It applies to both stationary and nonstationary ladders, and is shown to apply to spaces generated by (exponential) box splines, polyharmonic splines, multiquadrics, and Gauss kernel.     

On the L 1-condition number of the univariate Bernstein basis

We show that the size of the 1-norm condition number of the univariate Bernstein basis for polynomials of degree n is O (2ⁿ / √n). This is consistent with known estimates [3], [5] for p = 2 and p = ∞ and leads to asymptotically correct results for the p-norm condition number of the Bernstein basis for any p with 1 ≤ p ≤ ∞.     

Adaptive greedy approximations

The problem of optimally approximating a function with a linear expansion over a redundant dictionary of waveforms is NP-hard. The greedy matching pursuit algorithm and its orthogonalized variant produce suboptimal function expansions by iteratively choosing dictionary waveforms that best match the function’s structures. A matching pursuit provides a means of quickly computing compact, adaptive function approximations. Numerical experiments show that the approximation errors from matching pursuits initially decrease rapidly, but the asymptotic decay rate of the errors is slow. We explain this behavior by showing that matching pursuits are chaotic, ergodic maps. The statistical properties of the approximation errors of a pursuit can be obtained from the invariant measure of the pursuit. We characterize these measures using group symmetries of dictionaries and by constructing a stochastic differential equation model. We derive a notion of the coherence of a signal with respect to a dictionary from our characterization of the approximation errors of a pursuit. The dictionary elements slected during the initial iterations of a pursuit correspond to a function’s coherent structures. The tail of the expansion, on the other hand, corresponds to a noise which is characterized by the invariant measure of the pursuit map. When using a suitable dictionary, the expansion of a function into its coherent structures yields a compact approximation. We demonstrate a denoising algorithm based on coherent function expansions.     

Universal bases and greedy algorithms for anisotropic function classes

We suggest a three-step strategy to find a good basis (dictionary) for non-linear m-term approximation. The first step consists of solving an optimization problem of finding a near best basis for a given function class F, when we optimize over a collection D of bases (dictionaries). The second step is devoted to finding a universal basis (dictionary) D _u ∈ D for a given pair (F, D) of collections: F of function classes and D of bases (dictionaries). This means that D_u provides near optimal approximation for each class F from a collection F. The third step deals with constructing a theoretical algorithm that realizes near best m-term approximation with regard to D _u for function classes from F. In this paper we work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet-type basis and prove that it is universal. Moreover, we prove that a greedy algorithm realizes near best m-term approximation with regard to this basis for all anisotropic function classes.     

Convex polynomial and spline approximation inL p,O<p<∞

We prove that a convex functionf ∈ L _p[−1, 1], 0<p<∞, can be approximated by convex polynomials with an error not exceeding Cω ₃ ^ϕ (f,1/n)_p where ω ₃ ^ϕ (f,·) is the Ditzian-Totik modulus of smoothness of order three off. We are thus filling the gap between previously known estimates involving ω ₃ ^ϕ (f,1/n)_p, and the impossibility of having such estimates involving ω₄. We also give similar estimates for the approximation off by convexC ⁰ andC ¹ piecewise quadratics as well as convexC ² piecewise cubic polynomials. Communicated by Dietrich Braess     

Optimality and uniqueness conditions in complex rational Chebyshev approximation with examples

It is well known that best complex rational Chebyshev approximants are not always unique and that, in general, they cannot be characterized by the necessary local Kolmogorov condition or by the sufficient global Kolmogorov condition. Recently, Ruttan (1985) proposed an interesting sufficient optimality criterion in terms of positive semidefiniteness of some Hermitian matrix. Moreover, he asserted that this condition is also necessary, and thus provides a characterization of best approximants, in a fundamental case.In this paper we complement Ruttan's sufficient optimality criterion by a uniqueness condition and we present a simple procedure for computing the set of best approximants in case of nonuniqueness. Then, by exhibiting an approximation problem on the unit disk, we point out that Ruttan's characterization in the fundamental case is not generally true. Finally, we produce several examples of best approximants on a real interval and on the unit circle which, among other things, give some answers to open questions raised in the literature.     

Explicit generalized zolotarev polynomials with complex coefficients

We give explicitly a class of polynomials with complex coefficients of degreen which deviate least from zero on [−1, 1] with respect to the max-norm among all polynomials which have the same,m + 1, 2m ≤n, first leading coefficients. Form=1, we obtain the polynomials discovered by Freund and Ruschewyh. Furthermore, corresponding results are obtained with respect to weight functions of the type 1/√ρl, whereρl is a polynomial positive on [−1, 1].     

Rates of convex approximation in non-hilbert spaces

This paper deals with sparse approximations by means of convex combinations of elements from a predetermined “basis” subsetS of a function space. Specifically, the focus is on therate at which the lowest achievable error can be reduced as larger subsets ofS are allowed when constructing an approximant. The new results extend those given for Hilbert spaces by Jones and Barron, including, in particular, a computationally attractive incremental approximation scheme. Bounds are derived for broad classes of Banach spaces; in particular, forL _p spaces with 1<p<∞, theO (n ^−1/2) bounds of Barron and Jones are recovered whenp=2. One motivation for the questions studied here arises from the area of “artificial neural networks,” where the problem can be stated in terms of the growth in the number of “neurons” (the elements ofS) needed in order to achieve a desired error rate. The focus on non-Hilbert spaces is due to the desire to understand approximation in the more “robust” (resistant to exemplar noise)L _p, 1 ≤p<2, norms. The techniques used borrow from results regarding moduli of smoothness in functional analysis as well as from the theory of stochastic processes on function spaces.     

Fourier analysis of the approximation power of principal shift-invariant spaces

The approximation order provided by a directed set {S _h } _h>0 of spaces, each spanned by thehZ ^d -translates of one function, is analyzed. The nearoptimal approximants of [R2] from eachs _h to the exponential functions are used to establish upper bounds on the approximation order. These approximants are also used on the Fourier transform domain to yield approximations for other smooth functions, and thereby provide lower bounds on the approximation order. As a special case, the classical Strang-Fix conditions are extended to bounded summable generating functions.The second part of the paper consists of a detailed account of various applications of these general results to spline and radial function theory. Emphasis is given to the case when the scale {s _h } is obtained froms ₁ by means other than dilation. This includes the derivation of spectral approximation orders associated with smooth positive definite generating functions.     

Approximation in L p (R d ) from a space spanned by the scattered shifts of a radial basis function

A new multivariate approximation scheme on R ^d using scattered translates of the “shifted” surface spline function is developed. The scheme is shown to provide spectral L _p -approximation orders with 1 ≤ p ≤ ∞, i.e., approximation orders that depend on the smoothness of the approximands. In addition, it applies to noisy data as well as noiseless data. A numerical example is presented with a comparison between the new scheme and the surface spline interpolation method.     

Rational approximation in the real Hardy spaceH 2 and Stieltjes integrals: A uniquencess theorem

The paper deals with rational approximation over the real Hardy spaceH _{2, R}(V), whereV is the complement of the closed unit disk. The results concern Stieltjes functions