In an underdetermined linear regression setup, why does the residual sum of squares equal 0?

In an underdetermined linear regression where the parameters to estimate outnumber the observations, why is it the case the residual sum of squares, defined as:

$$RSS = \sum_{i=1}^n (y_i-\widehat{y}_i)^2$$

equal zero?

• one way to look at it: if you have at least as many $\beta_p$ as $y_i$, through a change of basis you can make it so that each $x_i$ has zeros in all entries except the $i$th one such that each $y_i$ can have its own regression coefficient. Feb 6 at 3:41
• @JohnMadden What about the situation I describe in my answer? // If you believe the situation I describe is contained in your approach, please do post as an answer. While I do not believe your approach to be 100% correct (because of something annoying like I describe in my answer), I had never thought about it that for for the case where an over-parameterized regression can get perfect (in-sample) predictions.
– Dave
Feb 6 at 3:48
• @Dave I didn't mention the case with duplicate X's because you did :) you're right, in that case there's no way to rewrite the x's as I describe: rather, we can think of those two observations as sharing a regression coefficient. Feb 6 at 3:51
• In geometry one used to talk about points in general position Feb 6 at 4:58
• "In an underdetermined linear regression setup, why does the residual sum of squares equal 0?" The question is based in a false premise. Feb 6 at 16:36

That need not be the case.

It is routine to say that a polynomial of degree greater than the sample size will give a perfect fit to the data. However, this will not be the case if two points have equal feature ($$X$$) values but unequal outcome ($$y$$) values. No function can accommodate that. At least one of those points will have a fitted value $$\hat y_i$$ not equal to its observed $$y_i$$ value, thus a strictly positive squared residual.

EDIT

For example...

X  Y
1  1
2  2
3  3
3  4
4  5
5  6


No matter what a model predicts for x = 3, that model will make a prediction that is incorrect, resulting in a positive sum of squared residuals.

This really has nothing to do with $$p>n$$. If you have two instances with equal feature values and unequal outcomes, the model cannot ever get both right.

x1 x2 x3 x4 x5 x6  y
0  0  0  0  0  0  1.1
0  0  1  1  1  0  0.8
0  0  0  0  1  1  0.3
0  1  0  1  0  0  1.1
0  1  0  1  0  0  0.5


The final two rows have identical feature values yet different outcomes, so a model will get at least one of those wrong, leading to a positive sum of squared residuals.

• Your new example doesn't satisfy $n < p$? Feb 8 at 17:48

With one predictor (and an intercept): two points determines a lines exactly, with less than two points there are infinitely many lines that pass through that point ...

With two predictors (and an intercept): three points determines a plane exactly, with less than three points infinitely many planes will fit perfectly ...

The same principle continues into higher dimension.

• (some exceptions as noted in the answer by @Dave) Feb 6 at 3:39

$$\DeclareMathOperator{\rank}{rank}$$ Suppose all observations of explanatory variables are identical, then it can be shown that \begin{align} RSS = \sum_{i = 1}^n(y_i - \bar{y})^2. \tag{1} \end{align} Hence $$RSS > 0$$ unless $$y_1, \ldots, y_n$$ are all identical.

The reason of this example cannot provide a perfect fit is that the rank of the design matrix $$X \in \mathbb{R}^{n \times p}$$ is $$1$$. Following this key observation, there are actually countless examples of $$RSS > 0$$ as long as $$\rank(X) < n$$ (unless $$y$$ is a multiple of $$e = 1_n \in \mathbb{R}^n$$). This is clear from the projection point of view of least squares, because $$\|P_{\text{col}(X)}y\| < \|y\|$$ under the condition $$\rank(X) < n$$ and the linear algebra fact $$\dim(\text{col}(X)) = \rank(X) < n$$ (there is a theorem in linear algebra states that the rank of a matrix is equal to the dimension of column space).

The conjecture will be true if $$\operatorname{rank}(X) = n$$, i.e., $$X$$ is of full row rank. In this case, the dimension of column space is $$n$$ too, which implies that the columns of $$X$$ spans the whole space $$\mathbb{R}^n$$, hence $$y$$ can be perfectly expressed as a linear combination of columns of $$X$$ (i.e., $$y = P_{\text{col}(X)}y$$), this gives $$RSS = \|y - P_{\text{col}(X)}y\|^2 = 0$$.

Proof of $$(1)$$. Suppose there are $$n$$ observations $$(y_i, x_{i1}, \ldots, x_{ip}) \equiv (y_i, x_1, \ldots, x_p)$$, $$i = 1, \ldots, n$$. Then the least squares minimizes the objective function \begin{align} \sum_{i = 1}^n (y_i - (\beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p))^2. \tag{2} \end{align} Set $$t = \beta_0 + \beta_1 x_1 + \cdots + \beta_px_p$$, then it is easy to see the $$t$$ minimizes $$(2)$$ is $$t^* = \bar{y}$$. This implies that the minimizer $$(\hat{\beta}_0, \ldots, \hat{\beta}_p)$$ must satisfy $$\hat{\beta}_0 + \hat{\beta}_1 x_1 + \cdots + \hat{\beta}_px_p = \bar{y}$$, which is equivalent to $$\hat{y}_i = \bar{y}$$. This leads to $$RSS = \sum_{i = 1}^n (y_i - \bar{y})^2$$.

• I don’t agree about me having defined the sum to involve subtracting $\bar y$. Could you please explain your rationale?
– Dave
Feb 8 at 17:28
• @Dave It can be proved, if the rows of $X$ are identical, the RSS is like this. I will add a proof later (basically all $\hat{y}_i = \bar{y}$). Feb 8 at 17:30
• What is the relationship to what I wrote?
– Dave
Feb 8 at 17:34
• You didn't write. I kind of dug a little deeper to your example. Feb 8 at 17:37