A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
arXiv:1802.09303
Abstract
The sparse generalized eigenvalue problem arises in a number of standard and modern statistical learning models, including sparse principal component analysis, sparse Fisher discriminant analysis, and sparse canonical correlation analysis. However, this problem is difficult to solve since it is NP-hard. In this paper, we consider a new decomposition method to tackle this problem. Specifically, we use random or/and swapping strategies to find a working set and perform global combinatorial search over the small subset of variables. We consider a bisection search method and a coordinate descent method for solving the quadratic fractional programming subproblem. In addition, we provide some theoretical analysis for the proposed method. Our experiments have shown that the proposed method significantly and consistently outperforms existing solutions in term of accuracy.
To appear in CVPR 2019
References in corpus (6)
- Generalized power method for sparse principal component analysis
- A direct formulation for sparse PCA using semidefinite programming
- Sparse Generalized Eigenvalue Problem via Smooth Optimization
- Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization
- Incremental Training of a Detector Using Online Sparse Eigen-decomposition
- A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization