A case of multivariate Birkhoff interpolation using high order derivatives

Gil GoldmanJ. Approx. Theory 2017 · DOI

TL;DR

This paper introduces a specific scheme for multivariate Birkhoff interpolation, which uses high-order derivatives sampled along specific directions. The authors establish conditions for the regularity of this interpolation problem, showing it depends only on the directions of sampling, not the points themselves. They also derive a "Birkhoff-Remez" inequality that bounds the interpolation polynomial's norm by the norm of its samples, offering insights into the robustness of polynomial reconstruction.

What Problem Does This Paper Address?

The paper tackles a fundamental problem in approximation theory: multivariate polynomial interpolation. Specifically, it focuses on Birkhoff interpolation, a generalization of Hermite interpolation that allows for directional derivatives. The challenge lies in determining when such an interpolation problem is "regular," meaning it has a unique solution for any set of given derivative values. Traditional interpolation problems can be sensitive to the choice of sampling points and directions. This work aims to simplify the regularity conditions for a particular Birkhoff scheme and to provide a quantitative estimate of how well a polynomial can be reconstructed from potentially noisy derivative samples. This is crucial for understanding the stability and accuracy of numerical methods that rely on polynomial approximation.

Methods

The authors introduce a specific scheme for multivariate Birkhoff interpolation where samples are derivatives of various orders at fixed points, taken along fixed straight lines. A key assumption is that the total number of sampled derivatives of order $k$ equals the dimension of the space of homogeneous polynomials of degree $k$.

The core of their approach involves:

  • Regularity Analysis: They connect the regularity of their Birkhoff interpolation problem to the regularity of simpler, related problems involving homogeneous polynomials. This is achieved by analyzing the determinant of a multidimensional Vandermonde-like matrix.
  • Reduction to Homogeneous Polynomials: They show that the regularity of the overall problem depends on the regularity of sub-problems for homogeneous polynomials of each degree $k$.
  • Birkhoff-Remez Inequality: They extend the concept of Remez-type inequalities to this Birkhoff interpolation setting. This involves defining "norming sets" of linear functionals (representing derivative samples) and deriving bounds on the norm of the interpolating polynomial based on the geometry of these sampling sets.
  • Induction and Recurrence Relations: The proofs for the norming inequalities often rely on inductive arguments, particularly for bounding the norming constants for polynomials of decreasing degrees.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects of polynomial interpolation and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Direction-Dependent Regularity: A significant finding is that the regularity of this specific Birkhoff interpolation scheme depends only on the directions of the sampling lines, not on the positions of the sampling points. This simplifies the conditions for well-posedness.
  • Connection to Homogeneous Polynomials: The problem's regularity can be fully characterized by the regularity of related interpolation problems for homogeneous polynomials of each degree.
  • Birkhoff-Remez Inequality for Robustness: The derived "Birkhoff-Remez" inequality provides a theoretical guarantee for the robustness of polynomial reconstruction. It quantifies how well a polynomial can be recovered from noisy derivative samples, showing that the error is bounded by the norming constant (related to the sampling geometry), the ideal approximation error, and the measurement noise.
  • Planar Case Simplification: In the planar case ($n=2$), the regularity condition simplifies to requiring that the sampling directions for each degree are pairwise linearly independent.

Key Results

  • Theorem 2.1: The proposed Birkhoff interpolation scheme is regular for general directions, and the conditions for non-regularity are precisely characterized by the directions forming roots of certain homogeneous polynomials. This result is independent of the sampling points.
  • Theorem 3.1: A "Birkhoff-Remez" inequality is established, bounding the norm of an interpolating polynomial by the norm of its samples and the norming constant of the sampling directions. This provides an estimate for the error in polynomial reconstruction.
  • Corollary 3.1: For the planar case, regularity is achieved if the sampling directions for each degree are pairwise linearly independent.

Limitations and Future Work

  • Generalization of Markov Inequalities: The authors note that their proof of the Birkhoff-Remez inequality uses a standard Markov inequality for bounding derivatives. They suggest that sharper bounds might be achievable by using more advanced Markov-type inequalities for constrained polynomials, which could lead to improved norming constants.
  • Univariate Case Exploration: The paper briefly touches upon the univariate case ($n=1$) and suggests that for certain configurations of points, the norming constant might remain bounded. However, a deeper analysis of this case and its implications for reconstruction accuracy with permuted sampling sequences is proposed as an interesting and challenging future direction.
  • Specific Configurations: The authors express interest in exploring bounds for specific configurations of points in the univariate case, particularly concerning the effect of permuting sampling points on reconstruction accuracy.

Summary updated

BibTeX
@article{goldman2017case,
  author = {Gil Goldman},
  title = {{A case of multivariate Birkhoff interpolation using high order derivatives}},
  journal = {J. Approx. Theory},
  year = {2017},
  doi = {10.1016/j.jat.2017.07.010},
}

Loading related content...

Figure