Fdtxjr

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, kin1,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 mathbbR^+*$ be a minimal dissimilarity threshold.
A multivariate polynomial of degree $n$ is considered on the hypercube
$P_n: [-1,1]^d to mathbbR$.
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) = displaystylesum_i_1,dots,i_d in 0,dots,na_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 mathbbR^+$.

The dissimilarity between two polynomials is defined as (or monotonic with)
$d(P, Q) propto displaystyleint_xin[-1,1]^dleft(P(x) - Q(x)right)^2,mathrmdx$.

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

$c(P_n) = displaystylemin_Q_n-1d(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-1left((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.