Fast Algorithms for the Generalized Foley-Sammon Discriminant Analysis

Lei-Hong Zhang, Li-Zhi Liao, Michael K. NgSIAM J. Matrix Anal. Appl 2010 · DOI

TL;DR

This paper introduces faster and more robust algorithms for Generalized Foley-Sammon Transform (GFST) and its regularized version (RGFST), crucial for dimension reduction in high-dimensional data. The key contribution is proving quadratic convergence for these algorithms, even with computational inaccuracies, and developing a more efficient RGFST for undersampled datasets.

What Problem Does This Paper Address?

In fields like data mining, machine learning, and bioinformatics, datasets often have a very high number of features (dimensions) compared to the number of samples. This "curse of dimensionality" makes analysis difficult and inefficient. Linear Discriminant Analysis (LDA) is a popular technique to reduce this dimensionality by projecting data into a lower-dimensional space while preserving class separability. However, standard LDA methods struggle with undersampled problems (where the number of features N is much larger than the number of samples n) due to matrix singularity. This paper addresses these limitations by proposing faster algorithms for GFST and a regularized version (RGFST) that can handle these undersampled scenarios more effectively and with proven convergence guarantees.

Methods

The paper focuses on optimizing the trace ratio criterion for LDA. The core of their work involves:

  • Reduced Model for RGFST: They establish an equivalent, smaller-dimensional model for the regularized GFST (RGFST). This reduction from N to n dimensions significantly improves computational efficiency.
  • Quadratic Convergence Proof: A major contribution is the theoretical proof of quadratic convergence for the iterative algorithm used to solve the GFST and the reduced RGFST. This means the algorithm converges to the solution very quickly, even when dealing with inexact computations (e.g., due to floating-point errors).
  • Unified Optimization Framework: The paper frames the problem within a general optimization framework for maximizing a trace ratio, allowing their algorithms to be applicable to various LDA variants.
  • Algorithm 2 for RGFST: Based on the reduced model, they propose a practical, two-stage algorithm (Algorithm 2) for the RGFST, which leverages the efficient computation of the reduced problem.
  • Implicitly Restarted Lanczos Method (IRLM): For practical implementation, they suggest using IRLM to efficiently compute the required eigenvalues and eigenvectors, which is crucial for large-scale problems.

Datasets

The paper evaluates their algorithms on a variety of real-world datasets:

  • Image Datasets: ORL (faces), Yale (faces), Yale B (faces).
  • Gene Expression Datasets: Leukaemia (MIT AML/ALL), Colon cancer.
  • Text Datasets: Text A2, Text B2, Text A4, Text A4-U (all derived from the 20-Newsgroups dataset).

These datasets represent typical scenarios with high dimensionality and varying numbers of classes, including undersampled problems.

Key Insights and Ideas

  • The power of reduction: Reducing the problem's dimension from N to n for RGFST is a critical step that unlocks significant computational gains without sacrificing performance.
  • Guaranteed fast convergence: Proving quadratic convergence is a major theoretical advancement, assuring users that the algorithm will converge rapidly and reliably, even in the presence of numerical noise. This is a significant improvement over previous methods that lacked theoretical convergence rate analysis.
  • Unified approach for LDA variants: Framing the problem within a general trace ratio optimization problem highlights the underlying mathematical structure and allows for a more general understanding and solution.
  • Practicality for undersampled data: The RGFST and its associated algorithms are specifically designed to tackle the common and challenging undersampled problem, making them highly relevant for modern data analysis.

Key Results

  • Theoretical Proofs: The paper provides rigorous proofs for the global and quadratic convergence of their proposed algorithms for GFST and RGFST.
  • Efficient RGFST: An equivalent reduced model for RGFST is established, leading to a more efficient algorithm.
  • Experimental Performance: Numerical experiments on various datasets show that the proposed GFST model (and its RGFST variant) achieves competitive or superior classification accuracies compared to other methods. The average iteration numbers for Algorithm 1 were consistently low (less than 10), indicating fast convergence in practice.

Limitations and Future Work

  • Computational Cost of Eigenvalue Problems: While IRLM is efficient, computing eigenvalues and eigenvectors for very large matrices can still be computationally intensive. The paper mentions that the complexity is roughly O(n²m) per iteration for IRLM, where l ≤ m ≤ n.
  • Parameter Tuning: The regularization parameter μ in RGFST needs to be chosen optimally. The paper uses 5-fold cross-validation to find the best μ, which is a standard but computationally demanding procedure.
  • Future Work: The paper's conclusions suggest that the established theoretical framework and algorithms provide a strong foundation for further research in dimensionality reduction and classification. The authors' focus on convergence analysis and practical implementation paves the way for more robust and efficient machine learning tools.

Summary updated

BibTeX
@article{zhang2010fast,
  author = {Lei-Hong Zhang and Li-Zhi Liao and Michael K. Ng},
  title = {{Fast Algorithms for the Generalized Foley-Sammon Discriminant Analysis}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2010},
  doi = {10.1137/080720863},
}
Figure