When applying classical statistical methods to modern datasets, we frequently encounter a fundamental geometric bottleneck: the data has far more features than observations. This imbalance—often called the Small Sample Size (SSS) problem—causes traditional algorithms like Linear Discriminant Analysis (LDA) to fail.
To understand why, we must look at the geometry of high-dimensional spaces and see how researchers have reframed a mathematical breakdown into a powerful tool for dimensionality reduction.
The Geometry of Singularity
Imagine you are trying to calculate the variance of a dataset. If you have only two data points in a three-dimensional space, those two points define a single line. The data exhibits variance along that line, but if you look at the two perpendicular dimensions, the variance is exactly zero.
Mathematically, when the number of features $D$ significantly exceeds the number of available training samples $N$, the data points span a subspace of at most $N-1$ dimensions. In the remaining $D - N + 1$ dimensions, the measured within-class variance is zero. As noted by [Fernando De la Torre] et al. in Representational Oriented Component Analysis (ROCA) for Face Recognition with One Sample Image per Training Class, this makes the within-class scatter matrix $S_w$ non-full rank and singular.
This singularity is catastrophic for classical Fisher Linear Discriminant Analysis. The traditional Fisher criterion seeks a projection vector $w$ that maximizes the ratio of between-class scatter ($S_b$) to within-class scatter ($S_w$):
$$J(w) = \frac{w^T S_b w}{w^T S_w w}$$
Finding the optimal projection requires solving the generalized eigenvalue problem, which typically involves inverting the within-class scatter matrix ($S_w^{-1} S_b$). When $S_w$ is singular, computing its inverse is equivalent to dividing by zero. The algorithm cannot run.
The Traditional Fixes: Regularization and Subspace Pre-processing
The earliest and most intuitive solutions to this problem attempted to alter the matrices or the feature space to restore invertibility.
1. Regularization
The simplest way to make a singular matrix invertible is to inject a small amount of artificial variance. By adding a scaled identity matrix to the scatter matrix ($S_w + \gamma I$), we force all eigenvalues to be strictly positive. [Ming-Hsuan Yang] et al. utilize this approach in Extended Isomap for Pattern Classification to stabilize projection vectors. Similarly, [Sangki Kim] et al. introduce an eigen-spectrum regularization scheme in Two-fold regularization for kernel Fisher discriminant analysis in face recognition. While regularization provides numerical stability, choosing the right hyperparameter $\gamma$ is difficult, and over-regularization can distort the true underlying geometry of the data.
2. Subspace Pre-processing (PCA + LDA)
Another common workaround is a two-stage pipeline: first use Principal Component Analysis (PCA) to discard the zero-variance dimensions, reducing the data to an $N-1$ dimensional subspace where $S_w$ is guaranteed to be full-rank, and then perform LDA. This strategy is leveraged by [Alan Wee-Chung Liew] et al. in Gene expression data clustering and visualization based on a binary hierarchical clustering framework and evaluated by [ShaSha Fan] et al. in Comparative Research of PCA+AdaBoost and PCA+LDA for Face Recognition Technology.
However, this approach contains a major theoretical flaw: PCA maximizes total variance, meaning it might inadvertently discard dimensions where the total variance is small but the class-separating information is incredibly high.
Mining the Null Space: Turning Zero Variance into an Asset
Instead of treating the zero-variance dimensions as a mathematical nuisance to be regularized away or discarded, a powerful insight emerged: the null space of $S_w$ is actually a goldmine for classification.
If a direction $w$ lies within the null space of $S_w$, it means $w^T S_w w = 0$. In physical terms, the within-class variance in this direction is exactly zero. If we project our data onto this direction, every single training sample belonging to a given class will collapse into the exact same point. If the between-class variance in this same direction is greater than zero ($w^T S_b w > 0$), the classes will be perfectly separated with zero overlap.
Traditional LDA (Ratio Trace):
Wants to maximize Between-Class Variance / Within-Class Variance
Fails when Within-Class Variance = 0
Null Space LDA:
Finds directions where Within-Class Variance = 0
Ensures Between-Class Variance > 0
Result: Perfect class collapse and separation
This realization led to the development of Null Space LDA (NLDA). [Wangmeng Zuo] et al. study this behavior in Improvement on Null Space LDA for Face Recognition: A Symmetry Consideration. By explicitly mapping data into this discriminative null space, the authors of Maximum Margin Metric Learning over Discriminative Nullspace for Person Re-identification and [Li Zhang] et al. in Learning a Discriminative Null Space for Person Re-identification show that you can eliminate within-class variance entirely. As emphasized by [Dit-Yan Yeung] et al. in Boosting Kernel Discriminant Analysis and Its Application on Tissue Classification of Gene Expression Data, leveraging this null space allows for highly stable discriminant calculations precisely because it embraces the mathematical degeneracy of high-dimensional, low-sample-size regimes.
Bypassing Inversion: The Trace Difference Criterion
Another way to circumvent matrix singularity is to change the mathematical objective function itself. The traditional Fisher criterion is a ratio trace objective. If we rewrite the optimization problem to maximize a trace difference instead, we eliminate the division step entirely:
$$J(w) = \text{Tr}(w^T S_b w - \lambda w^T S_w w)$$
By optimizing the difference between between-class and within-class scatter rather than their ratio, the algorithm no longer requires $S_w$ to be invertible. [Xipeng Qiu] et al. implement this formulation in Stepwise Nearest Neighbor Discriminant Analysis, demonstrating that formulating discriminant criteria without matrix inversion ensures numerical stability and high recognition accuracy even when features vastly outnumber samples.
This mathematical shift is also vital when extending subspace learning to more complex data structures. For instance, [Huan Wang] et al. utilize a trace difference optimization in A Convengent Solution to Tensor Subspace Learning to guarantee convergence when learning from high-dimensional tensors without ever encountering singularity issues.
Local and Margin-Based Alignment
Global scatter matrices ($S_w$ and $S_b$) rely on global averages, implicitly assuming that each class forms a clean, Gaussian cluster. In sparse, high-dimensional settings, this assumption rarely holds. A final class of solutions bypasses global matrix singularity by focusing entirely on local neighborhoods or class boundaries.
Instead of computing global covariance matrices, Feiping Nie 0001 introduces Neighborhood MinMax Projections, an approach that optimizes local neighborhood structures. Because the objective function avoids global matrix inversion, it remains stable regardless of sample size.
Similarly, [Dacheng Tao] et al. propose Discriminative Locality Alignment, which avoids global calculations by optimizing local "patches" near classification boundaries. When data is sparse, modeling the margins between these local structures—or treating classes as continuous convex shapes as shown by [Hakan Cevikalp] et al. in Margin-based discriminant dimensionality reduction for visual recognition—allows models to find robust projection directions without ever risking the mathematical breakdown of matrix singularity.
Key Foundational Work
Gene expression data clustering and visualization based on a binary hierarchical clustering framework (2003) — contributed 2 concept elements to this direction.
Efficient and Robust Feature Extraction by Maximum Margin Criterion (2003) — contributed 1 concept elements to this direction.
Extended Isomap for Pattern Classification (2002) — contributed 1 concept elements to this direction.