Please use this identifier to cite or link to this item:

Sparse Generalized Eigenvalue Problem Via Smooth Optimization

Authors Song, Junxiao HKUST affiliated (currently or previously)
Babu, Prabhu HKUST affiliated (currently or previously)
Palomar, Daniel P. View this author's profile
Issue Date 2015
Source IEEE Transactions on Signal Processing , v. 63, (7), April 2015, article number 7017587, p. 1627-1642
Summary In this paper, we consider an - 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 - 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.
ISSN 1053-587X
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus