Biorthogonal Wavelet Expansions

This paper is concerned with developing conditions on a given finite collection of compactly supported algebraically linearly independent refinable functions that insure the existence of biorthogonal systems of refinable functions with similar properties. In particular, we address the close connection of this issue with stationary subdivision schemes. Date received: May 20, 1995. Date revised: March 2, 1996.     

Exponential Box-Like Splines on Nonuniform Grids

We generalize the exponential box spline by allowing it to have arbitrarily spaced knots in any of its directions and derive the corresponding recurrence and differentiation rules. The corresponding spline space is spanned by the shifts of finitely many such splines and contains the usual family of exponential polynomials. The (local) linear independence of the spanning set is equivalent to a geometric condition closely related to unimodularity. January 10, 1996. Date revised: December 9, 1997. Date accepted: March 18, 1998.     

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 Existence and Weak Stability of Matrix Refinable Functions

We consider the existence of distributional (or L ₂ ) solutions of the matrix refinement equation where P is an r×r matrix with trigonometric polynomial entries. One of the main results of this paper is that the above matrix refinement equation has a compactly supported distributional solution if and only if the matrix P (0) has an eigenvalue of the form 2 ⁿ , . A characterization of the existence of L ₂ -solutions of the above matrix refinement equation in terms of the mask is also given. A concept of L ₂ -weak stability of a (finite) sequence of function vectors is introduced. In the case when the function vectors are solutions of a matrix refinement equation, we characterize this weak stability in terms of the mask. August 1, 1996. Date revised: July 28, 1997. Date accepted: August 12, 1997.     

Biorthogonal M -Channel Compactly Supported Wavelets

We study a class of M -channel subband coding schemes with perfect reconstruction. Along the lines of [8] and [10], we construct compactly supported biorthogonal wavelet bases of L ² (R) , with dilation factor M , associated to these schemes. In particular, we study the case of splines, and obtain explicitly simple expressions for all the relevant filters. The resulting wavelets have arbitrarily large regularity and we also obtain asymptotic estimates for the regularity exponent. September 17, 1998. Date revised: June 14, 1999. Date accepted: June 25, 1999.     

Adaptive Mollifiers for High Resolution Recovery of Piecewise Smooth Data from its Spectral Information

We discuss the reconstruction of piecewise smooth data from its (pseudo-) spectral information. Spectral projections enjoy superior resolution provided the data is globally smooth, while the presence of jump discontinuities is responsible for spurious O (1) Gibbs oscillations in the neighborhood of edges and an overall deterioration of the unacceptable first-order convergence in rate. The purpose is to regain the superior accuracy in the piecewise smooth case, and this is achieved by mollification. Here we utilize a modified version of the two-parameter family of spectral mollifiers introduced by Gottlieb and Tadmor [GoTa85]. The ubiquitous one-parameter, finite-order mollifiers are based on dilation . In contrast, our mollifiers achieve their high resolution by an intricate process of high-order cancellation . To this end, we first implement a localization step using an edge detection procedure [GeTa00a, b]. The accurate recovery of piecewise smooth data is then carried out in the direction of smoothness away from the edges, and adaptivity is responsible for the high resolution. The resulting adaptive mollifier greatly accelerates the convergence rate, recovering piecewise analytic data within exponential accuracy while removing the spurious oscillations that remained in [GoTa85]. Thus, these adaptive mollifiers offer a robust, general-purpose ``black box' procedure for accurate post-processing of piecewise smooth data. March 29, 2001. Final version received: August 31, 2001.     

Cubic Spline Prewavelets on the Four-Directional Mesh

Dedicated to Professor M. J. D. Powell on the occasion of his sixty-fifth birthday and his retirement. In this paper, we design differentiable, two-dimensional, piecewise polynomial cubic prewavelets of particularly small compact support. They are given in closed form, and provide stable, orthogonal decompositions of L ² (R ² ) . In particular, the splines we use in our prewavelet constructions give rise to stable bases of spline spaces that contain all cubic polynomials, whereas the more familiar box spline constructions cannot reproduce all cubic polynomials, unless resorting to a box spline of higher polynomial degree.     

Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Bounds on Projections onto Bivariate Polynomial Spline Spaces with Stable Local Bases

L _& ∞ bounds for norms of projections onto bivariate polynomial spline spaces on regular triangulations with stable local bases are established. The general results are then applied to obtain error bounds for best L ₂ - and l ₂ -approximation by splines on quasi-uniform triangulations. March 8, 2000. Date revised: November 20, 2000. Date accepted: July 9, 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.     

Note on the Approximation of Powers of the Distance in Two-Dimensional Domains

Although Newman's trick has been mainly applied to the approximation of univariate functions, it is also appropriate for the approximation of multivariate functions that are encountered in connection with Green's functions for elliptic differential equations. The asymptotics of the real-valued function on a ball in 2-space coincides with that for an approximation problem in the complex plane. The note contains an open problem. May 17, 1999. Date revised: October 20, 1999. Date accepted: March 17, 2000.     

Using the refinement equation for the construction of pre-wavelets III: Elliptic splines

The purpose of this paper is to provide multiresolution analysis, stationary subdivision and pre-wavelet decomposition onL ²(R ^d ) based on a general class of functions which includes polyharmonic B-splines.The work of this author has been partially supported by a DARPA grant.The work of this author has been partially supported by Fondo Nacional de Ciencia y Technologia under Grant 880/89.     

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.     

More on Comonotone Polynomial Approximation

The main achievement of this paper is that we show, what was to us, a surprising conclusion, namely, twice continuously differentiable functions in (0,1) (with some regular behavior at the endpoints) which change monotonicity at least once in the interval, are approximable better by comonotone polynomials, than are such functions that are merely monotone. We obtain Jackson-type estimates for the comonotone polynomial approximation of such functions that are impossible to achieve for monotone approximation. July 7, 1998. Date revised: May 5, 1999. Date accepted: July 23, 1999.     

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.     

Greedy Algorithm and m -Term Trigonometric Approximation

We study the following nonlinear method of approximation by trigonometric polynomials in this paper. For a periodic function f we take as an approximant a trigonometric polynomial of the form , where is a set of cardinality m containing the indices of the m biggest (in absolute value) Fourier coefficients of function f . We compare the efficiency of this method with the best m -term trigonometric approximation both for individual functions and for some function classes. It turns out that the operator G _m provides the optimal (in the sense of order) error of m -term trigonometric approximation in the L _p -norm for many classes. September 23, 1996. Date revised: February 3, 1997.     

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.     

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.     

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.     

Interpolation by Polynomials and Radial Basis Functions on Spheres

The paper obtains error estimates for approximation by radial basis functions on the sphere. The approximations are generated by interpolation at scattered points on the sphere. The estimate is given in terms of the appropriate power of the fill distance for the interpolation points, in a similar manner to the estimates for interpolation in Euclidean space. A fundamental ingredient of our work is an estimate for the Lebesgue constant associated with certain interpolation processes by spherical harmonics. These interpolation processes take place in ``spherical caps' whose size is controlled by the fill distance, and the important aim is to keep the relevant Lebesgue constant bounded. This result seems to us to be of independent interest. March 27, 1997. Dates revised: March 19, 1998; August 5, 1999. Date accepted: December 15, 1999.