Abstract
Dimensionality reduction is a critical step in processing high-dimensional data such as images. While Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are widely used, they rely on global statistics and often fail to capture the local manifold structure. We propose Locality Sensitive Discriminant Analysis (LSDA), which focuses on the local neighborhood of each data point. By constructing within-class and between-class graphs, LSDA finds a projection that keeps nearby points of the same class together while separating nearby points of different classes. Our experiments on the Yale and ORL face databases show that LSDA consistently outperforms traditional methods, particularly in small-sample scenarios.
Introduction
In fields like computer vision and pattern recognition, datasets often consist of high-dimensional points, such as pixel intensities in face images. To make this data manageable, dimensionality reduction is employed. Traditional "gold standard" methods like PCA and LDA are global; they consider the mean and variance of the entire dataset. However, real-world data often lies on a complex, curved manifold where global statistics may not accurately reflect local relationships. Furthermore, LDA's performance can degrade significantly when the number of training samples is insufficient to estimate these global statistics.
Methodology
LSDA shifts the focus from global statistics to the local neighborhood, making it "manifold-aware." The process involves three key stages:
- Graph Construction: For every data point, the algorithm identifies its $k$ nearest neighbors.
- Graph Splitting: The neighborhood is partitioned into two distinct sub-graphs:
- Within-class graph ($G_w$): Connects the point to neighbors sharing the same label.
- Between-class graph ($G_b$): Connects the point to neighbors with different labels.
- Optimization: LSDA seeks a projection that simultaneously minimizes the distance between points in $G_w$ and maximizes the distance between points in $G_b$. This is formulated as a generalized eigenvalue problem.
By maximizing this local margin—the gap between different classes at specific points on the manifold—LSDA respects the underlying geometry of the data distribution more effectively than global methods.
Experimental Evaluation
The researchers evaluated LSDA using two benchmark face recognition datasets:
- The Yale Face Database: 165 images of 15 individuals with varying lighting and expressions.
- The ORL Face Database: 400 images of 40 individuals with variations in time and facial details.
Key Results
LSDA demonstrated superior performance across multiple metrics:
- Small Sample Success: On the Yale database with only 2 training images per person, LSDA achieved 56.5% accuracy, significantly higher than Fisherfaces (LDA) at 47.2%.
- Consistent Superiority: On the ORL database, LSDA reached 93.6% accuracy with 5 training samples, outperforming both Fisherfaces (93.2%) and the PCA baseline (86.6%).
- Robustness: LSDA proved less sensitive to dimensionality estimation errors compared to other subspace learning methods.
Conclusion
Locality Sensitive Discriminant Analysis provides a robust framework for supervised dimensionality reduction by prioritizing local geometric structure over global statistics. By focusing on the local margin, LSDA achieves higher accuracy and greater robustness, particularly in challenging scenarios with limited training data. Future work may further explore the non-linear capabilities of Kernel LSDA in more diverse datasets.
Summary updated