Sparse Generalized Eigenvalue Problem Via Smooth Optimization

DOI10.1109/TSP.2015.2394443MaRDI QIDQ4580466zbMATH OpenOpenAlexFDO

Authors Junxiao Song, Prabhu Babu, D. P. Palomar

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.6686

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: In this paper, we consider an $el{l}_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 $el{l}_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.

Cited in

(8)

• Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
• Sparse optimization problems in fractional order Sobolev spaces
• An \(\ell_1\)-penalized adaptive normalized quasi-Newton algorithm for sparsity-aware generalized eigen-subspace tracking
• Penalized Orthogonal Iteration for Sparse Estimation of Generalized Eigenvalue Problem
• Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow
• A majorization-minimization approach to the sparse generalized eigenvalue problem
• First-order algorithms for a class of fractional optimization problems
• A unified framework for structured graph learning via spectral constraints

This page was built for publication: Sparse Generalized Eigenvalue Problem Via Smooth Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580466)