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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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