# Multidimensional interpolation

In one dimension it is well known that any polynomial of degree $$N$$ can be identified by its values of any given sequence $$a_n$$ of $$N$$ distinct real numbers. That is because the Vandermonde Matrix $$\begin{bmatrix} 1\ a_1\ a_1^2\ ...a_2^N\\ 1\ a_2\ a_2^2\ ...a_2^N\\ \dots \\ 1\ a_N\ a_N^2\ ...a_N^N \end{bmatrix}$$ is always non singular and the coefficients of the polynomial can be found as solution of the linear system associated. Things cange in multiple dimension, where there are infinite polynomial $$p(x,y)$$ functions of degree $$2$$ such that $$p(n,n)=0\ \forall n\in \mathbb N$$ although we fix their value on an infinite number of points. My question is:

Given $$N,M\in \mathbb N$$, does there exist a finite set of points $$\{x_n\}_n$$ in $$\mathbb R^M$$ such that, a polynomial of degree $$N$$ in $$M$$ variables can be identified by its values on $$\{x_n\}_n$$?

A polynomial in $$M$$ variables can be written like this:

$$P(x_1,\cdots,x_M)=\sum_{i}c_{i}\cdot \prod_j {x_j}^{e_{i,j}}$$

For some vectorization so that exponents $$e_{i,j} \in \mathbb Z$$ and coefficients $$c_i \in \mathbb R$$.

Note that for any fixed point $$(x_1,\cdots,x_M)\in \mathbb R^M$$, and every ordered pair $$(i,j)$$ the product

$$\prod_j {x_j}^{e_{i,j}}$$

Will be a constant.

This means you will have a set of equations which are linear in the coefficients $$c_i$$.

One equation per prescribed value. This will give a number of degrees of freedom equal to $$D^M$$ if maximum degree is $$D$$. It should therefore surely be able to fit a polynomial perfectly on $$D^M$$ points.

But, if we are lucky and our data is well compressed by polynomials, we will be able to get away with a simpler polynomial. We know for example that any $$M$$-dimensional-sphere is expressible with $$D=2$$. So with thousands of points on any such sphere, we will never need more than degree $$2$$.

Here is also where regularization and norm minimization comes into play. Imagine we slightly perturb the points on sphere by adding some small noise. Very fast we will need higher degree polynomial to perfectly capture these points. But with regularization, we can encourage a simpler solution, at a small error cost. We can also view this regularization as noise-filtering. We have a model that fits spheres and we want to fit a sphere which makes the most sense.