Why classical methods fail when p > n
Section of High-dimensional analysis, part of Statistical learning
Why classical methods fail when p > n
| Type | Section |
| Taught in | High-dimensional analysis |
| Part | Statistical learning |
Dempster (1958) pointed out that neither Hotelling’s T^2 test for two groups nor Fisher’s linear discriminant analysis can be used when p>n_1+n_2-2. In both cases the difficulty is fitting a multivariate normal distribution in this number of dimensions. The procedures need a covariance inverse, and the sample covariance does not have one.
Prediction from a regularised fit can still have small error. Attribution of that error to individual coefficients is not identified, because many coefficient vectors produce the same fitted values once p exceeds the rank of the design.
The rank of the sample covariance
Main article: Rank of the sample covariance
For a single data set with p>n-1 the sample covariance matrix is singular, hence not invertible. The n\times p data matrix X_{\mathrm{all}} has rank at most \min(n,p). With A=\sum_{i=1}^{n}(x_i-\bar x)(x_i-\bar x)^\top and S=\frac{1}{n-1}A, the matrices A and S have the same rank. Each observation can contribute one dimension, and centring spends one of them: the rows of the centred matrix sum to zero.
Theorem 1 (Rank bound) \operatorname{rank}(S)\le\min(n-1,p). Hence S is invertible only if p\le n-1 and the centred data have rank p.
Let X_c be the centred data matrix with rows (x_i-\bar x)^\top, so that A=X_c^\top X_c and \operatorname{rank}(A)=\operatorname{rank}(X_c). The rows of X_c sum to zero, \sum_i(x_i-\bar x)=0, so they are linearly dependent and span a subspace of dimension at most n-1. Also \operatorname{rank}(X_c)\le p.
The key dependence is 1^\top X_c=0^\top: each column of the centred matrix lies in the (n-1)-dimensional subspace of \mathbb{R}^n perpendicular to 1. Equivalently, its rows sum to zero. Centring each of g nonempty groups gives the pooled within-group rank bound n-g. For n=100 and g=2, the full sample can have at most 99 positive principal variances, while a pooled covariance has rank at most 98. Neither upper bound guarantees full rank. In cross-validation, calculate these bounds using the training fold.
Example 1 (A singular covariance) Question. Three observations are recorded on five variables. What fails if this sample covariance is dropped into a Mahalanobis distance, Hotelling’s T^2, or an unregularised Gaussian discriminant rule?
Solution. S has rank at most two. At least three eigenvalues are zero. Those procedures need S^{-1}, which does not exist. The Gaussian likelihood itself is still defined for a candidate positive-definite population covariance. The problem is that its unrestricted covariance maximum-likelihood estimate is not a positive-definite matrix. For quadratic discrimination, n_g-1\ge p is necessary in each class. For linear discrimination with G nonempty classes, n-G\ge p is necessary for an invertible pooled estimate. Collinearity can make either estimate singular even when those inequalities hold.
Regression
Main article: Regression when p > n
The same rank obstruction appears in the normal equations. The least-squares coefficient for a linear model with an intercept is
\hat\beta=(X^\top X)^{-1}X^\top y,
where y is the vector of continuous responses and X is the n\times(p+1) matrix of explanatory variables augmented by a column of ones. The product is X^\top y. Dropping the transpose leaves Xy, which is undefined: X is n\times(p+1) and y is n\times 1. The same transpose belongs on the ridge formula below. The closed form is the one derived for linear regression when the columns are linearly independent.
The inverse formula requires full column rank, not merely a favourable count of rows and columns. When rank fails, least squares still projects y onto the column space of X, giving a unique fitted vector. The coefficient representation is non-unique: adding any v with Xv=0 leaves the fitted values unchanged. Exact interpolation occurs when y lies in that column space. Full row rank is sufficient. Having p\ge n alone is not sufficient.
Where the columns come from
Main article: Where high-dimensional columns come from
A large sample relative to the number of fitted coefficients makes classical estimation easier, but collecting another subject can cost much more than measuring another feature on an existing sample. High-dimensional methods address this imbalance by adding structure. They cannot manufacture information about directions that the observed design never distinguishes.
Microarray studies are one setting of this kind. One tissue sample produces measurements of many transcript-related features, while the number of sampled tissues can remain small. The Alon study below analyses 2000 selected gene-expression features from 62 samples (Alon et al., 1999). These measurements are not direct measurements of protein production, and a biological gene is not interchangeable with one independent predictor. Correlation, measurement processing, and tissue composition all affect the statistical question.
In that setting the scientific question is often which coordinates are associated with the response, not the size of the prediction error. Association is not causation.
What the question is
Main article: Questions to ask of high-dimensional data
The choice of method depends on the question.
- Which of the predictor variables are associated with the response? Either one variable at a time, or the explanatory variables all at once.
- Can the explanatory variables be transformed into a space of smaller dimension without losing anything important about the association with the response?
- Can they be transformed into a smaller space when there is no response, either to capture structure or to cluster?
- How can the highest-quality predictions of the response be made from the explanatory variables?
Selecting a subset of coordinates is one restricted form of dimension reduction. Finding scientific associations and finding a predictive representation need not give the same answer. Unsupervised principal components come first, then marginal testing, then joint penalised regression. Keep the target question visible when comparing their outputs.
Used in
See also
Rank bound · Family-wise control implies false-discovery control · Benjamini–Hochberg · Benjamini–Hochberg controls the false discovery rate · Rank of the sample covariance · Regression when p > n · Where high-dimensional columns come from · Questions to ask of high-dimensional data