# Find random non-almost-degenerated multivariate polynomials.

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]$$:

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.

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.

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.
• 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? – iago-lito 'considering leaving Mar 14 '19 at 10:33
• 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. – Wouter Mar 14 '19 at 12:37
• 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? – iago-lito 'considering leaving Mar 15 '19 at 14:03