Monotonicity preserving approximation of multivariate scattered data

This paper describes a new method of monotone interpolation and smoothing of multivariate scattered data. It is based on the assumption that the function to be approximated is Lipschitz continuous. The method provides the optimal approximation in the worst case scenario and tight error bounds. Smoothing of noisy data subject to monotonicity constraints is converted into a quadratic programming problem. Estimation of the unknown Lipschitz constant from the data by sample splitting and cross-validation is described. Extension of the method for locally Lipschitz functions is presented.

Interpolation of Lipschitz functions

This paper describes a new computational approach to multivariate scattered data interpolation. It is assumed that the data is generated by a Lipschitz continuous function f. The proposed approach uses the central interpolation scheme, which produces an optimal interpolant in the worst case scenario. It provides best uniform error bounds on f, and thus translates into reliable learning of f. This paper develops a computationally efficient algorithm for evaluating the interpolant in the multivariate case. We compare the proposed method with the radial basis functions and natural neighbor interpolation, provide the details of the algorithm and illustrate it on numerical experiments. The efficiency of this method surpasses alternative interpolation methods for scattered data.

Construction of aggregation operators for automated decision making via optimal interpolation and global optimization

This paper examines methods of point wise construction of aggregation operators via optimal interpolation. It is shown that several types of application-specific requirements lead to interpolatory type constraints on the aggregation function. These constraints are translated into global optimization problems, which are the focus of this paper. We present several methods of reduction of the number of variables, and formulate suitable numerical algorithms based on Lipschitz optimization.

Review of applications of the Cutting Angle methods

The theory of abstract convexity provides us with the necessary tools for building accurate one-sided approximations of functions. Cutting angle methods have recently emerged as a tool for global optimization of families of abstract convex functions. Their applicability have been subsequently extended to other problems, such as scattered data interpolation. This paper reviews three different applications of cutting angle methods, namely global optimization, generation of nonuniform random variates and multivatiate interpolation.

Monotone approximation of aggregation operators using least squares splines

The need for monotone approximation of scattered data often arises in many problems of regression, when the monotonicity is semantically important. One such domain is fuzzy set theory, where membership functions and aggregation operators are order preserving. Least squares polynomial splines provide great flexbility when modeling non-linear functions, but may fail to be monotone. Linear restrictions on spline coefficients provide necessary and sufficient conditions for spline monotonicity. The basis for splines is selected in such a way that these restrictions take an especially simple form. The resulting non-negative least squares problem can be solved by a variety of standard proven techniques. Additional interpolation requirements can also be imposed in the same framework. The method is applied to fuzzy systems, where membership functions and aggregation operators are constructed from empirical data.

Smoothing Lipschitz functions

This paper describes a new approach to multivariate scattered data smoothing. It is assumed that the data are generated by a Lipschitz continuous function f, and include random noise to be filtered out. The proposed approach uses known, or estimated value of the Lipschitz constant of f, and forces the data to be consistent with the Lipschitz properties of f. Depending on the assumptions about the distribution of the random noise, smoothing is reduced to a standard quadratic or a linear programming problem. We discuss an efficient algorithm which eliminates the redundant inequality constraints. Numerical experiments illustrate applicability and efficiency of the method. This approach provides an efficient new tool of multivariate scattered data approximation.

Path planning for sensor data collecting mobile robot

A mobile robot employed for data collection is faced with the problem of travelling from an initial location to a final location while maintaining as close a distance as possible to all the sensors at a given time in the journey. Here we employ optimal control ideas in forming the necessary control commands for such a robot resulting not only the necessary acceleration commands for the underlying robot, but also the resulting trajectory. This approach can also be easily extended for the case of producing the optimal trajectory for an ariel vehicle used for data collection from indiscriminately scattered ad-hoc sensors located on the ground. We demonstrate the implementation of our algorithm using a Pioneer 3-AT robot.

Can the choice of interpolation method explain the difference between swap prices and futures prices?

The standard model linking the swap rate to the rates in a contemporaneous strip of futures interest rate contracts typically produces biased estimates of the swap rate. Institutional differences usually require some form of interpolation to be employed and may in principle explain this empirical result. Using Australian data, we find evidence consistent with this explanation and show that model performance is greatly improved if an alternative interpolation method is used. In doing so, we also provide the first published Australian evidence on the accuracy of the futures-based approach to pricing interest rate swaps.

Parallel monotone spline interpolation and approximation on GPUs

Monotonicity preserving interpolation and approximation have received substantial attention in the last thirty years because of their numerous applications in computer aided-design, statistics, and machine learning [9, 10, 19]. Constrained splines are particularly popular because of their flexibility in modeling different geometrical shapes, sound theoretical properties, and availability of numerically stable algorithms [9,10,26]. In this work we examine parallelization and adaptation for GPUs of a few algorithms of monotone spline interpolation and data smoothing, which arose in the context of estimating probability distributions.

Improving cloud-based online social network data placement and replication

Online social networks make it easier for people to find and communicate with other people based on shared interests, values, membership in particular groups, etc. Common social networks such as Facebook and Twitter have hundreds of millions or even billions of users scattered all around the world sharing interconnected data. Users demand low latency access to not only their own data but also theirfriends’ data, often very large, e.g. videos, pictures etc. However, social network service providers have a limited monetary capital to store every piece of data everywhere to minimise users’ data access latency. Geo-distributed cloud services with virtually unlimited capabilities are suitable for large scale social networks data storage in different geographical locations. Key problems including how to optimally store and replicate these huge datasets and how to distribute the requests to different datacenters are addressed in this paper. A novel genetic algorithm-based approach is used to find a near-optimal number of replicas for every user’s data and a near-optimal placement of replicas to minimise monetary cost while satisfying latency requirements for all users. Experiments on a large Facebook dataset demonstrate our technique’s effectiveness in outperforming other representative placement and replication strategies.