# Sparse Generalized Eigenvalue Problem: Optimal Statistical Rates via Truncated Rayleigh Flow

arXiv: https://arxiv.org/abs/1604.08697 · HTML: https://mlsanity.com/paper/1604.08697/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2016.

## Built on by (most cited first, 6 of 6)

- [Sparse GCA and Thresholded Gradient Descent](https://mlsanity.com/paper/2107.00371/) (2021)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems](https://mlsanity.com/paper/2112.14738/) (2021)
- [ℓ1-norm constrained multi-block sparse canonical correlation analysis via proximal gradient descent](https://mlsanity.com/paper/2201.05289/) (2022)
- [Penalized Principal Component Analysis Using Smoothing](https://mlsanity.com/paper/2309.13838/) (2023)
- [λ-PSD: Scalable Approximate SNR-Optimised Polynomial Stein Discrepancies](https://mlsanity.com/paper/2606.26621/) (2026)

## Abstract (arXiv)

Sparse generalized eigenvalue problem (GEP) plays a pivotal role in a large family of high-dimensional statistical models, including sparse Fisher's discriminant analysis, canonical correlation analysis, and sufficient dimension reduction. Sparse GEP involves solving a non-convex optimization problem. Most existing methods and theory in the context of specific statistical models that are special cases of the sparse GEP require restrictive structural assumptions on the input matrices. In this paper, we propose a two-stage computational framework to solve the sparse GEP. At the first stage, we solve a convex relaxation of the sparse GEP. Taking the solution as an initial value, we then exploit a nonconvex optimization perspective and propose the truncated Rayleigh flow method (Rifle) to estimate the leading generalized eigenvector. We show that Rifle converges linearly to a solution with the optimal statistical rate of convergence for many statistical models. Theoretically, our method significantly improves upon the existing literature by eliminating structural assumptions on the input matrices for both stages. To achieve this, our analysis involves two key ingredients: (i) a new analysis of the gradient based method on nonconvex objective functions, and (ii) a fine-grained characterization of the evolution of sparsity patterns along the solution path. Thorough numerical studies are provided to validate the theoretical results.