Source-linked AI summary
Radial Basis Function Approximations: Comparison and Applications
Zuzana Majdisova, Vaclav Skala
TL;DR
The paper addresses approximation of large scattered datasets without converting them into ordered meshes, using RBF formulations based on linear systems. It compares several methods for stability and accuracy and reports that the proposed approximation gives the best error results while using a smaller M × M matrix when M ≪ N. The authors also report that global functions have difficulty preserving sharp edges.
Problem
Approximating large scattered datasets requires methods that handle unordered points while controlling computational cost and accuracy.
Method
The paper introduces and compares RBF approximation methods, including Lagrange-multiplier, polynomial-reproduction, and reduced-reference-point formulations.
Results
The proposed RBF approximation gives the best results due to the smallest error, while Lagrange multipliers produce the worst error and a high-dimensional matrix.
Takeaways & Limitations
The proposed method offers significantly better results and possible data compression because its matrix is M × M with M ≪ N.
Takeaways & Limitations
All evaluated methods have problems preserving sharp edges when global functions are used.
Abstract
from arXiv · showhide
Approximation of scattered data is often a task in many engineering problems. The Radial Basis Function (RBF) approximation is appropriate for large scattered (unordered) datasets in d-dimensional space. This approach is useful for a higher dimension d>2, because the other methods require the conversion of a scattered dataset to an ordered dataset (i.e. a semi-regular mesh is obtained by using some tessellation techniques), which is computationally expensive. The RBF approximation is non-separable, as it is based on the distance between two points. This method leads to a solution of Linear System of Equations (LSE) Ac=h. In this paper several RBF approximation methods are briefly introduced and a comparison of those is made with respect to the stability and accuracy of computation. The proposed RBF approximation offers lower memory requirements and better quality of approximation.
1. Introduction
RBF approximation is a meshless approach for scattered data that applies across spatial dimensions and avoids converting unordered data into an ordered mesh. Its computational cost grows nonlinearly with dataset size, while global and compactly supported RBFs present different efficiency and sensitivity trade-offs.
- Overview: RBF approximation is a meshless technique based on collocation at scattered nodes and applicable across spatial dimensions.It has been used in engineering, science, neural networks, visualization, medical applications, and surface reconstruction.
- Overview: The method avoids ordering scattered data, making it suitable for datasets whose points are not arranged on a regular structure.
- Computational characteristics: Computational cost increases nonlinearly with the number of data points and linearly with data dimensionality.
- RBF classes: Compactly supported RBFs produce sparse linear systems and faster computations but are sensitive to data density and the shape parameter.
- RBF classes: Global RBFs produce dense systems and require techniques such as the fast multipole method, while supporting applications including incomplete-data repair.
2. RBF Approximation using Lagrange Multipliers
The Lagrange-multiplier formulation approximates data by minimizing a quadratic form in RBF weights subject to linear constraints. It produces a block linear system whose matrix is built from pairwise basis-function evaluations, while reducing the number of reference points lowers evaluation cost.
- Formulation: The Lagrange-multiplier method formulates RBF approximation as a constrained quadratic optimization problem.The approximant uses M RBFs associated with reference points and coefficients c.
- Formulation: The coefficient vector c is obtained by minimizing 1/2 c^TQc subject to the linear constraints Ac = h.Q is symmetric positive definite, A has full rank, and h is given.
- Solution: Introducing Lagrange multipliers converts the constrained minimization into a linear system solved for c and λ.
- Solution: The matrix entries are defined by Qi,j = φ(∥ξi − ξj∥), so the system encodes distances between reference points through the RBF.
- Computational cost: Minimizing M reduces the computational cost of evaluating the approximated function.
3. RBF Approximation
RBF approximation reduces a scattered-data problem by representing values with fewer reference-point basis functions and solving an overdetermined system. Compared with interpolation, this reduces the number of weights and can lower computational burden while retaining approximation precision.
- Motivation: RBF interpolation uses a large, usually ill-conditioned linear-system matrix, motivating reduction of basis functions and weights.The reduction aims to preserve good precision in oversampled or intentionally reduced datasets.
- Purpose: The approximation process reduces the original problem while preserving the intended approximated solution precision.
- Reference points: The approximation represents each data point with a scalar or vector value and extends the dataset with M reference points, where M ≪ N.Reference points need not form a uniform grid and can be placed along important surface features.
- Approximation model: The approximating function sums M weighted RBFs evaluated by distances between an input x and reference points ξj.
- Linear system: The resulting system is overdetermined because it contains N equations and M unknown weights, with N much larger than M.It can be solved by least squares or singular value decomposition.
4. RBF Approximation with Polynomial Reproduction
Polynomial reproduction extends the RBF approximant with a polynomial term to address potential stability and solvability problems. With linear reproduction, the system includes reference-point weights and polynomial coefficients and remains overdetermined when N exceeds the number of variables.
- Motivation: Polynomial reproduction extends the RBF approximant with a polynomial Pk(x) because the basic method can have stability and solvability problems.
- Approximation model: The approximated value combines weighted RBF terms with the polynomial component Pk(x).
- Linear reproduction: In practice, the method uses a linear polynomial whose constant coefficient sets hyperplane placement and whose a^Tx term sets inclination.
- System size: For d-dimensional space, the system has N equations and M+d+1 variables, where M is the number of reference points.For d = 2, the spatial vectors are represented by xi = (xi, yi)^T and a = (ax, ay)^T.
- Solution: The system is overdetermined when N exceeds M+d+1 and can be solved using least squares or singular value decomposition.
5. Experimental Results
The experiments tested RBF approximation methods on synthetic and real datasets using varied global basis functions, shape parameters, and reference-point distributions.
- Experiments covered both synthetic and real datasets.
- The tests varied global radial basis functions and their shape parameter α.The tested global functions and α values are listed in Table 1.
- Reference points were tested using multiple distribution types described in Sect. 5.1.
Points on regular grid
One tested reference-point set places points on a regular grid in E2, alongside the global RBF configurations listed in Table 1.
- Points on regular grid: The reference-point set contains points on a regular grid in E2.
- Points on regular grid: The experiments used global RBFs with α as a shape parameter.
- Points on regular grid: Table 1 identifies the global RBF configurations used in the experiments.
Epsilon points
Another reference-point distribution is described separately in the paper's subsequent method text.
- Epsilon points: This reference-point distribution is described in the following text.
- Epsilon points: The distribution is treated as a distinct reference-point set in the experiments.
- Epsilon points: Its construction is specified after the introductory description.
Epsilon points + AABB corners
A reference-point set is formed as in the previous case, then augmented with the corners of the points' axis-aligned bounding box.
- Epsilon points + AABB corners: The set is determined in the same manner as the previous reference-point case.
- Epsilon points + AABB corners: Corners of the axis-aligned bounding box of Epsilon points are added to the reference-point set.
- Epsilon points + AABB corners: The resulting set combines the previous construction with AABB-corner points.
Halton points
The reference points for the RBF approximation are selected as a subset of the given dataset.
- Reference points are chosen from the given dataset to determine the RBF approximation.
Halton points + AABB corners
The paper compares Halton, epsilon, and regular-grid reference-point distributions across synthetic and real datasets. Halton points cover 2D space more evenly than uniformly random points, while approximation quality depends on the method, basis function, shape parameter, and reference-point placement.
- Halton points + AABB corners: Reference points are generated from a deterministic Halton sequence based on prime-number divisions of [0, 1].For E2, the bases 2 and 3 generate points in a rectangle, whose width and height are denoted by a and b.
- Halton points + AABB corners: Halton points cover E2 more evenly than uniformly random points in the same rectangle.The comparison uses 103 points in each distribution.
- Halton points + AABB corners: Epsilon points perturb regular-grid locations using uniformly distributed random drifts in the x and y directions.The construction uses grid spacings Δx and Δy together with grid dimensions Nx and Ny.
- Halton points + AABB corners: On the synthetic sinc dataset, Lagrange-multiplier RBF approximation has higher error than the proposed methods, while TPS produces much higher errors across methods.The comparison uses 1089 Halton data points and 81 Halton reference points; Gaussian and inverse-quadric bases perform best at α = 1 and α = 0.5, respectively, whereas TPS is unsuitable for this problem.
- Halton points + AABB corners: The proposed approximation and linear-reproduction variant have similar errors, but their performance varies with reference-point placement and shape parameter.Regular-grid reference points are worst for all variants; epsilon points plus AABB corners are usually best for linear reproduction, while Halton points are best for the Lagrange-multiplier method.
- Halton points + AABB corners: For real terrain data, increasing reference points improves approximation and reveals surface details, but global Gaussian and TPS bases cannot preserve sharp ridges.For the terrain dataset, TPS error decreases with more reference points and is largely independent of α; IQ gives the best error while TPS gives the worst.
6. Conclusion
The proposed RBF approximation achieves the smallest errors and uses a smaller M × M matrix, while global functions struggle to preserve sharp edges.
- The proposed RBF approximation gives the best results, with the smallest error among the compared methods.
- The Lagrange-multiplier method performs worst, behaves unpredictably, and typically uses an ill-conditioned (M + N) × (M + N) matrix.
- The proposed method uses an M × M matrix with M ≪ N, offering possible data compression for large datasets.
- All tested methods have difficulty preserving sharp edges when global basis functions are used.
- Future work will evaluate compactly supported RBFs for sparse matrices, lower memory requirements, faster computation, and optimized shape parameters.