Abstract
Standard Linear Discriminant Analysis (LDA) often fails when classes have different shapes or when some classes are much closer together than others. This paper introduces Pairwise-Covariance LDA (pcLDA), which replaces global averages with pairwise class statistics and uses a weighting scheme to prioritize separating the most difficult, closely-situated pairs of classes.
Introduction
Linear Discriminant Analysis (LDA) is a fundamental technique for dimensionality reduction, aiming to find a projection that minimizes within-class variance while maximizing between-class distance. However, standard LDA suffers from two significant limitations:
- The Homoscedasticity Assumption: It assumes every class shares the same covariance. In practice, one class might be a tight cluster while another is a long, thin ellipse. Standard LDA averages these into a single global within-class scatter matrix ($S_w$), which often results in a poor fit for individual class pairs.
- The "Easy Class" Bias: Standard LDA treats all class pairs equally. If two classes are already well-separated, LDA still allocates "energy" to separate them further, often at the expense of overlapping classes that require more discriminative focus.
Methods
The authors bridge information theory and classical statistics to create a more flexible model that addresses these shortcomings.
Pairwise Covariance and Weighting
Instead of a single global $S_w$, pcLDA calculates a unique covariance matrix for every pair of classes, capturing local data geometry more accurately. The core innovation is a new objective function that minimizes the sum of inverse distances between classes. By utilizing a hyper-parameter $q$, the algorithm is forced to focus on pairs with the smallest distances. If two classes are dangerously close, the "penalty" in the objective function becomes very large, forcing the projection to prioritize their separation—a "squeaky wheel gets the grease" approach.
Optimization and Extensions
Because the projection matrix must remain orthonormal, the authors employ a gradient descent algorithm designed for the Stiefel manifold. Additionally, a "Kernel pcLDA" variant is provided to handle datasets where classes are not linearly separable.
Results and Key Insights
The authors evaluated pcLDA against standard LDA and several modern variants (such as MMC and Orthogonal LDA) across diverse datasets, including Iris, MSRCv1, UMist, MNIST, and Binalpha.
- Superior Accuracy: pcLDA consistently outperformed state-of-the-art methods. The most significant gains were observed on the Binalpha dataset (36 classes), where pcLDA improved classification accuracy by nearly 5% over standard LDA, demonstrating the power of pairwise statistics as class counts increase.
- Enhanced Separability: Visualizations of projected data show that pcLDA creates much tighter, more distinct clusters compared to the "smearing" often seen in standard LDA projections.
Theoretical Bridge
The paper provides a solid theoretical justification for the "trace-of-ratio" objective used in LDA by linking it directly to Kullback-Leibler (KL) divergence, resolving long-standing ambiguities regarding different LDA formulations.
Conclusion
While pcLDA offers significant accuracy improvements, it introduces higher computational costs due to the need to calculate statistics for all $K(K-1)/2$ class pairs. Future work may involve optimizing this for datasets with thousands of classes or developing "active" dimensionality reduction where weighting changes dynamically based on classifier feedback. Despite these challenges, pcLDA represents a robust advancement for high-dimensional classification tasks where local class geometry is critical.
Summary updated