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.     

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.     

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.     

Markov—Bernstein-Type Inequality for Trigonometric Polynomials with Respect to Doubling Weights on [-ω,ω]

   Abstract. Various important, weighted polynomial inequalities, such as Bernstein, Marcinkiewicz, Nikolskii, Schur, Remez, etc., have been proved recently by Giuseppe Mastroianni and Vilmos Totik under minimal assumptions on the weights. In most cases this minimal assumption is the doubling condition. Here, based on a recently proved Bernstein-type inequality by D. S. Lubinsky, we establish Markov—Bernstein-type inequalities for trigonometric polynomials with respect to doubling weights on [-ω,ω] . Namely, we show the theorem below. Theorem Let p ∈ [1,∞) and ω ∈ (0, 1/2] . Suppose W is a weight function on [-ω,ω] such that W(ω cos t) is a doubling weight. Then there is a constant C depending only on p and the doubling constant L so that

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.     

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.     

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.     

Some remarks on Legendrian rectifiable currents

A rectifiable current of dimension n−1 in the sphere bundle Sℝⁿ≃ℝⁿ×S ^{n −1} for euclidean space is Legendrian if it annihilates the contact 1-form α (i.e. T(α∧φ)=0 for all forms φ of degree n−2). Such a current may be naturally associated to any convex set or to any singular real analytic variety, and induces the curvature measures of such a set. We prove that the projection to ℝⁿ of a carrier of a general such T is C ²-rectifiable in the sense of Anzellotti–Serapioni. We deduce that the boundary of a set with positive reach, as well as its singular skeleta, are C ²-rectifiable. In case ∂T= 0 we prove also that the curvature measures associated to T satisfy the analogues of the classical variational formulas for curvature integrals. It follows that such formulas are valid for the curvature measures of subsets of space forms. Received: 3 December 1997/ Revised version: 25 May 1998     

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     

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.     

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.     

Pointwise strong and very strong approximation of Fourier series

We present an estimation of the and H _u ^λφ f means as approximation versions of the Totik type generalization (see [6, 7]) of the result of G. H. Hardy, J. E. Littlewood, considered by N. L. Pachulia in [5]. Some results on the norm approximation will also be given.      

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.     

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.     

Ergodic Optimization for Renewal Type Shifts

We consider a class of countable Markov shifts and a locally H?lder potential φ. We prove that the existence of φ-optimal measures is closely related to the behaviour of the pressure function t → P(tφ). Using a Theorem by Sarig it is possible to prove that there exists a critical value t _c ∈ (0, ∞] such that for t < t _c the pressure is analytic and for t > t _c is linear. We prove that if t _c is finite, then there are no φ-optimal measures, and if it is infinite, then φ-optimal measures do exist. The author was partially supported by FCT/POCTI/FEDER and the grant SFRH/BPD/21927/2005.     

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.     

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.     

From continuous to discrete Weyl-Heisenberg frames through sampling

In this article we consider the question when one can generate a Weyl- Heisenberg frame for l ² (ℤ) with shift parameters N, M ⁻¹ (integer N, M) by sampling a Weyl-Heisenberg frame for L ² (ℝ) with the same shift parameters at the integers. It is shown that this is possible when the window g ε L ² (ℝ) generating the Weyl-Heisenberg frame satisfies an appropriate regularity condition at the integers. When, in addition, the Tolimieri-Orr condition A is satisfied, the minimum energy dual window ^o γ ε L ² (ℝ) can be sampled as well, and the two sampled windows continue to be related by duality and minimality. The results of this article also provide a rigorous basis for the engineering practice of computing dual functions by writing the Wexler-Raz biorthogonality condition in the time-domain as a collection of decoupled linear systems involving samples of g and ^o γ as knowns and unknowns, respectively. We briefly indicate when and how one can generate a Weyl-Heisenberg frame for the space of K-periodic sequences, where K=LCM (N, M), by periodization of a Weyl-Heisenberg frame for ℓ ² ℤ with shift parameters N, M ⁻¹ .     

Motivic equivalence of quadratic forms. II

Let F be a field of characteristic ≠2 and φ be a quadratic form over F. By X _φ we denote the projective variety given by the equation φ=0. For each positive even integer d≥8 (except for d=12) we construct a field F and a pair φ, ψ of anisotropic d-dimensional forms over F such that the Chow motives of X _φ and X _ψ coincide but . For a pair of anisotropic (2 ^{n -1})-dimensional quadrics X and Y, we prove that existence of a rational morphism Y→X is equivalent to existence of a rational morphism Y→X. Received: 27 September 1999 / Revised version: 27 December 1999     

Regularity of refinable function vectors

We study the existence and regularity of compactly supported solutions φ = (φ_v) _v=0 ^/r−1 of vector refinement equations. The space spanned by the translates of φ_v can only provide approximation order if the refinement maskP has certain particular factorization properties. We show, how the factorization ofP can lead to decay of |̸_v(u)| as |u| → ∞. The results on decay are used to prove uniqueness of solutions and convergence of the cascade algorithm.