I am trying to approximate a target function $f$ in 1D with a polynomial linear regression (using software like python polyfit) in a specific interval $[lb,ub]$. I am specially interested in the underdetermined case (i.e. more unknowns than data points). However whenever I choose to approximate my target function with a high degree polynomial, I get that the vandermonde feature matrix $\Phi(x)$ is poorly condition or that it has a really low rank, usually smaller than the number of data points.

For me this seems rather counter intuitive because the that would mean that there are rows in my data set that are "repeated" in some sense. However, I usually choose functions that are not in the space of polynomials that are considered by the regression model. For example I've chosen:

  1. really high degree (random polynomials)
  2. cosine, sine curves
  3. gabor like function $exp(-x^2)cos(2 \pi f x)$
  4. or a linear combination of the above

If I choose say a target polynomial of degree $D_{target}$ then to exactly learn/approximate it I would have expected one needs at least $N=D_{target}+1$ points. With this intuition I thought that given a function that can be expressed as an infinite power series most sampling methods of point from the target function should lead to a $\Phi(x)$ that is full row rank (since we would need infinite polynomials to really figure out the coefficients). However, empirically I have noticed this is not the case. Most target functions lead to very ranks plots. If I plot the number of rows of $\Phi$ on the x-axis and the rank of $\Phi$ on the y-axis, I usually get that the rank increase and then stops increasing. The funny thing is that sometimes it stops before the # of data set points. For me this is really odd and I can't explain this. My guess is that:

  1. Am might be just choosing really bad target functions (maybe not complex enough? or maybe in the case of a cosine there might be an issue its an even function? Though I've tried odd functions...)
  2. or maybe my sampling method is not good (usually just equally spaced points)

Anyway, those are my thoughts. Does anyone have any suggestion on how to choose a target function such that the underdetermined system is always full rank?

Some example plots of the # parameters vs rank:

enter image description here

enter image description here

enter image description here

  • $\begingroup$ When you say underdetermined do you mean you are trying to find a polynomial with degree higher than the number of data points you have? $\endgroup$ – David Reed Nov 19 '17 at 3:36
  • $\begingroup$ @DavidReed when I saw underdetermined, I mean that there are less rows than columns. So yes, I mean more degrees/monomials than data. $\endgroup$ – Pinocchio Nov 20 '17 at 23:32
  • 1
    $\begingroup$ The name of the text is "An introduction to numerical linear algebra" by Cullen. You can get it on Amazon for \$30 or \$15 used $\endgroup$ – David Reed Nov 21 '17 at 0:51

If I understand you correctly, given data points $(x_0,y_0),(x_1,y_1),\dots (x_m,y_m)$, you are trying to solve the matrix equation $(m \leq n)$:

$$\begin{bmatrix} x_0^n & x_1^{n-1} & \cdots & x_0 & 1 \\ x_1^n & x_1^{n-1} & \cdots & x_1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ x_m^n & x_m^{n-1} & \cdots & x_m & 1 \end{bmatrix} \begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_1 \\ a_0\end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{m-1} \\ y_m \end{bmatrix}$$

Then your matrix will theoretically always have full row rank. However, when dealing with machines that are limited to finite precision,taking something to the 50th power can cause problems, especially if your $x_i$ are not whole numbers. It may also be a result of the algorithm you are using to determine the rank of the matrix. I took numerical linear algebra in college and as a general rule computers HATE matrices that are not orthonormal. I can't really speculate as to exactly what's going on without knowing what data you are using.

Edit- In response to your comment. When the columns of a matrix are orthornormal, the corresponding transformation preserves "lengths" and "angles". That is $\mathbf{Ax} \cdot \mathbf{Ay} = \mathbf{x} \cdot \mathbf{y}$ and $\Vert\mathbf{Ax}\Vert = \Vert \mathbf{x} \Vert$ As a result, the condition number of an orthogonal matrix turns out to be $1$. You used the term "Well-conditioned" above. This is what it refers to. It turns out you can bound certain errors that occur in terms of the matrix's condition number, I don't remember how, but you can have very drastic results occur even with 2 x 2 matrices because of the way the computer does arithmetic. Virtually every algorithm, even Gaussian elimination, has to be modified for use in a computer. Some people dedicate their entire adult life to finding ways to make computers and matrices get along I don't know much about the environment you are using. You might consider trying matlab as its really built for matrix manipulations. I will also look-up my textbook info and send it to you. Its pretty small, and will teach you how computers deal with floating point numbers and the errors that it can cause. Its a good balance of concrete examples of problems that arise, practical solutions and algorithms for them, and rigorous theorem proving.

  • $\begingroup$ the point of the question is that we are free to choose $f(x)$ such that the linear system is well behaved (or at least thats the intuition). Right now I am using the pseudo-inverse. Are we really always guaranteed to have full row rank? What if the function is $f(x) = k$ for some constant $k$...I think what you made me realize is that the main issue is that the rank of the data i.e. $\Phi(X)$ is independent of the target function since the only thing that has a rank is $\Phi(X)$ the feature matrix...which is confusing me...why is $\Phi(X)$ not always full row rank? $\endgroup$ – Pinocchio Nov 20 '17 at 23:36
  • $\begingroup$ $\Phi(X)$ is just the standard Vandermonde matrix (as you write I believe). Is what you are saying that the computer is unable to find the rank of $\Phi(X)$ because of machine precision? Maybe the way I sample points on the given interval/hypercube matters...? I am sampling equidistant point usually over some interval. I think I've tried multiple intervals but mostly $[0,1]$. What do you think? $\endgroup$ – Pinocchio Nov 20 '17 at 23:38
  • $\begingroup$ why do computers really prefer orthogonal stuff? can you provide an intuition (or link) if possible? :) $\endgroup$ – Pinocchio Nov 20 '17 at 23:43
  • $\begingroup$ David, I did not perceive any irritation in your responses :). I'm grateful for ur engagement with me if anything. Anyway, back to maths. I guess it has to be a numerical issue since at around 30 it seems where the issue is arises...and machine precision seems to be $10^{-16}$ for 64 bit computers...I'm surprised its not at 16 though for values sampled btw [0,1]. I think what I am interested now is in computing $\Phi(X)$ such that its orthogonal only by sampling points. I wonder how easy that is to do... $\endgroup$ – Pinocchio Nov 21 '17 at 1:42
  • $\begingroup$ yea it mostly mock data sampled equidistant inside of an interval, usually [0,1]. The target functions are the ones described in my original question (sine, cos, combinations of those, gabour, polynomials, etc) $\endgroup$ – Pinocchio Nov 21 '17 at 16:58

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.