Direct and Inverse Estimates for Bernstein Polynomials

Direct estimates for the Bernstein operator are presented by the Ditzian—Totik modulus of smoothness , whereby the step-weight φ is a function such that φ ² is concave. The inverse direction will be established for those step-weights φ for which φ ² and , are concave functions. This combines the classical estimate (φ=1 ) and the estimate developed by Ditzian and Totik ( ). In particular, the cases , λ∈[0,1] , are included. August 2, 1996. Date revised: March 28, 1997.     

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 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 ≤ ∞.     

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.     

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.     

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.     

Inequalities for determinants and permanents

Let p be a prime > 3. It is shown that no integral circulant of order p^k exists with determinant p^k+1 . It is also shown that m is the determinant of an integral 9×9 circulant if and only if (m, 3)=l, or m = 0 mod 27. The proof makes use of a criterion which must be satisfied by the difference of two units in the cyclotomic field of level p^k .     

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.     

Sparse Components of Images and Optimal Atomic Decompositions

Recently, Field, Lewicki, Olshausen, and Sejnowski have reported efforts to identify the ``Sparse Components' of image data. Their empirical findings indicate that such components have elongated shapes and assume a wide range of positions, orientations, and scales. To date, sparse components analysis (SCA) has only been conducted on databases of small (e.g., 16 by 16) image patches and there seems limited prospect of dramatically increased resolving power. In this paper, we apply mathematical analysis to a specific formalization of SCA using synthetic image models, hoping to gain insight into what might emerge from a higher-resolution SCA based on n by n image patches for large n but a constant field of view. In our formalization, we study a class of objects \cal F in a functional space; they are to be represented by linear combinations of atoms from an overcomplete dictionary, and sparsity is measured by the ℓ <sup>p</sup> -norm of the coefficients in the linear combination. We focus on the class \cal F = \sc Star <sup>α</sup> of black and white images with the black region consisting of a star-shaped set with an α -smooth boundary. We aim to find an optimal dictionary, one achieving the optimal sparsity in an atomic decomposition uniformly over members of the class \sc Star <sup>α</sup> . We show that there is a well-defined optimal sparsity of representation of members of \sc Star <sup>α</sup> ; there are decompositions with finite ℓ <sup>p</sup> -norm for p > 2/(α+1) but not for p < 2/(α+1) . We show that the optimal degree of sparsity is nearly attained using atomic decompositions based on the wedgelet dictionary. Wedgelets provide a system of representation by elements in a dyadically organized collection, at all scales, locations, orientations, and positions. The atoms of our atomic decomposition contain both coarse-scale dyadic ``blobs,' which are simply wedgelets from our dictionary, and fine-scale ``needles,' which are differences of pairs of wedgelets. The fine-scale atoms used in the adaptive atomic decomposition are highly anisotropic and occupy a range of positions, scales, and locations. This agrees qualitatively with the visual appearance of empirically determined sparse components of natural images. The set has certain definite scaling properties; for example, the number of atoms of length l scales as 1/l , and, when the object has α -smooth boundaries, the number of atoms with anisotropy \approx A scales as \approx A ^α-1 . August 16, 1999. Date revised: April 24, 2000. Date accepted: April 4, 2000.     

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.     

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.     

Weighted Maximum Over Minimum Modulus of Polynomials, Applied to Ray Sequences of Padé Approximants

Let a≥ 0 , ɛ >0 . We use potential theory to obtain a sharp lower bound for the linear Lebesgue measure of the set Here P is an arbitrary polynomial of degree ≤ n . We then apply this to diagonal and ray Padé sequences for functions analytic (or meromorphic) in the unit ball. For example, we show that the diagonal \left{ [n/n]\right} _n=1 ^∞ sequence provides good approximation on almost one-eighth of the circles centre 0 , and the \left{ [2n/n]\right} _n=1 ^∞ sequence on almost one-quarter of such circles. July 18, 2000. Date revised: . Date accepted: April 19, 2001.     

L p -Error Bounds for Hermite Interpolation and the Associated Wirtinger Inequalities

The B-spline representation for divided differences is used, for the first time, to provide L _p -bounds for the error in Hermite interpolation, and its derivatives, thereby simplifying and improving the results to be found in the extensive literature on the problem. These bounds are equivalent to certain Wirtinger inequalities. The major result is the inequality where H_Θ f is the Hermite interpolant to f at the multiset of n points Θ, and is the diameter of . This inequality significantly improves upon Beesack's inequality, on which almost all the bounds given over the last 30 years have been based. Date received: June 24, 1994 Date revised: February 4, 1996.     

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     

Variational Principles and Sobolev-Type Estimates for Generalized Interpolation on a Riemannian Manifold

The purpose of this paper is to study certain variational principles and Sobolev-type estimates for the approximation order resulting from using strictly positive definite kernels to do generalized Hermite interpolation on a closed (i.e., no boundary), compact, connected, orientable, m -dimensional C ^∞ Riemannian manifold , with C ^∞ metric g _ij . The rate of approximation can be more fully analyzed with rates of approximation given in terms of Sobolev norms. Estimates on the rate of convergence for generalized Hermite and other distributional interpolants can be obtained in certain circumstances and, finally, the constants appearing in the approximation order inequalities are explicit. Our focus in this paper will be on approximation rates in the cases of the circle, other tori, and the 2 -sphere. April 10, 1996. Dates revised: March 26, 1997; August 26, 1997. Date accepted: September 12, 1997. Communicated by Ronald A. DeVore.     

Lagrange Interpolation in Weighted Besov Spaces

The behavior of the Lagrange polynomial L _m (w,f) , based on the zeros of the orthogonal polynomials, is studied in some weighted Besov spaces B ^p _r,q (u) . It is proved that L _m (w) is a uniformly bounded map under suitable conditions on the weight functions and the parameters p , r , and q . December 11, 1996. Date revised: October 29, 1997. Date accepted: June 15, 1998.     

Piecewise Monotone Pointwise Approximation

Let r, k, s be three integers such that , or We prove the following: Proposition. Let Y:={y _i } _i=1 ^s be a fixed collection of distinct points y _i ∈ (-1,1) and Π (x):= (x-y ₁ ). ... .(x-y _s ). Let I:=[-1,1]. If f ∈ C ^(r) (I) and f'(x)Π(x) ≥ 0, x ∈ I, then for each integer n ≥ k+r-1 there is an algebraic polynomial P _n =P _n (x) of degree ≤ n such that P _n '(x) Π (x) ≥ 0 and $$ \vert f(x)-P_n(x) \vert \le B\left(\frac{1}{n^2}+\frac{1}{n}\sqrt{1-x^2}\right)^r \omega_k \left(f^{(r)};\frac{1}{n^2}+\frac{1}{n}\sqrt{1-x^2}\right) \legno{(1)}$$ for all x∈ I, where ω _k (f ^(r) ;t) is the modulus of smoothness of the k -th order of the function f ^(r) and B is a constant depending only on r , k , and Y. If s=1, the constant B does not depend on Y except in the case (r=1, k=3). In addition it is shown that (1) does not hold for r=1, k>3. March 20, 1995. Dates revised: March 11, 1996; December 20, 1996; and August 7, 1997.     

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.     

On Stable Local Bases for Bivariate Polynomial Spline Spaces

Stable locally supported bases are constructed for the spaces \cal S _d ^r (\triangle) of polynomial splines of degree d≥ 3r+2 and smoothness r defined on triangulations \triangle , as well as for various superspline subspaces. In addition, we show that for r≥ 1 , in general, it is impossible to construct bases which are simultaneously stable and locally linearly independent. February 2, 2000. Date revised: November 27, 2000. Date accepted: March 7, 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.