Some Sharp Error Bounds for Multivariate Linear Interpolation and Extrapolation

Liyuan Cao, Zaiwen Wen, Ya-Xiang YuanarXiv 2022 · OpenReview

Abstract

We study in this paper the function approximation error of linear interpolation and extrapolation. Several upper bounds are presented along with the conditions under which they are sharp. All results are under the assumptions that the function has Lipschitz continuous gradient and is interpolated on an affinely independent sample set. Errors for quadratic functions and errors of bivariate linear extrapolation are analyzed in depth.

Introduction

Linear interpolation is a fundamental tool in numerical analysis, essential for methods ranging from finite element analysis to derivative-free optimization (DFO). While error bounds for interpolation—predicting values within the convex hull of sample points—are well-established, the accuracy of extrapolation (predicting values outside this hull) has remained a significant challenge due to the complex influence of sample point geometry. This paper addresses this gap by providing new, "sharp" (mathematically tight) upper bounds for linear interpolation and extrapolation errors, specifically for functions with Lipschitz continuous gradients.

Problem Formulation

In DFO, algorithms frequently predict function values at points distant from the current sample set. Existing error bounds often fail to account for the specific geometry of the sample points, such as "skinny" or "obtuse" configurations, leading to overly conservative estimates. The authors aim to determine the absolute maximum possible error for any given sample set and target point, assuming only that the function's gradient is Lipschitz continuous.

Methodology

The research approaches the error bound problem through a dual optimization lens:

  1. Minimizing the Upper Bound: The authors generalize the standard Taylor expansion by expanding the function around an optimal center $u$, then optimizing $u$ to minimize the resulting error bound.
  2. Maximizing the Error: They identify the "worst-case" function—typically a quadratic function—that maximizes the error for a given point set to prove the bound's sharpness.

Key mathematical frameworks employed include barycentric coordinates to define target point positions, eigendecomposition of a geometry matrix $G$ to capture sample set orientation, and piecewise quadratic constructions.

Key Insights

  • The Optimal Center ($w$): The tightest error bound is achieved by calculating a weighted center $w$ based on the absolute values of the target point's barycentric coordinates.
  • Geometric Sensitivity: The difficulty of finding sharp bounds increases significantly with "obtuse" geometries (where angles between sample points exceed 90 degrees). While non-obtuse cases often follow a single formula, obtuse geometries necessitate more complex, asymmetric bounds.
  • Quadratic Worst-Cases: In many scenarios, the maximum error is produced by a quadratic function whose Hessian aligns with the principal directions of the sample set's geometry.

Key Results

The authors introduced a generalized upper bound: $$|m(y_0) - f(y_0)| \le \frac{L}{2} \sum_{i=0}^{n+1} |\ell_i| \|y_i - w\|^2$$ where $w$ is an optimized center point. This bound is proven sharp for specific "cone" regions during extrapolation. For the bivariate case ($n=2$), the paper provides a complete set of formulas for sharp error bounds that cover both interpolation and extrapolation regions, resolving issues in previously loose obtuse regions.

Visualization of regions covered by different theorems: (a) interpolation area, (b) extrapolation cones, and (c) regions where sharpness is harder to prove.

Limitations and Future Work

While the 2D case is fully resolved, extending these results to higher dimensions ($n \ge 3$) is complex due to the exponential growth in the types of "obtuse" simplices. Additionally, calculating the sharpest bound requires eigendecomposition, which may introduce computational overhead in high-dimensional optimization loops. Future research remains open for finding sharp bounds for gradient error ($\|\nabla m - \nabla f\|$), a non-convex and significantly harder problem.

Summary updated

Abstract

We study in this paper the function approximation error of linear interpolation and extrapolation. Several upper bounds are presented along with the conditions under which they are sharp. All results are under the assumptions that the function has Lipschitz continuous gradient and is interpolated on an affinely independent sample set. Errors for quadratic functions and errors of bivariate linear extrapolation are analyzed in depth.
BibTeX
@misc{cao2022some,
  author = {Liyuan Cao and Zaiwen Wen and Ya-Xiang Yuan},
  title = {{Some Sharp Error Bounds for Multivariate Linear Interpolation and Extrapolation}},
  year = {2022},
  eprint = {2209.12606},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.12606},
}
Figure