Trace Ratio Problem Revisited: Beyond the Greedy Eigenvalue Approximation

TL;DR

Dimensionality reduction is a cornerstone of pattern recognition, but we've often settled for "good enough" approximations. This paper revisits the Trace Ratio (TR) problem, proving that we can find the global optimum more efficiently than previously thought. By introducing Eigenvalue Perturbation Theory, the authors propose the Decomposed Newton’s Method (DNM), which outperforms classic Generalized Eigenvalue Decomposition (GEVD) in both accuracy and theoretical convergence speed.

The "Ratio Trace" Trap

In classic Linear Discriminant Analysis (LDA), we seek a transformation matrix $W$ that maximizes between-class scatter while minimizing within-class scatter. Mathematically, this is expressed as:

$W^{\ast }=\arg {\max }_W\frac{extTr[W^T{S}_{b}W]}{extTr[W^T{S}_{w}W]}$

Most practitioners solve this using the Ratio Trace approximation: $extTr[(W^T{S}_{w}W{)}^{-1}(W^T{S}_{b}W)]$. Why? Because it has a closed-form solution via GEVD. However, this is a greedy approach. It optimizes each dimension independently rather than the collective ratio, leading to a performance gap, especially as the number of dimensions ($d$) increases.

Methodology: The Power of Perturbation

The authors tackle the TR problem by transforming it into a Trace Difference problem: finding the zero point of $f(\lambda )=\max extTr[W^T(S_p-\lambda S_l)W]$.

The Decomposed Newton’s Method (DNM)

Past attempts (like the ITR algorithm) used a naive Newton-Raphson approach. This paper improves upon this by using Eigenvalue Perturbation Theory. Instead of approximating the total function $f(\lambda )$ linearly, DNM decomposes the function into its constituent eigenvalues.

It approximates the eigenvalues individually using first-order Taylor expansions: ${\hat{\beta }}_k(\lambda )={\beta }_k({\lambda }_t)-(\lambda -{\lambda }_t)w_k^T{S}_l{w}_k$

The Intuition: The "largest" eigenvalues at a specific point ${\lambda }_t$ might not remain the largest as $\lambda$ changes. By dynamically re-selecting the top eigenvalues at each iteration, DNM provides a tighter lower bound than ITR, ensuring faster convergence.

Experimental Battleground

The researchers tested their method against PCA, GEVD (Ratio Trace), and Maximum Margin Criterion (MMC) on several datasets, including ORL, UMist, and MNIST.

Key Results:

1. Accuracy Boost: On the ORL face database, the TR method achieved an error rate significantly lower than the Ratio Trace (GEVD) solution.
2. Convergence Efficiency: DNM was empirically and theoretically proven to converge in fewer iterations than ITR.
3. High-Dimensional Robustness: The TR framework showed its greatest strength in "small sample size" problems—where the dimensionality is high but the number of images is low.

Fig 1: Toy example showing how DNM (dashed line) provides a closer approximation to the true trace difference function (solid line) compared to ITR.

Critical Insight: Why This Matters

The fundamental contribution here isn't just a faster algorithm—it's the bridge between Matrix Analysis and Dimensionality Reduction. By showing that the Maximum Margin Criterion (MMC) is essentially a special, non-optimized case of the Trace Ratio framework (where $\lambda =1$), the authors provide a unified perspective on feature extraction.

Limitations & Future Work

While DNM is highly efficient, each iteration still requires an eigenvalue decomposition, which can be computationally expensive for extremely high-dimensional matrices (e.g., $10^{5}imes10^5$). Future research could explore Stochastic versions of DNM or integrate this trace-ratio optimization directly into the loss functions of Deep Neural Networks to replace standard softmax-based feature learning.

Conclusion

The "Trace Ratio Problem Revisited" reminds us that mathematical rigor in optimization can yield significant practical gains. If you are still using standard GEVD for supervised dimensionality reduction, you are likely leaving performance on the table.