Computing size of N-Dimensional Polynomial Basis and Efficient Representation of Basis

Question

A problem I have had on my mind recently has been a compact way to compute the size of an $N$-Dimensional Polynomial basis of some order $p$, where a linear basis is $p=1$. I have attempted searching for such a formula online but haven't been able to stumble upon one.

I have to believe a formula for this computation exists, though, because this should be a question that statisticians or others who build higher dimensional models ask when figuring out what polynomial basis order to use, based on the size of their data sets, when they want to build a model using polynomials.

What I would like to know is, is there any compact formula for this question that I have not been able to find via my search online?

Another related question is, is there a clever algorithmic way to represent and compute individual $N$-Dimensional polynomial basis terms such that one could target a specific basis function in the set using a single index? Because then one could do a simple loop through all the basis functions to do any necessary computations.

Edit

Note that I am fine with someone mentioning these answers don't really need to be answered explicitly due to some reasoning. It's just that, as far as my experience has shown, these questions seem important to answer to tackle certain modeling problems based on polynomials.

Like how do I estimate what polynomial order to use to model a data set to avoid overfitting (without explicit regularization)? Do people just avoid answering this question by using something like K-fold Cross Validation to find the appropriate polynomial order?

And then, how can I compactly program software that can represent an $N$-D order $p$ polynomial basis in a way that could simply be looped through without needing to store data for each polynomial term?

These are the underlying questions of this post I am trying to get answered.

Answer 1

As for how to create a linear index for the polynomial terms, let's consider an arrangement of terms that works nice for deduction. The terms for each dimension are enumerated as $a,b,c,\dots$. A one dimensional polynomial is straightforward $$ \begin{matrix} 0 & 1 & 2 & 3 & 4 & \dots \\ \hline 1 & a & a^2 & a^3 & a^4 & \dots \end{matrix} $$ The index is the order of the term itself $$ i_1(p_a)=p_a $$ For two dimensions, we arrange the terms as follows, with the dashed lines separating the group of terms with the same degree: $$ \begin{array}{c:cc:ccc:cccc:c} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\dots \\ \hline 1 & b & a & b^2 & ab & a^2 & b^3 & ab^2 & a^2b & a^3 & \dots \end{array} $$ It turns out each degree group contains a one-dimensional indexing subproblem, while the starting index is the arithmetic sum of number of terms from the lower degree groups. $$ i_2(p_a,p_b) = \frac{(p_a+p_b)(p_a+p_b+1)}{2}+i_1(p_a) $$ We go to third dimension. $$ \begin{array}{c:ccc:cccccc:ccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & \dots \\ \hline 1 & c & b & a & c^2 & bc & ac & b^2 & ab & a^2 & c^3 & bc^2 & ac^2 & cb^2 & abc & a^2c & \dots \end{array} $$ I ran out of space to write all the terms for the third degree, but you should be able to notice a pattern here: each degree group contains a two-dimensional indexing subproblem so we can just add the formula from before to the index of the first term in the group. Meanwhile, the index of the first term is the arithmetic sum of the arithmetic sum up to the degree of the group, which is $$ i_3(p_a,p_b,p_c) = \frac{(p_a+p_b+p_c)(p_a+p_b+p_c+1)}{3\cdot2}+i_2(p_a,p_b) $$ Now that we know how to deduce the indexing formula, we can write the general indexing formula for the $n$ dimensonal polynomial $$ i_n(p_1,\dots,p_n) = \sum_{k=1}^n \binom{(\sum_{l=1}^{k}p_l)+k-1}{k} $$ where $p_1,p_2\dots$ is taken to mean $p_a,p_b,\dots$ i.e. the order of the term of each dimension.

Answer 2

Just thought I would post an answer to this question I had since I found solutions. First, the number of coefficients for a polynomial basis complete up to degree $p$ in $n$ dimensions, designated $N_p^n$, is:

\begin{align} N_p^n &= \begin{pmatrix} n + p \\ p \end{pmatrix} \end{align}

Additionally, it's pretty straight forward to compute a basis efficiently using graph algorithms where you compute all sequences of powers that have a sum less than or equal to $p$. Mathematically this is:

Find all possible sequences for $(c_1, c_2, \cdots, c_n)$ such that $\sum_{k=1}^n c_k \leq p$ where $0 \leq c_k \leq p$.

This problem can be viewed as finding valid paths in a dense graph and it is pretty simple to solve in an efficient fashion.