I often see people using products of 1-D polynomials to do interpolation or projection of smooth multivariate functions over grids or cells because it is intuitive and simple to implement. What are the effects of using these product-type polynomials, which contain terms up to degree $kp$ where $k$ is the number of dimensions and $p$ is the maximal degree of the 1-D polynomial, as opposed to using a polynomial basis which merely spans the degree-$p$ polynomial space $P_p$? Obviously $P_p$ is a subspace of the product polynomial space, but it seems to me that the product polynomials just add degrees of freedom while adding bits and pieces of higher-degree polynomial spaces, like a kind of crappy low-pass filter. I'd appreciate your thoughts and good references to relevant reading material.

Edit: To clarify, consider a smooth function $f(x,y)$ projected into the tensor product polynomial space $P_3 \otimes P_3$. If I evaluate the projection $\tilde{f}(x,y)$ along a line parallel to the $x$-axis or $y$-axis the oscillation along that line is cubic, whereas if I evaluate it on a line at 45 degrees from the $x$ axis, i.e. $y(x)=x$, the oscillation is of degree 6 due to the $x^3y^3$ term. What are the ramifications of selectively including this oscillation but excluding other terms of the same combined degree, e.g. $x^4y^2$? Can we obtain a more accurate projection of $f$ in a space $P_k \otimes P_k$ with fewer degrees of freedom than in a polynomial space with elements $x^my^n, m+n \leq k'$, where $k' \approx k$?


2 Answers 2


Let me answer you using a more general concept.

We seek a space of functions (not only polynomials) in which a function may be described. This space of functions $V$ is defined by a basis. The number of elements $d$ within this basis coincides with the dimension of the space of functions $V$.

Let these functions in one dimension be $\phi_i$ and therefore $V_1=\textrm{span}\left\{\phi_i\right\}_{i=1}^{d}$. As an example, in the one-dimensional case, the monomials $1,x,x^2,...$ will form a basis of $V$: $$V_x=\textrm{span}\left\{1,x,x^2,...\right\}$$ On the other hand, the functions $1,\cos{(x)},\cos{(2x)},...$ form another basis: $$V_{\sin{x}}=\textrm{span}\left\{1,\cos{(x)},\cos{(2x)},...\right\}$$ with the particularity that its elements are orthogonal to each other within $[0,2\pi]$ and therefore it has better properties than the polynomial basis.

Now it is clear that we can form any basis once we now we have distict elements, $\textit{i.e.}$ our basis is linearly independent. For example, the basis given by $\textrm{span}\left\{1,\cos{(\pm x)}\right\}$ will have a dimension of $d=2$ despite it having 3 elements.

Imagine now we move to two-dimensional space, in which we must form a two-dimensional basis. We know that if, for example, the basis $V_x$ defines a complete basis in 1D, the tensor product space $V_{xy}=V_x\otimes V_y$ will also form a complete basis in 2D. Formally the two-dimensional space $V_2=\textrm{span}\left\{\phi_i(x)\phi_k(y)\right\}_{i,k=1}^{d}$.

Therefore we only need two complete one-dimensional function spaces to form one complete two-dimensional space. It is natural to form the function spaces: $$V_{xy} = \textrm{span}\left\{1,x,y,xy,x^2,x^2y,...\right\}$$ or $$V_{\cos{x}\cos{y}} = \textrm{span}\left\{1,\cos{(x)},\cos{(y)},\cos{(x)}\cos{(y)},\cos{(x)}^2,\cos{(x)}^2\cos{(y)},...\right\}$$ But no one has forbidden us to build spaces of the kind $$V_{x\cos{y}}= \textrm{span}\left\{1,x,\cos{(y)},x\cos{(y)},x^2,x^2\cos{(y)},...\right\}$$ But the nice properties that $V_{\cos{x}}$ had are not present any more.

As a final remark, you can also form a basis from a linear combination of its elements. If the initial monomial basis is given by: $$V_{xy}=\textrm{span}\left\{1,x,y,xy\right\}$$ you can also form variants of this basis from basic operations among its elements: $$V_{xy}'=\textrm{span}\left\{1+x+y,x(1+y),y(1-x),y\right\}$$ As @njuffa pointed out, there are special linear combinations of these basis that lead to orthogonal polynomials. For example if one forces that $(\phi_i,\phi_k)=\delta_{ik}$ (by means for example Gramm-Smith) for the monomial basis one will obtain the Legendre polynomials, which are orthogonal to each other in the considered interval (usually $[-1,1]$ or $[0,1]$) with respect to the unit weighing function. What is more, if one restrict the values of $x=\cos^{-1}{(y)}\in[-1,1]$ in the basis $V_{\cos{x}}$ one obtains the Tschebycheff polynomials: $$V_{T}=\textrm{span}\left\{1,\cos{(\cos^{-1}{(y)})},\cos{(2\cos^{-1}{(y)})},...\right\}=\textrm{span}\left\{1,y,2y^2-1,...\right\}$$ Which are orthogonal in the interval $[-1,1]$ to each other with respect to the weighing function that appears after a change of variables ($x=\cos^{-1}{(y)}$) in the following integral: $$\int_{-\pi}^{\pi}\cos{(nx)}\cos{(mx)}\,dx=\pi\delta_{nm}$$

  • $\begingroup$ Re "our basis is linearly independent": Would it make sense to specifically mention some commonly-used classes of orthogonal polynomials by name here, e.g. Chebyshev polynomials, or Legendre polynomials? $\endgroup$
    – njuffa
    Jul 23, 2018 at 17:13
  • 4
    $\begingroup$ "We know that if, for example, the basis Vx defines a complete basis in 1D, the tensor product space Vxy=Vx⊗Vy will also form a complete basis in 2D." Could you clarify what is meant by a "complete" basis? It is clear that the standard monomial basis elements of the tensor product space are linearly independent, but it seems the original question is asking, for example, about an element like $x^3y^3$ in the space $P_3 \otimes P_3$ as it is the only monomial of degree 6 in that space out of a possible 28. $\endgroup$
    – smh
    Jul 24, 2018 at 12:27
  • $\begingroup$ @smh That is exactly my question; I will update the OP to reflect this more precisely. $\endgroup$ Jul 24, 2018 at 22:46

the $x^3y^3$ term... but excluding other terms of the same combined degree, e.g. $x^4y^2$

It's because for a constant $y$ the approximant must be a cubic polynomial at most. Cubic was our chosen model along each dimension. Which dictates the corresponding basis for the tensor product polynomial subspace.

Bilinear approximation similarly must produce a line along each coordinate, not a quadric. That's why there can be a $xy$ term but not $x^2y^0$ etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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