4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have some Matlab code that does this. See the following: mathworks.com/matlabcentral/fileexchange/… In particular, look at the files index_set.m and evaluate_ops.m. I represent each polynomial basis function (in this case, an orthogonal basis for a given weight function) by an array of integers. The whole basis is represented by a 2d array of integers. $\endgroup$ – Paul G. Constantine Jul 5 '16 at 17:58
  • $\begingroup$ @PaulG.Constantine Thanks for the link Paul. The 2D array representation your code generates is analogous to what I have thought to implement, assuming there's no more concise pattern that could avoid. The question is more, is there any more concise way to represent the basis than even the 2D array? Either way, the index_set.m code is a good foundation upon which I might build my code, so thanks for the reference! $\endgroup$ – spektr Jul 5 '16 at 20:23
0
$\begingroup$

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.

$\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.