Unifying Orthogonal LDA: The Hidden Synthesis of Trace Ratio and Null-Space Methods

TL;DR

This research provides a rigorous theoretical proof that two of the most popular orthogonal extensions of Linear Discriminant Analysis—Trace Ratio LDA (TR-LDA) and Null-space LDA (NLDA)—are mathematically equivalent when dealing with the "Singularity Problem" (small sample size). By bridging these methods via a Trace Difference criterion, the authors simplify the landscape of dimensionality reduction, showing that TR-LDA provides a universal framework that encompasses NLDA, OLDA, and DCV.

Problem & Motivation: The Singularity Trap

In modern machine learning, we often encounter datasets where the dimensionality ($D$) is much larger than the number of samples ($l$), such as face recognition or document categorization. In these cases, the within-class scatter matrix ($S_w$) becomes singular (non-invertible).

Traditional Fisher LDA fails because it requires inverting $S_w$. To solve this:

• NLDA searches for discriminative information specifically in the null space of $S_w$.
• TR-LDA maximizes a ratio of traces using an iterative procedure to avoid direct inversion.

The authors' core Insight was that while these two methods use different computational paths (iterative vs. closed-form null-space projection), they both seek the same optimal orthogonal transformation when the data is high-dimensional and sparse.

Methodology: The Trace Difference Bridge

The paper's breakthrough lies in using the Trace Difference Criterion as an intermediary: $W^{\ast }=\arg {\max }_{W^{T}W=I}Tr[W^T(S_b-\lambda S_w)W]$

The Theoretical Proof

1. Iterative Convergence: The authors show that TR-LDA is solved by iteratively updating $\lambda$ and finding the zero point of a trace difference function.
2. The $\lambda o\infty$ Limit: They prove that as $\lambda$ grows (which happens when $S_w$ is near-singular), the eigenvectors of the trace difference problem align perfectly with the basis vectors of the null space of $S_w$.
3. Unified Framework: This logic extends to other variants, proving that OLDA (Orthogonal LDA) and DCV (Discriminative Common Vectors) are also members of this equivalent family under specific rank conditions.

Figure 1: The pictorial relationship demonstrating how TR-LDA serves as the overarching framework for other orthogonal LDA variants.

Experiments & Results: Performance in the Wild

The researchers tested their theory on the UMIST Face and COIL20 Object datasets.

1. Verification of Equivalence

When the "Singularity Problem" was present (e.g., only 4 training samples), TR-LDA, NLDA, DCV, and OLDA produced identical classification accuracy curves. This empirically validated the mathematical proof of equivalence.

2. Superiority in Image Segmentation

In tasks where $S_w$ is not singular (e.g., pixel-level image segmentation), TR-LDA demonstrated its true strength. Because it directly optimizes the ratio of Euclidean distances, it achieved much cleaner segmentation of complex objects (like a boat against a sea background) compared to PCA or standard LDA.

Figure 2: TR-LDA (bottom right) shows significantly fewer misclassified pixels in the boat and sea categories compared to OLDA and MMC.

Critical Analysis & Conclusion

Takeaway

The paper effectively "cleans up" a cluttered subfield of dimensionality reduction. By proving that TR-LDA is a more general version of NLDA, it suggests that researchers no longer need to choose between them based on whether a matrix is singular—TR-LDA handles both cases optimally.

Limitations & Future Work

While the equivalence holds for the global optimum, the computational cost of the iterative TR-LDA can be higher than the closed-form SVD-based NLDA. Future research could focus on hybrid solvers that switch from iterative to closed-form projections automatically when singularity is detected to save GPU/CPU cycles.

Ultimately, this work reinforces the value of seeking Orthogonal Projections; they preserve Euclidean distances, ensuring that "similar" items in high-dimensional space remain "similar" after we've compressed them.