How can one design a polynomial function that really does require higher order terms to approximate it well?

My goal is to design an experiment such that only a high order polynomial function can approximate the target polynomial function.

I've been trying to approximate a polynomial function in 1D $f_{target}(x) = \sum^{ D_{target} }_{d=1} c_d x^d$ with linear regression:

$$\Phi(x) w = y$$

where $\Phi(x)$ is the Vandermonde matrix (of polynomial features) of whatever degree greater or less than or equal to the degree of the target polynomial $f_{target}(x)$. Note the number rows for $\Phi(x)$ is $N$ and each row corresponds to one data point. The issue that I am having is that whenever I try to approximate $f_{target}(x)$, I get that the low order terms approximate it well pretty too quickly. i.e. there are usually quite a few degrees that have zero least squares error before it reaches $D_{target}+1 = N$. I would have expected that the only point the regression problem should really start to be zero $D_{model}+1 > D_{target}+1 = N$. I want the error to be high until for $D_{model} < N = D_{target}+1$.

For example in the following you can see how the error drops too quickly:

One of my intuitions is that the functions I am using might be too simple. So to combat I've tried the following:

• Use really high degree polynomial target functions
• since the interval of my experiments were mostly between [-1,1] I decided to make sure the higher order terms had larger coefficients. I used increasing sequence $[c_i = i]^{Deg}_{i=1}$ to crazier things like: $[c_i = i^5]^{Deg}_{i=2}$. I did this because raising a number $|x|<1$ many times yields essentially zero so its as if the high order terms don't contribute anything...
• I also simply just changed the interval to $[lb,ub]$ s.t. $lb=ub > 1$. This didn't really seemed to help much. Usually I got that at the edges of my target function, the function had extremely large values which seemed to hint that now I had the opposite issue, the high order terms were too important? But if that were true then why can I still fit it well with a low order polynomial...?
• I have also tried other things like tracking the rank of $\Phi(x)$. I notice that I usually get $\Phi(x)$ to be really low rank for some reason. Which seems really counter intuitive to me because if my target function has degree $D_{target}$ I thought we would need at least those many data points (plus 1) to approximate it well. Anyway, that weird behavior took me to ask this question to mathematicians: What are good mathematical heuristics for choosing a good target function that always produce a stable linear regression solution?
• I also plotted the target function and it usually looked like a straight line on the interval given (except at the edges where it had really large values). So this made me think that maybe the right thing to do is to give the target function more non-trivial shape. So what I did was the polynomial target function itself fit some other curve. I tried the target polynomial to fit: cosine & sine with many frequencies, gabor function $e^{-x^2}cos(2 \pi f x)$, product of sinusoidals $sin(2\pi f_s x)cos(2\pi f_c x)$, sum of sinusoidals $sin(2\pi f_s x) + cos(2\pi f_c x)$. I thought those would be specially good functions since under the hood they are infinite summations of polynomials.
• similar to the past point since the function seemed like a straight line, then what I decided to do what force it to have more shape by going through the line $y=0$. i.e. have it have non trivial roots. So for that I defined $p(x) = \prod^{Deg}_{i=1} (x - r_i)$ where $r_i$ where roots that I choose that fitted in the given interval in question. Random and equally spaced.

honestly right now I am not sure how to design the polynomials so that low order polynomials don't reach zero (or close to it) so quickly. Thus, if anyone has suggestions, feel free to post!

As a side note python's polyfit is what I am using and it nearly always complains about the condition number. I don't know why or how to sample points such that that is not an issue, suggestions there are appreciate too. Also, maybe the issue I am seeing are related to numerical stuff? Since there is always a complaint about the condition number? Not sure but I did try different intervals beyond just $[-1,1]$ and they didn't really seem to help.

• Python complains because the polynomial basis (Vandermonde matrix) has poor numerical conditioning -- even though your matrices are full-rank. The intuition here is that the even roots all have essentially the same "U-shape", likewise the odd roots have a "sigmoidal" shape. So the basis functions are very similar. Splines, like $B$-splines, have improved numerical properties and are also polynomials. Also, this link is interesting but perhaps not directly relevant. en.wikipedia.org/wiki/Runge%27s_phenomenon – Sycorax Oct 23 '17 at 18:05
• It's hard to tell what you're actually trying to achieve, since the problem involves various functions as well as how you sample them. However, if you want to study how increasing the order of a polynomial can approximate a function, start with $\sin$ (for instance) and sample it uniformly through several periods. Study how and to what extent each successive approximation changes: that will give you a way to identify a sequence of polynomial functions and samples thereof where each one is not well approximated by the previous. Taylor's Theorem (with remainder) can help you analyze this. – whuber Oct 23 '17 at 19:08
• (cont'd) A more formal approach is to begin with an $L^2$ function that determines how you will compare two approximations and then develop the polynomial basis for the corresponding Hilbert space through the Gram-Schmidt procedure. Examples are Hermite polynomials, Legendre polynomials, etc. – whuber Oct 23 '17 at 19:10
• @whuber thanx for the suggestions. I'll need to think about them a bit more to really understand them...to address what exactly I am asking. I really tried to make it as direct and explicit as possible but I guess I failed. If you look at the plot in my question, I want the training error to go to zero at the green line and not before. I've obviously tried decreasing the # of data points but as far as I've tried it did not seem help. I guess I just don't understand why the error drops (close to) zero so quickly, way before the number of data set points match the number of parameters. – Pinocchio Oct 23 '17 at 21:12
• @Sycorax is the complain about the condition number due to my basis? Or what is the source of the problem for that? Or is it the degree of the polynomial? Or is it a combination of high degree plus $|x| < 1$? – Pinocchio Jan 10 '18 at 22:07