Smoothing noisy data with spline functions

Summary A procedure for calculating the trace of the influence matrix associated with a polynomial smoothing spline of degree2m–1 fitted ton distinct, not necessarily equally spaced or uniformly weighted, data points is presented. The procedure requires orderm ² n operations and therefore permits efficient orderm ² n calculation of statistics associated with a polynomial smoothing spline, including the generalized cross validation. The method is a significant improvement over an existing method which requires ordern ³ operations.     

An efficient method for calculating smoothing splines using orthogonal transformations

Summary A procedure for calculating the mean squared residual and the trace of the influence matrix associated with a polynomial smoothing spline of degree 2m–1 using an orthogonal factorization is presented. The procedure substantially overcomes the problem of ill-conditioning encountered by a recently developed method which employs a Cholesky factorization, but still requires only orderm ² n operations and ordermn storage.     

LM-g splines

As an extension of the notion of an L-g spline, three mathematical structures called LM-g splines of types I, II, and III are introduced. Each is defined in terms of two differential operators the coefficients a_j, J = 0,…, n − 1, and b_i, I = 0,…, m, are sufficiently smooth; and b_m is bounded away from zero on [0, T]. Each of the above types of splines is the solution of an optimization problem more general than the one used in the definition of the L-g spline and hence it is recognized as an entity which is distinct from and more general mathematically than the L-g spline. The LM-g splines introduced here reduce to an L-g spline in the special case in which m = 0 and b₀ = constant ≠ 0. After the existence and uniqueness conditions, characterization, and best approximation properties for the proposed splines are obtained in an appropriate reproducing kernel Hilbert space framework, their usefulness in extending the range of applicability of spline theory to problems in estimation, optimal control, and digital signal processing are indicated. Also, as an extension of recent results in the generalized spline literature, state variable models for the LM-g splines introduced here are exhibited, based on which existing least squares algorithms can be used for the recursive calculation of these splines from the data.     

Natural spline functions,their associated eigenvalue problem

Summary We consider the problem of studying the behaviour of the eigenvalues associated with spline functions with equally spaced knots. We show that they are wherem is the order of the spline andn, the number of knots.This result is of particular interest to prove optimality properties of the Generalized Cross-Validation Method and had been conjectured by Craven and Wahba in a recent paper.     

Monotonicity of quadrature formulae of Gauss type and comparison theorems for monosplines

Summary This paper deals with quadrature formulae of Gauss type corresponding to subspaces of spline functionsS _{m–1, k} of degreem–1 withk fixed knots. We shall show monotonicity of the quadrature formulae for functions which are contained in the so-called convexity cone ofS _m–1,k Moreover, we apply these results to monosplines and establish comparison theorems for these splines.     

An algorithm for the computation of the exponential spline

Summary Procedures for the calculation of the exponential spline (spline under tension) are presented in this paper. The procedureexsplcoeff calculates the second derivatives of the exponential spline. Using the second derivatives the exponential spline can be evaluated in a stable and efficient manner by the procedureexspl. The limiting cases of the exponential spline, the cubic spline and the linear spline are included. A proceduregenerator is proposed, which computes appropriate tension parameters. The performance of the algorithm is discussed for several examples.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

The <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-Approximation Order of Surface Spline Interpolation for 1 \leq <Emphasis Type="Italic">p</Emphasis> \leq 2

We show that the L_p-approximation order of surface spline interpolation equals m+1/p for p in the range 1 \leq p \leq 2, where m is an integer parameter which specifies the surface spline. Previously it was known that this order was bounded below by m + &frac; and above by m+1/p. With h denoting the fill-distance between the interpolation points and the domain , we show specifically that the L_p()-norm of the error between f and its surface spline interpolant is O(h^{m + 1/p}) provided that f belongs to an appropriate Sobolev or Besov space and that \subset R^d is open, bounded, and has the C^2m-regularity property. We also show that the boundary effects (which cause the rate of convergence to be significantly worse than O(h^2m)) are confined to a boundary layer whose width is no larger than a constant multiple of h |log h|. Finally, we state numerical evidence which supports the conjecture that the L_p-approximation order of surface spline interpolation is m + 1/p for 2 < p \leq \infty.     

Two-scale symbol and autocorrelation symbol for B-splines with multiple knots

The Fourier transforms of B-splines with multiple integer knots are shown to satisfy a simple recursion relation. This recursion formula is applied to derive a generalized two-scale relation for B-splines with multiple knots. Furthermore, the structure of the corresponding autocorrelation symbol is investigated. In particular, it can be observed that the solvability of the cardinal Hermite spline interpolation problem for spline functions of degree 2m+1 and defectr, first considered by Lipow and Schoenberg [9], is equivalent to the Riesz basis property of our B-splines with degreem and defectr. In this way we obtain a new, simple proof for the assertion that the cardinal Hermite spline interpolation problem in [9] has a unique solution.     

Some Properties of Minimal Splines

S. G. Mikhlin was the first to construct systematically coordinate functions on an equidistant grid solving a system of approximate equations (called “fundamental relations”, see [5]; Goel discussed some special cases earlier in 1969; see also [1, 4, 6]). Further, the idea was developed in the case of irregular grids (which may have finite accumulation points, see [1] ). This paper is devoted to the investigation of A-minimal splines, introduced by the author; they include polynomial minimal splines which have been discussed earlier. Using the idea mentioned above, we give necessary and sufficient conditions for existence, uniqueness and g-continuity of these splines. The application of these results to polynomial splines of m-th degree on an equidistant grid leads us, in particular, to necessary and sufficient conditions for the continuity of their i-th derivative (i = 1, ?, m). These conditions do not exclude discontinuities of other derivatives (e.g. of order less than i). This allows us to give a certain classification of minimal spline spaces. It turns out that the spline classes are in one-to-one-correspondence with certain planes contained in a hyperplane.     

Convergence of Derivatives of Optimal Nodal Splines

Optimal nodal spline interpolantsWfof ordermwhich have local support can be used to interpolate a continuous functionfat a set of mesh points. These splines belong to a spline space with simple knots at the mesh points as well as atm−2 arbitrary points between any two mesh points and they reproduce polynomials of orderm. It has been shown that, for a sequence of locally uniform meshes, these splines converge uniformly for anyfCas the mesh norm tends to zero. In this paper, we derive a set of sufficient conditions on the sequence of meshes for the uniform convergence ofD^jWftoD^jfforfC^sandj=1, …, s<m. In addition we give a bound forD^rWfwiths<r<m. Finally, we use optimal nodal spline interpolants for the numerical evaluation of Cauchy principal value integrals.     

Spline approximations to spherically symmetric distributions

Summary We discuss the problem of approximating a functionf of the radial distancer in ^d on 0r< by a spline function of degreem withn (variable) knots. The spline is to be constructed so as to match the first 2n moments off. We show that if a solution exists, it can be obtained from ann-point Gauss-Christoffel quadrature formula relative to an appropriate moment functional or, iff is suitably restricted, relative to a measure, both depending onf. The moment functional and the measure may or may not be positive definite. Pointwise convergence is discussed asn. Examples are given including distributions from statistical mechanics.The work of the first author was supported in part by the National Science Foundation under grant DCR-8320561.     

Moment-preserving spline approximation on finite intervals

Summary Continuing previous wotk, we discuss the problem of approximating a functionf on the interval [0, 1] by a spline function of degreem, withn (variable) knots, matching, as many of the initial moments off as possible. Additional constraints on the derivatives of the approximation at one endpoint of [0, 1] may also be imposed. We show that, if the approximations exist, they can be represented in terms of generalized Gauss-Lobatto and Gauss-Radau quadrature rules relative to appropriate moment functionals or measures (depending off). Pointwise convergence asn, for fixedm>0, is shown for functionsf that are completely monotonic on [0, 1], among others. Numerical examples conclude the paper.The work of the first author was supported by theMinistero della Pubblica Istruzione and by theConsiglio Nazionale delle Ricerche. The work of the second author was supported, in part, by the National Science Foundation under grant DCR-8320561     

Notes on spline functions III: On the convergence of the interpolating cardinal splines as their degree tends to infinity

It is shown that for entire functionsf(x) defined by a Fourier-Stieltjes integral (9) the cardinal splineS _m (x) of the odd degree 2m−1, which interpolatesf(x) at all integers, converges tof(x) asm tends to infinity. Properties of the exponential Euler spline are used in the proof. Sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

Truncated Laurent expansions for the fast evaluation of thin plate splines

Thin plate splines are highly useful for the approximation of functions of two variables, partly because they provide the interpolant to scattered function values that minimizes a 2-norm of second derivatives. On the other hand, they have the severe disadvantage that the explicit calculation of a thin plate spline approximation requires a log function to be evaluatedm times, wherem is the number of r ²logr ² terms that occur. Therefore we consider a recent technique that saves much work whenm is large by forming sets of terms, and then the total contribution to the thin plate spline from the terms of each set is estimated by a single truncated Laurent expansion. In order to apply this technique, one has to pick the sets, one has to generate the coefficients of the expansions, and one has to decide which expansions give enough accuracy when the value of the spline is required at a general point of ². Our answers to these questions are different from those that are given elsewhere, as we prefer to refine sets of terms recursively by splitting them into two rather than four subsets. Some theoretical properties and several numerical results of our method are presented. They show that the work to calculate all the Laurent coefficients is usuallyO(m logm), and then onlyO(logm) operations are needed to estimate the value of the thin plate spline at a typical point of ². Thus substantial gains over direct methods are achieved form200.     

Stability of a spline collocation method for strongly elliptic multidimensional singular integral equations

Summary We consider a spline collocation method for strongly elliptic zero order pseudodifferential equationsp _gw Au=f on a cube =(0, 1) ^m . Utilizing multilinear spline functions which are zero at the boundary we collocate at the meshpoints inside . For classical strongly elliptic translation invariant pseudodifferential operators, we verify the stability of the considered collocation method inL ²(). Afterwards, form2 and a right hand sidefH ⁸(),s>m/2, we prove an asymptotic convergence estimate.The author has been supported by a grant of Deutsche Forschungsgemeinschaft under grant number Ko 634/32-1     

Minimal splines and wavelets

This paper is dedicated to the memory of the prominent mathematician S.G. Mikhlin. Here, Mikhlin’s idea of approximation relations is used for construction of wavelet resolution in the case of spline spaces of zero height. These approximation relations allow one to establish the embedding of the spline spaces corresponding to nested grids. Systems of functionals which are biorthogonal to the basic splines are constructed using the relations; then the systems obtained are used for wavelet decomposition. It is established that, for a fixed pair of grids of which one is embedded into the other and for an arbitrary fixed (on the coarse grid) spline space, there exists a continuum of spline spaces (on the fine grid) which contain the aforementioned spline space on the coarse grid. The wavelet decomposition of such embedding is given and the corresponding formulas of decomposition and formulas of reconstruction are deduced. The space of ( , φ)-splines is introduced with three objects: the full chain of vectors, prescribed infinite grid on real axis and the preassigned vector-function φ with m + 1 components (m is called the order of the splines). Under certain assumptions, the splines belong to the class C ^{m ? 1}. The gauge relations between the basic splines on the coarse grid and the basic splines on the fine grid are deduced. A general method for construction of a biorthogonal system of functionals (to basic spline system) is suggested. In this way, a chain of nested spline spaces is obtained, and the wavelet decomposition of the chain is discussed. The spaces and chains of spaces are completely classified in the terms of manifolds. The manifold of spaces considered is identified with the manifold of complete sequences of points of the direct product of an interval on the real axis and the projective space ? ^m ; the manifold of nested spaces is identified with the manifold of nested sequences of points of the direct product mentioned above.     

Natural spline block implicit methods

Two classes of one-step methods for the solution of the ordinary initial value problem are treated. The schemes of orderm give blocks ofm approximate solutions at each step and are constructed fromm integration formulas. Since each formula is obtained by the integration of an interpolatory natural spline, it is best in the sense of Sard. Sufficient conditions for the convergence of the iterative techniques used in each block and of the discrete variable solutions are given. The notion of block stability is introduced and the regions of block stability are given for two methods. Finally, eight block methods are compared by means of some numerical data.Also, Department of Chemical and Petroleum Engineering.     

Error bounds for derivative estimates based on spline smoothing of exact or noisy data

Estimates are found for the L₂ error in approximating the jth derivative of a given smooth function f by the corresponding derivative of the 2mth order smoothing spline based on an n-point sample from the function. The results cover both the case of an exact sample from f and the case when the sample is subject to some random noise. In the noisy case, the estimates are for the expected value of the approximation error. These bounds show that, even in the presence of noise, the derivatives of the smoothing splines of order less than m can be expected to converge to those of f as the number of (uniform) sample points increases, and the smoothing parameter approaches zero at a rate appropriately related to m, n, and the order of differentiability of f.     

Increasing the polynomial reproduction of a quasi-interpolation operator

Quasi-interpolation is an important tool, used both in theory and in practice, for the approximation of smooth functions from univariate or multivariate spaces which contain , the d-variate polynomials of degree ≤m. In particular, the reproduction of Π_m leads to an approximation order of m+1. Prominent examples include Lagrange and Bernstein type approximations by polynomials, the orthogonal projection onto Π_m for some inner product, finite element methods of precision m, and multivariate spline approximations based on macroelements or the translates of a single spline.For such a quasi-interpolation operator L which reproduces and any r≥0, we give an explicit construction of a quasi-interpolant which reproduces Π_m+r, together with an integral error formula which involves only the (m+r+1)th derivative of the function approximated. The operator is defined on functions with r additional orders of smoothness than those on which L is defined. This very general construction holds in all dimensions d. A number of representative examples are considered.     

A spline smoothing homotopy method for nonconvex nonlinear programming

Homotopy methods are globally convergent under weak conditions and robust; however, the efficiency of a homotopy method is closely related with the construction of the homotopy map and the path tracing algorithm. Different homotopies may behave very different in performance even though they are all theoretically convergent. In this paper, a spline smoothing homotopy method for nonconvex nonlinear programming is developed using cubic spline to smooth the max function of the constraints of nonlinear programming. Some properties of spline smoothing function are discussed and the global convergence of spline smoothing homotopy under the weak normal cone condition is proven. The spline smoothing technique uses a smooth constraint instead of m constraints and acts also as an active set technique. So the spline smoothing homotopy method is more efficient than previous homotopy methods like combined homotopy interior point method, aggregate constraint homotopy method and other probability one homotopy methods. Numerical tests with the comparisons to some other methods show that the new method is very efficient for nonlinear programming with large number of complicated constraints.