# Why is it bad if number of dimensions / factors > sample size?

I've been told (read) this many times, but I never understood why it's bad for the number of dimensions in your data, or the number of explanatory variables in your model to be higher than your number of samples. Why is this the case?

First of all, this is not a "hard" limit in the way that a model with sample size $n =$ number of variates $p$ is bad and adding one sample or case (model with $n = p + 1$) would turn this into a good model. The rule rather focuses on the idea that the model quality depends on sample size compared to the number of variates, as opposed e.g. to the quality of validation results which often depends on the absolute number of test cases.

You can think of your data as spanning a $p$-dimensional space: each variate opens a new direction. The model describes the points (samples) in this space; often it is some kind of (hyper)surface.
In that description, you can think of model quality as the answer to how certain you can be about the hypersurface: that depends on the sample density. The tighter are the data points which you know, the more certain can you be about the surface.

In a very general setting, this leads to the conclusion that with growing number of variates you may need exponential growth in the number of samples in order to have the same certainty in fitting your model. However, if you impose restrictions on your model (i.e. you reduce the degrees of freedom) such as allowing planes only (linear model), you can reduce the needed growth in sample size (e.g. to linear for linear models).

However, for sample sizes $n \leq p$ even a linear model is not even unique any more: there are infinitely many planes that perfectly fit the given points (including their noise) in $p$ dimensions.
Adding more samples will first make the model mathematically unique and then overdetermined (so that degrees of freedom are left after fitting the model that can be used to estimate and reduce uncertainty). Of course the step from underdetermined to determined (at $n = p + 1$) is a huge improvement. But the improvement to $n = p + 2$ which for the first time gives a (still very rough) idea about the uncertainty is almost as big IMHO. Hence, the model will gradually improve by each new case.

The Elements of Statistical Learning give a nice discussion in chapter 2.

• I'll start reading the chapter you mentioned, but this is illuminating. Just thinking about the most simple case helps, e.g. fitting a linear model with two independent variables beginning with 1 sample point, and then 2, then 3... etc. However I don't follow what you mean by the improvement to $n = p + 2$ is almost as big as the step from $n <= p$ to $n = p + 1$. Also what do you mean by "overdetermined?" Jun 27, 2013 at 18:26
• Well, with $n = p$, the surface is not yet fixed. So it is obvious that the sample size is too small. With $n = p + 1$, the plane is fixed (unique, determined), and it goes through all points. But there is still no indication about the uncertainty related to noise (uncertainty) of the data points. IMHO this is almost as bad as not being able to fix the plane. Each new data point now helps to estimate this uncertainty (and refine the estimated plane). Overdetermined: there are more data points than are needed to mathematically define the plane (the ones used for estimating the uncertainty) Jun 27, 2013 at 21:50

To comment on @cbeleites' answer, there are exceptions to the rule (sort of). Specifically, often your predictors are correlated, so they can be replaced by only one variable; or otherwise many of the predictors can be removed. Thus, even though you cannot create, say, a straightforward linear regression model with $n \leq p$, you can work with data sets that have many more variables than samples. This is a case for dimension reduction strategies, variable selection and other related tools.

• Yes, that is true. Dimension reduction often helps very much (though it is no magic bullet). Jun 27, 2013 at 21:42
• Yeah, I totally agree. I'm a biologist. My latest data set has 16 samples and over 400,000 variables. Jun 27, 2013 at 21:45