Nonlinear Approximation with Local Fourier Bases

It is shown that local Fourier bases are unconditional bases for the modulation spaces on R, including the Bessel potential spaces and the Segal algebra S ₀ . As a consequence, the abstract function spaces, that are defined by the approximation properties with respect to a local Fourier basis, are precisely the modulation space s. April 22, 1998. Date accepted: May 18, 1999.     

Restricted Nonlinear Approximation

We introduce a new form of nonlinear approximation called restricted approximation . It is a generalization of n -term wavelet approximation in which a weight function is used to control the terms in the wavelet expansion of the approximant. This form of approximation occurs in statistical estimation and in the characterization of interpolation spaces for certain pairs of L _p and Besov spaces. We characterize, both in terms of their wavelet coefficients and also in terms of their smoothness, the functions which are approximated with a specified rate by restricted approximation. We also show the relation of this form of approximation with certain types of thresholding of wavelet coefficients. March 31, 1998. Date accepted: January 28, 1999.     

On the approximation power of bivariate splines

We show how to construct stable quasi-interpolation schemes in the bivariate spline spaces S _d ^r (Δ) with d⩾ 3r + 2 which achieve optimal approximation order. In addition to treating the usual max norm, we also give results in the L _p norms, and show that the methods also approximate derivatives to optimal order. We pay special attention to the approximation constants, and show that they depend only on the smallest angle in the underlying triangulation and the nature of the boundary of the domain. This revised version was published online in August 2006 with corrections to the Cover Date.     

A Bound on the Approximation Order of Surface Splines

The functions φ _m :=|.| ^2m-d if d is odd, and φ _m :=|.| ^2m-d \log|.| if d is even, are known as surface splines, and are commonly used in the interpolation or approximation of smooth functions. We show that if one's domain is the unit ball in R ^d , then the approximation order of the translates of φ _m is at most m . This is in contrast to the case when the domain is all of R ^d where it is known that the approximation order is exactly 2m . April 23, 1996. Date revised: May 5, 1997.     

Contracted Zero Distributions of Extremal Polynomials Associated with Slowly Decaying Weights

We consider the asymptotic zero behavior of polynomials that are extremal with respect to slowly decaying weights on [0, ∈fty) , such as the log-normal weight \exp(-γ ² log  ² x) . The zeros are contracted by taking the appropriate d _n th roots with d _n →∈fty . The limiting distribution of the contracted zeros is described in terms of the solution of an extremal problem in logarithmic potential theory with a circular symmetric external field. November 23, 1998. Date revised: February 8, 1999. Date accepted: March 2, 1999.     

Greedy Algorithms with Regard to Multivariate Systems with Special Structure

The question of finding an optimal dictionary for nonlinear m -term approximation is studied in this paper. We consider this problem in the periodic multivariate (d variables) case for classes of functions with mixed smoothness. We prove that the well-known dictionary U ^d which consists of trigonometric polynomials (shifts of the Dirichlet kernels) is nearly optimal among orthonormal dictionaries. Next, it is established that for these classes near-best m -term approximation, with regard to U ^d , can be achieved by simple greedy-type (thresholding-type) algorithms. The univariate dictionary U is used to construct a dictionary which is optimal among dictionaries with the tensor product structure. June 22, 1998. Date revised: March 26, 1999. Date accepted: March 22, 1999.     

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.     

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.     

Uniqueness of Markov-Extremal Polynomials on Symmetric Convex Bodies

For a compact set K\subset R ^d with nonempty interior, the Markov constants M _n (K) can be defined as the maximal possible absolute value attained on K by the gradient vector of an n -degree polynomial p with maximum norm 1 on K . It is known that for convex, symmetric bodies M _n (K) = n ² /r(K) , where r(K) is the ``half-width' (i.e., the radius of the maximal inscribed ball) of the body K . We study extremal polynomials of this Markov inequality, and show that they are essentially unique if and only if K has a certain geometric property, called flatness. For example, for the unit ball B ^d (\smallbf 0, 1) we do not have uniqueness, while for the unit cube [-1,1] ^d the extremal polynomials are essentially unique. September 9, 1999. Date revised: September 28, 2000. Date accepted: November 14, 2000.     

On the Best Approximation by Ridge Functions in the Uniform Norm

We consider the best approximation of some function classes by the manifold M _n consisting of sums of n arbitrary ridge functions. It is proved that the deviation of the Sobolev class W _p ^r,d from the manifold M _n in the space L _q for any 2≤ q≤ p≤∈fty behaves asymptotically as n ^-r/(d-1) . In particular, we obtain this asymptotic estimate for the uniform norm p=q=∈fty . January 10, 2000. Date revised: March 1, 2001. Date accepted: March 12, 2001.     

Rates of Best Uniform Rational Approximation of Analytic Functions by Ray Sequences of Rational Functions

In this paper, problems related to the approximation of a holomorphic function f on a compact subset E of the complex plane C by rational functions from the class of all rational functions of order (n,m) are considered. Let ρ _n,m = ρ _n,m (f;E) be the distance of f in the uniform metric on E from the class . We obtain results characterizing the rate of convergence to zero of the sequence of the best rational approximation { ρ _n,m(n) } _n=0 ^∞ , m(n)/n → θ ∈ (0,1] as n → ∞ . In particular, we give an upper estimate for the liminf _{n →∞} ρ _n,m(n) ^1/(n+m(n)) in terms of the solution to a certain minimum energy problem with respect to the logarithmic potential. The proofs of the results obtained are based on the methods of the theory of Hankel operators. June 16, 1997. Date revised: December 1, 1997. Date accepted: December 1, 1997. Communicated by Ronald A. DeVore.     

Representation,interpolation, and reiteration theorems for generalized approximation spaces

We show that the representation theorem for classical approximation spaces can be generalized to spaces A(X,l ^q (ℬ))={f∈X:{E _n (f)}∈l ^q (ℬ)} in which the weighted l ^q -space l ^q (ℬ) can be (more or less) arbitrary. We use this theorem to show that generalized approximation spaces can be viewed as real interpolation spaces (defined with K-functionals or main-part K-functionals) between couples of quasi-normed spaces which satisfy certain Jackson and Bernstein-type inequalities. Especially, interpolation between an approximation space and the underlying quasi-normed space leads again to an approximation space. Together with a general reiteration theorem, which we also prove in the present paper, we obtain formulas for interpolation of two generalized approximation spaces. Received: December 6, 2001; in final form: April 2, 2002?Published online: March 14, 2003     

On a Banach space approximable by Jacobi polynomials

Let X represent either the space C[-1,1] L _p ^(α,β) (w), 1 ≦ p < ∞ on [-1, 1]. Then Xare Banach spaces under the sup or the p norms, respectively. We prove that there exists a normalized Banach subspace X ¹ _αβ of Xsuch that every f ∈ X ¹ _αβ can be represented by a linear combination of Jacobi polynomials to any degree of accuracy. Our method to prove such an approximation problem is Fourier–Jacobi analysis based on the convergence of Fourier–Jacobi expansions. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

On the Convergence in Capacity of Rational Approximants

Let {r _n } be a sequence of rational functions deg( r _n ≤ n) that converge rapidly in measure to an analytic function f on an open set in C ^N . We show that {r _n } converges rapidly in capacity to f on its natural domain of definition W _f (which, by a result of Goncar, is an open subset of C ^N ). In particular, for f meromorphic on C ^N and analytic near zero the sequence of Padé approximants {π _n (z, f, λ)} (as defined by Goncar) converges rapidly in capacity to f on C ^N . January 14, 1999. Date revised: October 7, 1999. Date accepted: November 1, 1999.     

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.     

Polynomial Approximation on Convex Subsets of R n

Let K be a closed bounded convex subset of R ⁿ ; then by a result of the first author, which extends a classical theorem of Whitney there is a constant w _m (K) so that for every continuous function f on K there is a polynomial ϕ of degree at most m-1 so that |f(x)-ϕ(x)|≤ w_m(K) sup _{x,x+mh∈ K} |Δ_h^m(f;x)|. The aim of this paper is to study the constant w _m (K) in terms of the dimension n and the geometry of K . For example, we show that w ₂ (K)≤ (1/2) [ log ₂ n]+5/4 and that for suitable K this bound is almost attained. We place special emphasis on the case when K is symmetric and so can be identified as the unit ball of finite-dimensional Banach space; then there are connections between the behavior of w _m (K) and the geometry (particularly the Rademacher type) of the underlying Banach space. It is shown, for example, that if K is an ellipsoid then w ₂ (K) is bounded, independent of dimension, and w ₃ (K)\sim log n . We also give estimates for w ₂ and w ₃ for the unit ball of the spaces l _p ⁿ where 1≤ p≤∈fty. September 24, 1997. Dates revised: January 18, 1999 and June 10, 1999. Date accepted: June 25, 1999.     

On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension

The pseudo-dimension of a real-valued function class is an extension of the VC dimension for set-indicator function classes. A class of finite pseudo-dimension possesses a useful statistical smoothness property. In [10] we introduced a nonlinear approximation width = which measures the worst-case approximation error over all functions by the best manifold of pseudo-dimension n . In this paper we obtain tight upper and lower bounds on ρ _n (W ^r,d _p , L _q ) , both being a constant factor of n ^-r/d , for a Sobolev class W ^r,d _p , . As this is also the estimate of the classical Alexandrov nonlinear n -width, our result proves that approximation of W ^r,d _p by the family of manifolds of pseudo-dimension n is as powerful as approximation by the family of all nonlinear manifolds with continuous selection operators. March 12, 1997. Dates revised: August 26, 1997, October 24, 1997, March 16, 1998, June 15, 1998. Date accepted: June 25, 1998.     

Interpolatory Pointwise Estimates for Polynomial Approximation

We discuss whether or not it is possible to have interpolatory pointwise estimates in the approximation of a function f∈ C[0,1] , by polynomials. For the sake of completeness, as well as in order to strengthen some existing results, we discuss briefly the situation in unconstrained approximation. Then we deal with positive and monotone constraints where we show exactly when such interpolatory estimates are achievable by proving affirmative results and by providing the necessary counterexamples in all other cases. November 16, 1998. Date revised: July 12, 1999. Date accepted: September 13, 1999.     

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.