# Why is $n < p$ a problem for OLS regression?

I realize I can't invert the $X'X$ matrix but I can use gradient descent on the quadratic loss function and get a solution. I can then use those estimates to calculate standard errors and residuals. Am I going to encounter any problems doing this?

• The title may be misleading as $n$ is often the notation for the number of observations while $p$ is the notation for the number of variables in a dataset. With these, $n > p$ is never a problem (on the contrary).
– Riff
Commented May 31, 2017 at 11:27

I can use gradient descent on the quadratic loss function and get a solution…

Sure, but you have fewer constraints than unknowns, so your loss function is something like a parabola in three-space: $L =(w_1+w_2-1)^2$. There is a whole space of solutions. In this example, the solutions lie on the line: $w_1+w_2=1$.

If you're really indifferent to which solution you take, then there is no problem. If you do care, regularization (additional loss terms) can change the set of solutions. E.g., adding the L2 norm of the weights would identify the solution $w_1=w_2=\frac13$, which is not quite on the parabola, but it's close and adding the L2 norm guarantees a unique solution.

Here is a little specific example to illustrate the issue:

Suppose you want to fit a regression of $y_i$ on $x_i$, $x_i^2$ and a constant, i.e. $$y_i = a x_i + b x_i^2 + c + u_i$$ or, in matrix notation, \begin{align*} \mathbf{y} = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix}, \quad \mathbf{X} = \begin{pmatrix} 1 & x_1 & x_1^2 \\ \vdots & \vdots & \vdots \\ 1 & x_n & x_n^2 \end{pmatrix}, \quad \boldsymbol{\beta} = \begin{pmatrix} c \\ a \\ b \end{pmatrix}, \quad \mathbf{u} = \begin{pmatrix} u_1 \\ \vdots \\ u_n \end{pmatrix} \end{align*}

Suppose you observe $\mathbf{y}^T=(0,1)$ and $\mathbf{x}^T=(0,1)$, i.e., $n=2<p=3$.

Then, the OLS estimator is

\begin{align*} \widehat{\boldsymbol{\beta}} =& \, (\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y} \\ =& \, \left[ \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix}^T \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix} \right]^{-1} \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \end{pmatrix}^T \begin{pmatrix} 0 \\ 1 \end{pmatrix} \\ =& \, \left[\underbrace{\begin{pmatrix} 2 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}}_{\text{not invertible, as $\mathrm{rk}()=2\neq 3$}} \right]^{-1} \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \end{align*}

There are infinitely many solutions to the problem: setting up a system of equations and inserting the observations gives

\begin{align*} 0 =& \, a \cdot 0 + b \cdot 0^2 + c \ \ \Rightarrow c=0 \\ 1 =& \, a \cdot 1 + b \cdot 1^2 + c \ \ \Rightarrow 1 = a + b \end{align*} Hence, all $a=1-b$, $b \in \mathbb{R}$ satisfy the regression equation.

If $X'X$ is not invertable, the estimation $\hat \beta$ does not exists.

Check this post, @mpiktas's answer for details ("Existence" section)

What is a complete list of the usual assumptions for linear regression?

• Actually, I wouldn't say that $\hat{ \beta }$ does not exist, but rather that $\hat{ \beta}$ is not unique. Commented May 31, 2017 at 3:50