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