What is the significance of a linear dependency in a polynomial regression?

Question

I'm trying to find the best polynomial regression for a dataset where the polynomial's power is between 2 and 10. So the regression can have an x¹⁰ term at most in it. The dataset itself is simply a set of x and y pairs as follows:

1,15.3
2,66.0
3,272.5
4,814.8

As I understand, the normal way to do a polynomial regression is to simply apply the power transformation to the x vector (i.e. put every element in the vector to the power of 6), add this vector to the dataset, and then treat this transformed vector as another independent variable.

However if I try this approach with high enough powers (usually 6 and above), my regression library (statsample for Ruby) tells me "Regressors are linearly dependent", and throws an error. I know that technically the x vectors are dependent on each other since they were derived from each other, but it's certainly not a linear dependency (where one is the same as the other multiplied by a scalar). What's going on? And what does this mean?

As an example, here's an example of my code in Ruby (I'm told that this library is a lot like R however, for all you R users):

# Read the dataset (like an R data frame??) containing just x and y (see the example above)
ds = CSV.read(file_name)

# For each possible polynomial power between 2 and 10, add a new vector which consists
# of the x vector to that power, and then run a regression
(2..10).each do |i|

  # Add a vector called x2, x3, x4 etc. and apply the power transformation
  ds.add_vector("x#{i}", ds["x"].map{ |x| x**i }.to_scale)

  #Run the regression
  reg = lr(ds,'y')
end

Answer 1

Recall from linear algebra that linearly dependent vectors are a set of vectors which can be expressed as a linear combination of each other. When performing regression, this creates problems because the matrix $X^TX$ is singular, so there is not a uniquely defined solution to estimating your regression coefficients. (The matrix $X^TX$ is important because of its role in estimating OLS regression coefficients $\hat{\beta}$: $\hat{\beta}=(X^TX)^{-1}X^Ty$.)

Linear dependence is a technical phenomenon distinct from the ordinary usage of "dependence" as you express it.

So with an understanding of linear dependence in hand, we can begin to examine likely sources of this problem.

1. More features than rows It's unclear how much data you have, but it's possible that by adding polynomial terms, you're inadvertently creating a dimensionality problem: an ordinary regression with more columns than observations will fail! This is because the system of equations that you've defined has infinitely many solutions, i.e. there is not a pivot point in every column. This amounts to the same problem as having a singular $X^TX$.

2. Duplicate data Even if you have more rows than features, it's important that each of those rows provides unique information. Duplicate rows are unhelpful in this context. By definition, the polynomial regression matrix $X$ (consisting of $[\mathbf{1} , x, x^2, ... x^m]$ as columns) is a Vandermonde matrix, so it will have a unique OLS solution provided that there are $m+1$ unique entries in your original $x$ vector. So despite having 100 observations, perhaps you have a smaller number of unique $x$ entries?

3. Ill-conditioned matrix Even if neither (1) nor (2) is true, it's possible that the matrix is numerically singular, i.e. singular due to machine precision reasons. There are a number methods of dealing with this, depending on what kinds of compromises you're willing to make. These include orthogonal polynomials, regularization, and splines among others.

A general strategy to address an ill-conditioned matrix $X$ is called ridge regression, which works by finding an optimal amount of regularization to apply to your problem. Ridge regression is discussed all over this website. One place to start would be with this excellent answer.

AndyW points out that fitting very high-order polynomials is often ill-advised since it increases the risk of overfitting. In predictive settings, it's often advised that one use cross validation to assess the fitness of a given model. Depending on your application, you might care about different out-of-sample tests, but a typical metric for this type of problem is mean squared error.