Scattered data interpolation based upon generalized minimum norm networks

A generalization of G. M. Nielson's method for bivariate scattered data interpolation based upon a minimum norm network is presented. The essential part of the new method is the use of a variational principle for definition of function values as well as cross-boundary derivatives over the edges of a triangulation of the data points. We mainly discuss the case ofC ² interpolants and present some examples including quality control with systems of isophotes.     

Filling polygonal holes with minimal energy surfaces on Powell-Sabin type triangulations

In this paper we present two different methods for filling in a hole in an explicit 3D surface, defined by a smooth function f in a part of a polygonal domain D⊂R². We obtain the final reconstructed surface over the whole domain D. We do the filling in two different ways: discontinuous and continuous. In the discontinuous case, we fill the hole with a function in a Powell-Sabin spline space that minimizes a linear combination of the usual seminorms in an adequate Sobolev space, and approximates (in the least squares sense) the values of f and those of its normal derivatives at an adequate set of points. In the continuous case, we will first replace f outside the hole by a smoothing bivariate spline s_f, and then we fill the hole also with a Powell-Sabin spline minimizing a linear combination of given seminorms. In both cases, we obtain existence and uniqueness of solutions and we present some graphical examples, and, in the continuous case, we also give a local convergence result.     

Scattered and track data interpolation using an efficient strip searching procedure

A new local algorithm for bivariate interpolation of large sets of scattered and track data is presented. The method, which changes partially depending on the kind of data, is based on the partition of the interpolation domain in a suitable number of parallel strips, and, starting from these, on the construction for any data point of a square neighbourhood containing a convenient number of data points. Then, the well-known modified Shepard’s formula for surface interpolation is applied with some effective improvements. The proposed algorithm is very fast, owing to the optimal nearest neighbour searching, and achieves good accuracy. Computational cost and storage requirements are analyzed. Moreover, the efficiency and reliability of the algorithm are shown by several numerical tests, also performed by Renka’s algorithm for a comparison.     

Macro-elements and stable local bases for splines on Powell-Sabin triangulations

Macro-elements of arbitrary smoothness are constructed on Powell-Sabin triangle splits. These elements are useful for solving boundary-value problems and for interpolation of Hermite data. It is shown that they are optimal with respect to spline degree, and we believe they are also optimal with respect to the number of degrees of freedom. The construction provides local bases for certain superspline spaces defined over Powell-Sabin refinements. These bases are shown to be stable as a function of the smallest angle in the triangulation, which in turn implies that the associated spline spaces have optimal order approximation power.

     

Scattered data quasi‐interpolation on spheres

This paper studies the construction and approximation of quasi‐interpolation for spherical scattered data. First of all, a kind of quasi‐interpolation operator with Gaussian kernel is constructed to approximate the spherical function, and two Jackson type theorems are established. Second, the classical Shepard operator is extended from Euclidean space to the unit sphere, and the error of approximation by the spherical Shepard operator is estimated. Finally, the compact supported kernel is used to construct quasi‐interpolation operator for fitting spherical scattered data, where the spherical modulus of continuity and separation distance of scattered sampling points are employed as the measurements of approximation error. Copyright © 2014 John Wiley & Sons, Ltd.     

Scattered data interpolation by bivariate C1-piecewise quadratic functions

In this paper, we propose a completely local scheme based on continuously differentiable quadratic piecewise polynomials for interpolating scattered positional data in the plane, in such a way that quadratic polynomials are reproduced exactly. We present some numerical examples and applications to contour plotting.     

Complexity-penalized estimation of minimum volume sets for dependent data

A minimum volume (MV) set, at level α, is a set having minimum volume among all those sets containing at least α probability mass. MV sets provide a natural notion of the ‘central mass’ of a distribution and, as such, have recently become popular as a tool for the detection of anomalies in multivariate data. Motivated by the fact that anomaly detection problems frequently arise in settings with temporally indexed measurements, we propose here a new method for the estimation of MV sets from dependent data. Our method is based on the concept of complexity-penalized estimation, extending recent work of Scott and Nowak for the case of independent and identically distributed measurements, and has both desirable theoretical properties and a practical implementation. Of particular note is the fact that, for a large class of stochastic processes, choice of an appropriate complexity penalty reduces to the selection of a single tuning parameter, which represents the data dependency of the underlying stochastic process. While in reality the dependence structure is unknown, we offer a data-dependent method for selecting this parameter, based on subsampling principles. Our work is motivated by and illustrated through an application to the detection of anomalous traffic levels in Internet traffic time series.     

Nonconforming P1 elements on distorted triangulations: Lower bounds for the discrete energy norm error

Compared to conforming P1 finite elements, nonconforming P1 finite element discretizations are thought to be less sensitive to the appearance of distorted triangulations. E.g., optimal-order discrete H¹ norm best approximation error estimates for H² functions hold for arbitrary triangulations. However, the constants in similar estimates for the error of the Galerkin projection for second-order elliptic problems show a dependence on the maximum angle of all triangles in the triangulation. We demonstrate on an example of a special family of distorted triangulations that this dependence is essential, and due to the deterioration of the consistency error. We also provide examples of sequences of triangulations such that the nonconforming P1 Galerkin projections for a Poisson problem with polynomial solution do not converge or converge at arbitrarily low speed. The results complement analogous findings for conforming P1 finite elements.     

Smoothing noisy data for irregular regions using penalized bivariate splines on triangulations

The penalized spline method has been widely used for estimating univariate smooth functions based on noisy data. This paper studies its extension to the two-dimensional case. To accommodate the need of handling data distributed on irregular regions, we consider bivariate splines defined on triangulations. Penalty functions based on the second-order derivatives are employed to regularize the spline fit and generalized cross-validation is used to select the penalty parameters. A simulation study shows that the penalized bivariate spline method is competitive to some well-established two-dimensional smoothers. The method is also illustrated using a real dataset on Texas temperature.     

Iterative polynomial interpolation and data compression

In this paper we look at some iterative interpolation schemes and investigate how they may be used in data compression. In particular, we use the pointwise polynomial interpolation method to decompose discrete data into a sequence of difference vectors. By compressing these differences, one can store an approximation to the data within a specified tolerance using a fraction of the original storage space (the larger the tolerance, the smaller the fraction).We review the iterative interpolation scheme, describe the decomposition algorithm and present some numerical examples. The numerical results are that the best compression rate (ratio of non-zero data in the approximation to the data in the original) is often attained by using cubic polynomials and in some cases polynomials of higher degree.This work was supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF).     

Application of the string method to compute minimum energy paths for a chain of bi-stable elements using the finite element method and molecular dynamics

Activated processes are frequently found in solid state mechanics. The energy landscape of such processes show a non-convex behaviour, and therefore the computation of energy barriers between two stable minima is of importance. Such barriers are revealed by computing minimum energy paths. The string method is a simple and efficient algorithm to move curves over an energy landscape and to identify minimum energy paths. A hierarchical two-scale model recently introduced to the literature (molecular dynamics coupled with the finite element method) is used in this paper to investigate the string method in a model phase transition in a copper single crystal. To do so, bi-stable elements are constructed and the energetic behaviour of a two-elements chain is investigated. We identify successfully the minimum energy path between two local stable minima of the chain and demonstrate thereby the performance of the string method applied to a complex multiscale model. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A minimum energy problem and Dirichlet spaces

We analyze a minimum energy problem for a discrete electrostatic model in the complex plane and discuss some applications. A natural characteristic distinguishing the state of minimum energy from other equilibrium states is established. It enables us to gain insight into the structure of positive trigonometric polynomials and Dirichlet spaces associated with finitely atomic measures. We also derive a related family of linear second order differential equations with polynomial solutions.

     

Finding the maximum and minimum elements with one lie

In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size n using pairwise comparisons if one of the comparisons might be erroneous and prove a conjecture of Aigner stating that the minimum number of comparisons needed is for some constant c. We also address some related problems.     

Learning mixtures of polynomials of multidimensional probability densities from data using B-spline interpolation

Non-parametric density estimation is an important technique in probabilistic modeling and reasoning with uncertainty. We present a method for learning mixtures of polynomials (MoPs) approximations of one-dimensional and multidimensional probability densities from data. The method is based on basis spline interpolation, where a density is approximated as a linear combination of basis splines. We compute maximum likelihood estimators of the mixing coefficients of the linear combination. The Bayesian information criterion is used as the score function to select the order of the polynomials and the number of pieces of the MoP. The method is evaluated in two ways. First, we test the approximation fitting. We sample artificial datasets from known one-dimensional and multidimensional densities and learn MoP approximations from the datasets. The quality of the approximations is analyzed according to different criteria, and the new proposal is compared with MoPs learned with Lagrange interpolation and mixtures of truncated basis functions. Second, the proposed method is used as a non-parametric density estimation technique in Bayesian classifiers. Two of the most widely studied Bayesian classifiers, i.e., the naive Bayes and tree-augmented naive Bayes classifiers, are implemented and compared. Results on real datasets show that the non-parametric Bayesian classifiers using MoPs are comparable to the kernel density-based Bayesian classifiers. We provide a free R package implementing the proposed methods.     

Scattered data reconstruction by regularization in B-spline and associated wavelet spaces

The problem of fitting a nice curve or surface to scattered, possibly noisy, data arises in many applications in science and engineering. In this paper we solve the problem using a standard regularized least square framework in an approximation space spanned by the shifts and dilates of a single compactly supported function . We first provide an error analysis to our approach which, roughly speaking, states that the error between the exact (probably unknown) data function and the obtained fitting function is small whenever the scattered samples have a high sampling density and a low noise level. We then give a computational formulation in the univariate case when is a uniform B-spline and in the bivariate case when is the tensor product of uniform B-splines. Though sparse, the arising system of linear equations is ill-conditioned; however, when written in terms of a short support wavelet basis with a well-chosen normalization, the resulting system, which is symmetric positive definite, appears to be well-conditioned, as evidenced by the fast convergence of the conjugate gradient iteration. Finally, our method is compared with the classical cubic/thin-plate smoothing spline methods via numerical experiments, where it is seen that the quality of the obtained fitting function is very much equivalent to that of the classical methods, but our method offers advantages in terms of numerical efficiency. We expect that our method remains numerically feasible even when the number of samples in the given data is very large.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

Zero data and interpolation problems for rectangular matrix polynomials

Zero data of rectangular matrix polynomials are described in various forms. The basic interpolation problem of constructing rectangular matrix polynomials from their zero data is solved. Certain rectangular factorizations are analyzed in terms of spectral data.     

Measure data problems,lower-order terms and interpolation effects

We deal with the solutions to nonlinear elliptic equations of the form $$-{\rm div}\, a(x, Du) + g(x, u)=f$$ , with f being just a summable function, under standard growth conditions on g and a. We prove general local decay estimates for level sets of the gradient of solutions in turn implying very general estimates in rearrangement and non-rearrangement function spaces, up to Lorentz–Morrey spaces. The results obtained are in clear accordance with the classical Gagliardo–Nirenberg interpolation theory.     

Multilevel interpolation of scattered data using H ${\mathcal{H}}$ -matrices

Numerical Algorithms - Scattered data interpolation can be used to approximate a multivariate function by a linear combination of positive definite radial basis functions (RBFs). In practice, the...