Sparse Generalized Eigenvalue Problem via Smooth Optimization

Abstract

In this paper, we consider an ${\ell }_0$-norm penalized formulation of the generalized eigenvalue problem (GEP), aimed at extracting the leading sparse generalized eigenvector of a matrix pair. The formulation involves maximization of a discontinuous nonconcave objective function over a nonconvex constraint set, and is therefore computationally intractable. To tackle the problem, we first approximate the ${\ell }_0$-norm by a continuous surrogate function. Then an algorithm is developed via iteratively majorizing the surrogate function by a quadratic separable function, which at each iteration reduces to a regular generalized eigenvalue problem. A preconditioned steepest ascent algorithm for finding the leading generalized eigenvector is provided. A systematic way based on smoothing is proposed to deal with the "singularity issue" that arises when a quadratic function is used to majorize the nondifferentiable surrogate function. For sparse GEPs with special structure, algorithms that admit a closed-form solution at every iteration are derived. Numerical experiments show that the proposed algorithms match or outperform existing algorithms in terms of computational complexity and support recovery.

References in corpus (3)

• NESTA: A Fast and Accurate First-order Method for Sparse Recovery
• Generalized power method for sparse principal component analysis
• Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems

Cited by in corpus (13)

• A Unified Framework for Structured Graph Learning via Spectral Constraints
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Mean-Reverting Portfolio Design with Budget Constraint
• Convergence Rate Analysis of the Majorize-Minimize Subspace Algorithm -- Extended Version
• Penalized Orthogonal Iteration for Sparse Estimation of Generalized Eigenvalue Problem
• Design of MIMO Radar Waveforms based on lp-Norm Criteria
• Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
• Sparse optimization problems in fractional order Sobolev spaces
• Multi-Rank Sparse and Functional PCA: Manifold Optimization and Iterative Deflation Techniques
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation
• An Inverse-free Truncated Rayleigh-Ritz Method for Sparse Generalized Eigenvalue Problem
• A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
• An iterative coordinate descent algorithm to compute sparse low-rank approximations