Controlling the Condition Number of Multiquadric RBF Matrices via Poisson Disk Sampling

Technical Summary: Controlling the Condition Number of Multiquadric RBF Matrices via Poisson Disk Sampling

Problem Statement
Radial Basis Function (RBF) interpolation is a robust method for approximating functions from scattered data, particularly using the Multiquadric (MQ) function due to its spectral accuracy and geometric flexibility. However, a significant numerical challenge persists: the interpolation matrix $A$ often becomes severely ill-conditioned. This ill-conditioning arises when interpolation centers are too close together or when the shape parameter $c$ is large, leading to numerical instability and potential failure in solving the linear system $A\Lambda = F$. While previous literature has established that matrix conditioning depends on the geometry of centers and the fill distance, there is a lack of specific strategies to control the growth of the condition number $\kappa(A)$ as the number of points $N$ increases within a fixed domain.

Methodology
This work investigates the relationship between the geometric distribution of interpolation centers and the condition number of the MQ matrix by imposing Poisson Disk Sampling constraints. The study employs a two-pronged approach:

1. Theoretical Analysis:

   • Spectral Analysis: The MQ function is expanded via Taylor series around $r=0$ (assuming $r \ll c$). The resulting matrix $A$ is approximated as a linear combination of the identity matrix $I$ and the all-ones matrix $J$.
   • Quasi-Uniform Case: For points distributed with a characteristic distance $r_0$, the eigenvalues are derived explicitly. The analysis identifies a dominant eigenvalue (constant mode) and $N-1$ oscillatory modes.
   • Unstructured Case: Using first-order matrix perturbation theory, the eigenvalues are approximated for general scattered points. The condition number is expressed as a function of $N$, the shape parameter $c$, and the effective variance of inter-point distances.
   • Optimization: The study seeks to minimize $\kappa(A)$ by determining the optimal relationship between the minimum separation distance $r_{min}$ (or characteristic distance $r_0$), the shape parameter $c$, and the number of points $N$.

2. Numerical Experiments:

   • Simulations were conducted in $\mathbb{R}^2$ with a fixed shape parameter $c=0.15$.
   • Three strategies for choosing the minimum separation distance $r_{min}$ were compared:
     1. Fixed: A constant $r_{min} = 0.05$ regardless of $N$.
     2. Quasi-Uniform Optimal: $r_{min} = c/\sqrt{2}$, derived from minimizing the condition number for quasi-uniform distributions.
     3. Adaptive/N-Dependent: $r_{min}(N) = \frac{c}{\sqrt{K}}\sqrt{\frac{N}{N-1}}$, derived from the optimality condition $d\kappa/dN = 0$ for unstructured points, where $K$ is a constant chosen to minimize the average condition number.

Key Contributions

• Derivation of Optimal Separation: The paper derives that for quasi-uniform distributions, the condition number is minimized when the characteristic distance satisfies $r_0 = c/\sqrt{2}$, yielding a minimum condition number of $\kappa_{min} = 3N + 1$.
• Constant Condition Number Strategy: Crucially, for unstructured points, the authors derive a functional relationship between $c$, $N$, and the effective distance $\sigma_{eff}$ (related to $r_{min}$) such that the condition number becomes independent of $N$. Specifically, if $c^2 / \sigma_{eff}^2 = K \frac{N-1}{N}$, the condition number stabilizes at $\kappa(A) = 1 + 2K$.
• Poisson Disk Implementation: The work demonstrates how Poisson Disk Sampling can be parameterized to satisfy these theoretical constraints, effectively controlling the growth of ill-conditioning.

Results
Numerical experiments in $\mathbb{R}^2$ validated the theoretical predictions:

• Fixed Strategy: With a fixed $r_{min}$, the condition number grew exponentially, reaching values as high as $6.33 \times 10^{17}$ for $N=1955$, confirming severe ill-conditioning.
• Quasi-Uniform Strategy ($r_{min} = c/\sqrt{2}$): This approach reduced the condition number significantly compared to the fixed case, with values ranging from 30.57 to 452.00. However, it still exhibited linear growth consistent with the theoretical prediction of $3N+1$.
• Adaptive Strategy ($r_{min}(N)$): The N-dependent optimized strategy successfully maintained the condition number in a remarkably low and stable range (1.00 to 10.48, with a mean of 4.14) across the entire range of $N$ tested (5 to 1955). This confirmed the theoretical claim that $\kappa(A)$ can be kept constant and close to $1+2K \approx 1.11$, independent of the number of centers.

Significance and Claims
The paper claims that the proposed adaptive choice of the Poisson Disk minimum distance provides a rigorous mathematical and numerical justification for controlling the condition number of Multiquadric RBF matrices. By establishing an optimal functional relationship between the shape parameter, the number of points, and the sampling distance, the method ensures uniform spectral stability. The authors assert that this strategy offers a robust alternative for meshless methods, particularly in applications involving irregular geometries (such as PDE solvers, geostatistics, and computer graphics), where traditional fixed or arbitrary point distributions lead to numerical instability. The work suggests that the linear growth of the condition number with $N$ is not an inherent limitation of MQ-RBFs but can be eliminated through adaptive center generation.

Limitations
The authors note that the analysis relies on the Taylor expansion assumption $r \ll c$, which may require higher-order terms for small shape parameters or widely spaced points. Additionally, generating Poisson Disk configurations becomes computationally expensive for very large $N$ ($N \gg 2000$). Future work is suggested to extend these findings to other RBFs and three-dimensional domains.