Curse of dimensionality mimics multicollinearity?

Question

Why does the curse of dimensionality mimic multicollinearity, in the following sense..

1. Consider the random vector $Y = [y_{1}, \dots, y_{4}]$ where each element is ~ Uniform (0,1).
2. Take 10 samples of $Y$. Call this your dependent variable observations.
3. Let the independent variable $X$ be 1 for the first 5 samples of $Y$, and 0 for the last 5 samples.
4. Fit a multivariate regression for $Y | X$ (allow there to be a constant term in the regression).

Of course, the above fit succeeds. No problem.
Now let's increase the dimensionality.

1. Now let $W = [w_{1}, \dots, w_{300}]$
2. Take 10 samples of $W$, as above.
3. Use the same $X$ as above.
4. Fit a multivariate regression for $Y | X$.

The fit fails due to multicollinearity (says Matlab).
I can try scaling the observations by large positive constants - still fails.

Why does increasing the dimension mimic multicollinearity?

If I try a MANOVA test, I encounter same problem (of course, because ANOVA is regression).

Note: if I impose the constraint that the covariance matrix is diagonal, then it works. Why?

---

Matlab code for the above, for anybody interested:

Y = rand(300,10);
X = [ repmat([1 0],  5,1)  ;  repmat([1 1],  5,1) ];
mvregress(X,Y')
% generates error:  "Covariance is not positive-definite."

Answer 1

Without getting into the algebra,

• in the former case you are trying to find 5 coefficients which minimize the sq. error on 10 points, which succeeds.
• in the latter case you are trying to find 301 coefficients which minimize the sq. error on 10 points. Not only you can fit the function perfectly, but you can do it in infinite number of ways, because for a perfect fit you need to solve 10 equations with 301 unknowns. Obviously, you have infinite number of solutions. Therefore, without any additional information, linear regression is unable to determine the coefficients.

This happens not only with linear regression. Many some statistical models fail (either formally, or produce bad fitting) when there are more dimensions than observations.

But this is not what is usually called the curse of dimensionality. The curse of dimensionality means that in some circumstances, in order to obtain a decent prediction, you need the number of observations which grows exponentionally with dimensionality (i.e. for knn models). (There are also other meanings for curse of dimensionality, which have nothing to do with number of observation vs dimensionality.)