Moving Least Squares without Quasi-Uniformity: A Stochastic Approach

Technical Summary: Moving Least Squares without Quasi-Uniformity: A Stochastic Approach

Problem Statement
Local Polynomial Regression (LPR) and Moving Least Squares (MLS) are algebraically equivalent nonparametric methods, yet they have evolved under distinct theoretical frameworks. LPR, rooted in statistics, analyzes convergence under random sampling assumptions, focusing on handling observational noise. Conversely, MLS, developed in numerical analysis, relies on deterministic sampling assumptions, specifically quasi-uniformity, where the fill distance ($h_n$) and separation distance ($\delta_n$) are comparable up to a constant factor.

The central problem addressed in this work is the breakdown of classical MLS theory when applied to random sampling. Under independent and identically distributed (i.i.d.) random sampling, the quasi-uniformity assumption fails: random points tend to form dense local clusters, causing the separation distance to decay at a different rate than the fill distance. This geometric instability threatens the invertibility of local design matrices and the validity of classical convergence proofs. While recent work suggested random points might be asymptotically optimal for Sobolev space approximation, a rigorous stochastic analysis proving that MLS preserves its classical derivative approximation and smoothness properties under random sampling was lacking.

Methodology
The authors adopt a purely noise-free approximation framework where the randomness arises solely from the spatial layout of the sample points. The methodology proceeds in three stages:

1. Probabilistic Characterization of Geometry: The authors first quantify the asymptotic behavior of the fill distance ($h_n$) and separation distance ($\delta_n$) for i.i.d. samples drawn from a "nicely behaving" distribution (bounded away from zero and infinity) on a domain satisfying an interior cone condition. They establish that $h_n \propto n^{-1/d} \log^{1/d}(n)$ and $\delta_n \propto n^{-2/d}$ in probability, confirming that $h_n$ and $\delta_n$ are not comparable, thus violating quasi-uniformity.
2. Stochastic Stability Analysis: To overcome the lack of quasi-uniformity, the authors adapt the deterministic proofs of Mirzaei [8] and Levin [6]. They introduce a high-probability event $E_I$ ensuring that the number of samples in local neighborhoods of radius proportional to $h_n$ grows logarithmically with $n$ (specifically, $\Theta(\log n)$). Under this event, they prove that the normalized Gram matrix (empirical weighted covariance matrix) remains positive definite and well-conditioned with high probability.
3. Derivative and Smoothness Bounds: Using the stability of the Gram matrix and its inverse, the authors derive probabilistic bounds for the derivatives of the MLS shape functions. They leverage the Bernstein inequality and union bounds to control the deviation of the empirical matrices from their theoretical counterparts.

Key Contributions and Results

• Theorem 1 (Geometric Rates): The paper establishes that for i.i.d. samples, the fill distance decays as $O_P(n^{-1/d} \log^{1/d} n)$ while the separation distance decays as $\Omega_P(n^{-2/d})$. This rigorously demonstrates the failure of the quasi-uniformity condition in stochastic settings.
• Theorem 2 (Stochastic Convergence of Derivatives): The primary contribution is proving that for a function $f \in C^k$, the error in approximating a linear differential operator $Q$ of order $m < k$ using MLS decays as $h_n^{k-m}$ with high probability. Specifically, the probability that the error exceeds $K h_n^{k-m}$ vanishes as $n \to \infty$. This establishes a stochastic analogue to the classical deterministic convergence rates, despite the absence of quasi-uniformity.
• Theorem 3 (Local Smoothness): The authors prove that the MLS approximant is locally $C^k$ smooth with high probability. Specifically, on balls of radius $\delta_0 \asymp h_n$, the approximant inherits the smoothness of the weight function. This result relies on the fact that while the normalized Gram matrix involves a discontinuous sample count, the unnormalized Gram matrix varies smoothly with the evaluation point, ensuring the invertibility and smoothness of the shape functions locally.
• Resolution of the Quasi-Uniformity Bottleneck: The work demonstrates that the algebraic stability of local design matrices is preserved under random sampling, provided the sample density is sufficient (logarithmic growth in local neighborhoods). This allows the extension of deterministic derivative approximation results to purely random configurations.

Significance and Claims
The paper claims to provide the first unified stochastic analysis of MLS. Its significance lies in bridging the gap between the statistical tradition of LPR and the numerical analysis tradition of MLS. The authors demonstrate that the classical convergence rates and smoothness properties of MLS are not artifacts of deterministic, quasi-uniform sampling but persist under natural probabilistic models.

Crucially, the authors distinguish their work from standard statistical LPR analysis by focusing on the functional behavior of the MLS approximant (a single function defined over the domain) rather than point-wise estimates. This is a critical prerequisite for applications such as solving partial differential equations (PDEs) using meshless methods, where the global smoothness and differentiability of the approximation are required.

The paper is modest regarding the scope of smoothness: it establishes local smoothness on balls scaled by the fill distance. The authors explicitly note that achieving a global smoothness statement would require enlarging the bandwidth, which would degrade the approximation rate. Since their setting is noise-free, this degradation represents a genuine loss of accuracy, unlike in noisy settings where the noise floor might absorb such a trade-off. Therefore, they retain the sharp local result.

Finally, the authors indicate that these results lay the groundwork for future extensions to Stochastic Manifold Moving Least Squares (MMLS) for data sampled from unknown Riemannian manifolds, a topic reserved for a companion study.