If I randomly draw parameters for a polynomial of degree $n$, say $P_n$, there seems to be big chances that this polynomial can be closely approximated by a polynomial of smaller degree $P_{n-k}, k\in\{1,\dots,n\}$.

For instance, this $P_5$ (in blue) is easily approximated by a $P_3$ (in red), as measured by their Mean Squared Error on the interval $[-1, 1]$:

P5 easily approximated by P3

I am interested in random polynomials $P_n$ that are "complete" in the sense that they are not easily approximated by lower-degree polynomials.

For instance, this $P_4$ (in orange) fails to approximate the $P_5$ (in blue) as its measured MSE is high.

P4 fails to approximate P5

How do I randomly draw from this class of polynomials only?

Attempt to formalize the problem, and generalize to multivariate polynomials in $d$ dimensions:

Let $t \in \mathbb{R}^{+*}$ be a minimal dissimilarity threshold. A multivariate polynomial of degree $n$ is considered on the hypercube $P_n: [-1,1]^d \to \mathbb{R}$. Its coefficients $a$ can be refered to by $d$ indexes so that $P_n(x)$ can be expressed as the sum of each monom

$P_n(x) = \displaystyle\sum_{i_1,\dots,i_d \in \{0,\dots,n\}}{a_{i_1,\dots,i_d} \times x{_1}^{i_1} \times \dots \times x{_d}^{i_d}}$

Each coefficient is restricted to the bounded hypercube $a_{i_1,\dots,i_d} \in [-A,A], A \in \mathbb{R}^+$.

The dissimilarity between two polynomials is defined as (or monotonic with) $d(P, Q) \propto \displaystyle\int_{x\in[-1,1]^d}{\left(P(x) - Q(x)\right)^2\,\mathrm{d}x}$.

For each polynomial $P_n$, its "completeness" is measured by the smallest dissimilarity between itself and another $Q_{n-1}$ polynomial:

$c(P_n) = \displaystyle\min_{Q_{n-1}}{d(P_n, Q_{n-1})}$

How do I randomly draw parameters $a$ so as to ensure that

$c(P_n) \geqslant t$


Put it another way, the problem seems to be that the "average $P_n$" is the trivial, null, degenerated polynomial $P_n(x) = 0, \forall x \in [-1,1]^d$. Therefore, if I naively, randomly draw the parameters from $[-A,A]$, I'll get something closer from degenerated polynomials than to "complete" ones. How do I bias the sampling in $[-A,A]$ so as to avoid such almost-degenerated polynomials?

Bonus: if I could also relax the $A$ restriction but ensure that

$\forall x \in [-1,1]^d, P_n(x) \in [-1, 1]$

the satisfaction would be complete.


Use orthogonal polynomials, say Legendre polynomials.

Instead of writing $$f_n=\sum_i^n \alpha_i x^i$$ with random $\alpha_i$, write $$f_n=\sum_i^n \alpha_i P_i(x)$$ with $P_i$ the $i$th Legendre polynomial. Let $g$ be the best $(n-1)$th order approximation to $f_n$: $$g=\sum_{i=0}^{n-1}\left((2i+1)\int_{-1}^1 f_n(x') P_i(x') dx'\right) P_i(x)$$ $$g=\sum_{i=0}^{n-1} \alpha_i P_i(x)$$ so the approximation error is given entirely by $\alpha_n$. Put a lower bound on $|\alpha_n|$, and you will have a non-degenerate polynomial.

  • $\begingroup$ This is really helpful! And thank you for these pointers :) The restriction to $[-1,1]$ codomain can be ensured if I enforce that $\sum{|\alpha_i|}=1$. Is the plain product of Legendre polynomials the correct generalization to multivariate functions? Is the class of functions you describe somehow restricted compared to the class of all polynoms that would fit? For instance, do I have any interest in generalizing to Jacobi polynoms instead? $\endgroup$ – iago-lito 'considering leaving Mar 14 '19 at 10:33
  • 1
    $\begingroup$ Yes, the product is the generalization to multivariate functions. Any set of orthogonal polynomials up to order $n$ spans all polynomials up to order $n$, so there is no restriction. Using different types of orthogonal polynomials, which are orthogonal under different inner products, will also work, but the norm that you want to lower-bound (what you call dissimilarity) is the norm corresponding to the inner product for whatever set of orthogonal polynomials you use. $\endgroup$ – Wouter Mar 14 '19 at 12:37
  • $\begingroup$ .. thus the awesomeness of Legendre polynomials. Thanks a lot :) $\endgroup$ – iago-lito 'considering leaving Mar 14 '19 at 12:38
  • $\begingroup$ As an update on this: I can ensure that $f_n(x) \in [-1,1] \forall x \in [-1,1]^d$ by picking each $\alpha_i$ from a Dirichlet distribution, then I randomly flip their sign. The problem is that, the higher the degree $n$, the closer $f_n$ is from 0 (for the same reasons I suppose). How can I adjust the $\alpha_i$ so that the full range [-1,1] is exploited no matter the degree? I have tried with $tanh(a\times arctanh(f_n))$ transformations ($a\in\mathbb{R}^+$) with not much success. Maybe I should increase $a$ depending on $d$ and $n$.. Does this deserve another post? $\endgroup$ – iago-lito 'considering leaving Mar 15 '19 at 14:03
  • $\begingroup$ You can always try the quick-and-dirty method of finding the maximum and minimum numerically and then rescaling the polynomial such that they are -1 and 1. $\endgroup$ – Wouter Mar 15 '19 at 20:08

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.