0
$\begingroup$

It is well known that in the univariate case, to interpolate $k$ points in $\mathbb{R}$, we need to use a polynomial of degree $k-1$.

My question is about multivariate polynomial interpolation in higher dimension. We are given $k$ points $x_1,\ldots,x_k$ in $\mathbb{R}^d$. Define the max-deg of a multivariate polynomial to be the maximum exponent of any variable. For example, the max-deg of the linear function $x_1+x_2+x_3$ is 1 and the max-deg $x_1^2+x_2$ is 2. My question is: given $x_1,\ldots,x_n$, what is the minimum $d$ such that for any $y_1,\ldots, y_d$, there is a polynomial $P$ of max-deg $d$ such that $P(x_i)=y_i\forall i$. The answer should really depend on the configuration of $x_1 ,\ldots,x_k$. For example, if $x_1 ,\ldots,x_k$ are linearly independent, we only need max-deg to be 1 (i.e., we can use a linear function to intepolate it).

Has the same problem (or some thing similar) been studied before?

$\endgroup$
  • 1
    $\begingroup$ Same as before, $d=k-1$. You can't improve on this because the points could be on a coordinate axis. Conversely, you can interpolate with polynomials of this max-deg. $\endgroup$ – Christian Remling Oct 11 '14 at 4:25
  • $\begingroup$ I am not looking for the worse case scenorios. The answer should really depend on the configuration of $x_1,\ldots,x_k$. For example, if $x_1,\ldots,x_k$ are linearly independent, we only need max-deg to be 1. $\endgroup$ – jian Oct 11 '14 at 11:07
  • $\begingroup$ Then you get the max-deg's between $0$ and $k-1$, since you can deliberately put some or all of your points on the graph of a given polynomial. $\endgroup$ – Christian Remling Oct 11 '14 at 16:56
  • 1
    $\begingroup$ Maybe I did not make myself clear. My question was "given $x_1,\ldots, x_n$, what the max-deg should be". We do not get to choose where $x_1,\ldots,x_n$ are, but $y_1,\ldots, y_n$ can be arbitrary. $\endgroup$ – jian Oct 12 '14 at 3:23
1
$\begingroup$

I think relevant results are summarized in part 2 "Haar spaces and multivariate polynomials" of the "Scattered Data Approximation" by Holger Wendland.

One would hope to be able to interpolate data sites $X = \{x_1,\dots, x_Q \}$ with a polynomial from $\pi_m(\mathbb{R}^d)$ when $Q=\dim \pi_m(\mathbb{R}^d)={m+d\choose d}$. Here $m$ is your "max-deg".

It is proven (Mairhuber–Curtis) to be generally impossible unless unisolvency of data sites is ensured: for example, when they are on a more or less regular grid, interpolation with multivariate polynomials is possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.