Riemannian Manifold Optimization for Discriminant Subspace Learning

Wanguang Yin, Zhengming Ma, Quanying Liu

Abstract

Linear discriminant analysis (LDA) is a widely used algorithm in machine learning to extract a low-dimensional representation of high-dimensional data, it features to find the orthogonal discriminant projection subspace by using the Fisher discriminant criterion. However, the traditional Euclidean-based methods for solving LDA are easily convergent to spurious local minima and hardly obtain an optimal solution. To address such a problem, in this paper, we propose a novel algorithm namely Riemannian-based discriminant analysis (RDA) for subspace learning. In order to obtain an explicit solution, we transform the traditional Euclidean-based methods to the Riemannian manifold space and use the trust-region method to learn the discriminant projection subspace. We compare the proposed algorithm to existing variants of LDA, as well as the unsupervised tensor decomposition methods on image classification tasks. The numerical results suggest that RDA achieves state-of-the-art performance in classification accuracy.

Introduction

Linear Discriminant Analysis (LDA) is a fundamental technique in machine learning and pattern recognition, designed to project high-dimensional data into a lower-dimensional subspace while maximizing class separability. By maximizing the ratio of between-class scatter to within-class scatter, LDA identifies features that are most discriminative. Despite its popularity, traditional Euclidean-based solvers for LDA encounter significant challenges. First, the non-convex nature of the Fisher criterion often leads optimization algorithms to "spurious local minima," resulting in sub-optimal projection matrices. Second, the "singularity problem" arises in high-dimensional, low-sample-size (HDLSS) scenarios where the within-class scatter matrix becomes non-invertible, leading to numerical instability.

Methodology: Riemannian-based Discriminant Analysis (RDA)

To overcome these limitations, we propose Riemannian-based Discriminant Analysis (RDA). Instead of treating the optimization problem in a flat Euclidean space, RDA operates directly on the "curved" geometry of Riemannian manifolds. Specifically, the set of orthogonal projection matrices is modeled as points on a Stiefel manifold or a Grassmann manifold.

Conceptual framework of Riemannian manifold optimization for subspace learning showing the transition from data space to manifold optimization.

Key Technical Innovations

  • Reformulated Objective Function: The traditional Fisher criterion, expressed as a generalized Rayleigh quotient (division), is transformed into a subtraction form. This reformulation simplifies the calculation of the Riemannian Gradient and Hessian, which are essential for advanced optimization.
  • Trust-Region Optimization: Unlike standard first-order methods (like gradient descent), RDA employs a Riemannian trust-region method. This second-order approach utilizes the manifold's curvature to make more informed updates, significantly improving convergence to the global optimum.
  • Sparsity Regularization: To enhance robustness against noise and prevent overfitting, an $L_1$ penalty is integrated into the model, encouraging the learning of sparse discriminant features.

Experimental Setup

The effectiveness of RDA was evaluated across seven diverse image datasets encompassing object, face, and digit recognition tasks. These include:

  • Objects: COIL20 and ETH80.
  • Digits: MNIST and USPS.
  • Faces: ORL, Olivetti, and CMU PIE.
Sample images from the benchmark datasets (Olivetti, COIL20, ETH80, ORL, CMU PIE, and USPS) used to evaluate RDA.

These datasets present various challenges, such as variations in lighting, pose, and high dimensionality relative to the number of samples.

Results and Discussion

RDA demonstrated substantial improvements over traditional Euclidean methods (e.g., HODA, CMDA) and unsupervised tensor methods (e.g., HOSVD).

Clustering and Classification Performance

On the CMU PIE face dataset, RDA achieved a clustering accuracy of 78.66%, a dramatic improvement over HODA (15.46%) and CMDA (12.06%). In classification tasks using 5-fold cross-validation, RDA consistently outperformed competitors. For instance, on the USPS digit dataset, RDA reached 86.00% accuracy, while the nearest Euclidean variant, CMDA, achieved only 56.88%.

Robustness

RDA proved particularly effective in multi-class and large-scale scenarios where traditional methods often fail due to matrix singularity. By working on the manifold, the orthogonality constraints are naturally satisfied, and the subtraction-based objective avoids the instabilities associated with matrix inversion.

Conclusion

Riemannian-based Discriminant Analysis (RDA) offers a robust solution to the long-standing issues of local minima and singularity in LDA. By leveraging the geometric properties of Riemannian manifolds and second-order trust-region optimization, RDA achieves state-of-the-art performance in image classification and clustering. While the computational cost of manifold optimization is higher than Euclidean methods, the gains in accuracy and stability make it a compelling choice for complex subspace learning tasks.

Summary updated

Abstract

Linear discriminant analysis (LDA) is a widely used algorithm in machine learning to extract a low-dimensional representation of high-dimensional data, it features to find the orthogonal discriminant projection subspace by using the Fisher discriminant criterion. However, the traditional Euclidean-based methods for solving LDA are easily convergent to spurious local minima and hardly obtain an optimal solution. To address such a problem, in this paper, we propose a novel algorithm namely Riemannian-based discriminant analysis (RDA) for subspace learning. In order to obtain an explicit solution, we transform the traditional Euclidean-based methods to the Riemannian manifold space and use the trust-region method to learn the discriminant projection subspace. We compare the proposed algorithm to existing variants of LDA, as well as the unsupervised tensor decomposition methods on image classification tasks. The numerical results suggest that RDA achieves state-of-the-art performance in classification accuracy.
BibTeX
@misc{yin2021riemannian,
  author = {Wanguang Yin and Zhengming Ma and Quanying Liu},
  title = {{Riemannian Manifold Optimization for Discriminant Subspace Learning}},
  year = {2021},
  eprint = {2101.08032},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.08032},
}
Figure