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.     

An Adaptive Compression Algorithm in Besov Spaces

Given a function f on [0,1] and a wavelet-type expansion of f , we introduce a new algorithm providing an approximation $\tilde f of f with a prescribed number D of nonzero coefficients in its expansion. This algorithm depends only on the number of coefficients to be kept and not on any smoothness assumption on f . Nevertheless it provides the optimal rate D ^-α of approximation with respect to the L _q -norm when f belongs to some Besov space B ^α _p,∈fty whenever α>(1/p-1/q) ⁺ . These results extend to more general expansions including splines and piecewise polynomials and to multivariate functions. Moreover, this construction allows us to compute easily the metric entropy of Besov balls. June 21, 1996. Dates revised: April 9, 1998; October 14, 1998. Date accepted: October 20, 1998.     

A discrepancy theorem concerning polynomials of best approximation inL w p [−1, 1]

Letw be a suitable weight function,B _n,p denote the polynomial of best approximation to a functionf inL _w ^p [–1, 1],v _n be the measure that associates a mass of 1/(n+1) with each of then+1 zeros ofB _n+1,p–B _n,p and be the arcsine measure defined by . We estimate the rate at which the sequencev _n converges to in the weak-^* topology. In particular, our theorem applies to the zeros of monic polynomials of minimalL _w ^p norm.This author gratefully acknowledges partial support from NSA contract #A4235802 during 1992, AFSOR Grant 226113 during 1993 and The Alexander von Humboldt Foundation during both of these years.     

A note on an error estimate for least squares approximation

An asymptotic expansion is obtained which provides upper and lower bounds for the error of the bestL ₂ polynomial approximation of degreen forx ⁿ⁺¹ on [–1, 1]. Because the expansion proceeds in only even powers of the reciprocal of the large variable, and the error made by truncating the expansion is numerically less than, and has the same sign as the first neglected term, very good bounds can be obtained. Via a result of Phillips, these results can be extended fromx ⁿ⁺¹ to anyfC ⁿ⁺¹[–1, 1], provided upper and lower bounds for the modulus off ⁽ⁿ⁺¹⁾ are available.     

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.     

Some Results on Best Coapproximation in L 1 (S, X)

As a counterpart to best approximation in normed linear spaces, best coapproximation was introduced by Franchetti and Furi. In this paper, we shall show that if M is a separable, coproximinal subspace of X satisfying some additional conditions, then L ¹ (S, M) is coproximinal in L ¹(S, X).      

Approximation by p -Faber polynomials in the weighted Smirnov class Ep( G,ω ) and the Bieberbach polynomials

Let G\subset C be a finite domain with a regular Jordan boundary L . In this work, the approximation properties of a p -Faber polynomial series of functions in the weighted Smirnov class E ^p (G,ω) are studied and the rate of polynomial approximation, for f∈ E ^p ( G,ω) by the weighted integral modulus of continuity, is estimated. Some application of this result to the uniform convergence of the Bieberbach polynomials π _n in a closed domain \overline G with a smooth boundary L is given. February 25, 1999. Date revised: October 20, 1999. Date accepted: May 26, 2000.     

Bivariate spline interpolation with optimal approximation order

Let Δ be a triangulation of some polygonal domain Ω ⊂ R² and let S_q^r(Δ) denote the space of all bivariate polynomial splines of smoothness r and degree q with respect to Δ. We develop the first Hermite-type interpolation scheme for S _q ^r (Δ), q ≥ 3r + 2, whose approximation error is bounded above by Kh ^q +1, where h is the maximal diameter of the triangles in Δ, and the constant K only depends on the smallest angle of the triangulation and is independent of near-degenerate edges and near-singular vertices. Moreover, the fundamental functions of our scheme are minimally supported and form a locally linearly independent basis for a superspline subspace of S _q ^r (Δ). This shows that the optimal approximation order can be achieved by using minimally supported splines. Our method of proof is completely different from the quasi-interpolation techniques for the study of the approximation power of bivariate splines developed in [7] and [18].     

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     

Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval [–1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.     

WeightedL p approximation by modified hermite interpolation of higher order

The authors establish necessary and sufficient conditions for the weightedL ^p convergence at given rates of Hermite interpolation of higher order based on Jacobi zeros plus the endpoints ±1. Theorems on simultaneous approximation are also proved.This material is based upon work supported by the Ministero della Università e della Ricerca Scientifica e Tecnologica (the first two authors), by the National Research Council (the second author) and by Hungarian National Foundation Grant No. 1910 (the third author).     

Bivariate Lagrange interpolation at the Padua points: the ideal theory approach

The Padua points are a family of points on the square [−1, 1]² given by explicit formulas that admits unique Lagrange interpolation by bivariate polynomials. Interpolation polynomials and cubature formulas based on the Padua points are studied from an ideal theoretic point of view, which leads to the discovery of a compact formula for the interpolation polynomials. The L ^p convergence of the interpolation polynomials is also studied. S. De Marchi and M. Vianello were supported by the “ex-60%” funds of the University of Padua and by the INdAM GNCS (Italian National Group for Scientific Computing). Y. Xu was partially supported by NSF Grant DMS-0604056.     

The bestL 2-approximation by finite sums of functions with separable variables

Summary We consider the problem of the best approximation of a given functionh L ² (X × Y) by sums _k=1 ⁿ f _k f _k, with a prescribed numbern of products of arbitrary functionsf _k L ² (X) andg _k L ² (Y). As a co-product we develop a new proof of the Hilbert—Schmidt decomposition theorem for functions lying inL ² (X × Y).     

Approximations of linear control problems with bang-bang solutions

We analyse the Euler discretization to a class of linear optimal control problems. First we show convergence of order h for the discrete approximation of the adjoint solution and the switching function, where h is the mesh size. Under the additional assumption that the optimal control has bang-bang structure we show that the discrete and the exact controls coincide except on a set of measure O(h). As a consequence, the discrete optimal control approximates the optimal control with order 1 w.r.t. the L ¹-norm and with order 1/2 w.r.t. the L ²-norm. An essential assumption is that the slopes of the switching function at its zeros are bounded away from zero which is in fact an inverse stability condition for these zeros. We also discuss higher order approximation methods based on the approximation of the adjoint solution and the switching function. Several numerical examples underline the results.     

Shape-preserving approximation inL p

We prove a direct theorem for shape preservingL _p -approximation, 0p, in terms of the classical modulus of smoothnessw ₂(f, t _p ¹ ). This theorem may be regarded as an extension toL _p of the well-known pointwise estimates of the Timan type and their shape-preserving variants of R. DeVore, D. Leviatan, and X. M. Yu. It leads to a characterization of monotone and convex functions in Lipschitz classes (and more general Besov spaces) in terms of their approximation by algebraic polynomials.Communicated by Ron DeVore.     

Approximation Orders of FSI Spaces in L 2 (R d )

A second look at the authors' [BDR1], [BDR2] characterization of the approximation order of a Finitely generated Shift-Invariant (FSI) subspace of L ₂(R ^d ) results in a more explicit formulation entirely in terms of the (Fourier transform of the) generators of the subspace. Further, when the generators satisfy a certain technical condition, then, under the mild assumption that the set of 1-periodizations of the generators is linearly independent, such a space is shown to provide approximation order k if and only if contains a (necessarily unique) satisfying for |j|<k , . The technical condition is satisfied, e.g., when the generators are at infinity for some >k+d. In the case of compactly supported generators, this recovers an earlier result of Jia [J1], [J2]. March 19, 1996. Dates revised: September 6, 1996, March 4, 1997.     

Approximation Orders of FSI Spaces in L 2 (R d )

A second look at the authors' [BDR1], [BDR2] characterization of the approximation order of a Finitely generated Shift-Invariant subspace S(Φ) of L ₂ (R ^d ) results in a more explicit formulation entirely in terms of the (Fourier transform of the) generators of the subspace. Further, when the generators satisfy a certain technical condition, then, under the mild assumption that the set of 1-periodizations of the generators is linearly independent, such a space is shown to provide approximation order k if and only if contains a ψ (necessarily unique) satisfying . The technical condition is satisfied, e.g., when the generators are at infinity for some ρ>k+d . In the case of compactly supported generators, this recovers an earlier result of Jia [J1], [J2]. March 19. 1996. Date revised: September 6, 1996.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

On Multivariate Adaptive Approximation

Recently, A. Cohen, R. A. DeVore, P. Petrushev, and H. Xu investigated nonlinear approximation in the space BV (R ² ). They modified the classical adaptive algorithm to solve related extremal problems. In this paper, we further study the modified adaptive approximation and obtain results on some extremal problems related to the spaces V _σ,p ^r (R ^d ) of functions of ``Bounded Variation" and Besov spaces B ^α (R ^d ). November 23, 1998. Date revised: June 25, 1999. Date accepted: September 13, 1999.     

The approximation by q-Bernstein polynomials in the case q ↓ 1

Let B_n (f, q; x), n=1, 2, ... , 0 < q < ∞, be the q-Bernstein polynomials of a function f, B_n (f, 1; x) being the classical Bernstein polynomials. It is proved that, in general, {B_n (f, q_n; x)} with q_n ↓ 1 is not an approximating sequence for f ∈C[0, 1], in contrast to the standard case q_n ↓ 1. At the same time, there exists a sequence 0 < δ_n ↓ 0 such that the condition implies the approximation of f by {B_n (f, q_n; x)} for all f ∈C[0, 1]. Received: 15 March 2005