Why is linear regression considered an ill-posed problem?

Question

Could someone please explain to me why exactly linear regression is considered ill-posed?

Answer 1

According to Wikipedia, a problem is well-posed if:

1. a solution exists,
2. the solution is unique,
3. the solution's behaviour changes continuously with the initial conditions.

Now suppose that you have a dataset $(X, y)$ consisting of samples $(x_i, y_i)_{i = 1}^m$, with $x_i \in \mathbb{R}^n$, $y_i \in \mathbb{R}$. I suppose that you think of linear regression as of the following problem for weights $w$ of the regression: $X w = y$ (or something similar depending on how do you stack samples in the matrix).

This problem is ill-posed because of the following reasons:

• the solution is not unique if you have too few samples, namely $m < n$ (for example, there are infinitely many straight lines going through a given point in $\mathbb{R}^2$);
• the solution may not exist if you have too many samples, namely $m > n$ (for example, there are not straight lines going through three given points in $\mathbb{R}^2$);
• finally, there is multicollinearity issue which contradicts the last necessary condition of weight estimates being continuous in observations.

However, the problem can be adapted to fix these properties. Modifying the problem to $\|Xw - y\|_2^2 \to \min$ allows obtaining a pseudo-solution when there is no exact solution (the problem is still ill-posed because there may be many solutions).

You can also add Tikhonov regularization (a.k.a. ridge in the setting of regression) to get $\|Xw-y\|_2^2 + \lambda \|w\|_2^2 \to \min$ which allows selecting one solution if there are many solutions of the original problem.