# Polynomial approximation spaces

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$?

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}$$

• 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? – njuffa Jul 23 '18 at 17:13
• "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. – smh Jul 24 '18 at 12:27
• @smh That is exactly my question; I will update the OP to reflect this more precisely. – sssssssssssss Jul 24 '18 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.