Curse of dimensionality mimics multicollinearity?

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."

• What does "Of course, this works, no problem." mean? – Alexis Sep 25 '14 at 19:02
• It means, fitting a regression for the "small dimensional" case succeeds - the regression coefficient values are found (by Matlab) with no warnings or errors. – cmo Sep 25 '14 at 19:44
• Sometimes, "multivariate regression" is used to mean different estimation structures. Could you perhaps include in your question the mathematical representation of the equations you are estimating (for the $Y, X$ case)? – Alecos Papadopoulos Sep 28 '14 at 21:16

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.)

• I have 10 samples, but of course each sample is 300 points (it is a fully-observed instance of the 300-element dependent variable vector). So for each regression coefficient $\beta_i$, I essentially have 10 observations. This is plenty to estimate the $\beta$ s – cmo Sep 26 '14 at 4:17
• No, this is not. As I explained, you need at least 300 observations. And I explained why. – user31264 Sep 26 '14 at 4:29
• Then please explain why imposing the diagonal constraint on the covariance matrix makes everything work fine... – cmo Sep 26 '14 at 17:16
• what do you mean by "diagonal constraint on the covariance matrix" ? – user31264 Sep 26 '14 at 18:21
• If I declare the covariance matrix to have a diagonal structure (also called "Variance Components" structure - where all off-diagonal elements are 0), then it works – cmo Sep 27 '14 at 2:40