Sparse generalized eigenvalue problem: optimal statistical rates via truncated Rayleigh flow

Kean Ming Tan, Zhaoran Wang, Han Liu and Tong Zhang

Journal of the Royal Statistical Society Series B, 2018, vol. 80, issue 5, 1057-1086

Abstract: The 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. The 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. 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 non‐convex optimization perspective and propose the truncated Rayleigh flow method (which we call ‘rifle’) to estimate the leading generalized eigenvector. We show that rifle converges linearly to a solution with the optimal statistical rate of convergence. Theoretically, our method significantly improves on the existing literature by eliminating structural assumptions on the input matrices. To achieve this, our analysis involves two key ingredients: a new analysis of the gradient‐based method on non‐convex objective functions, and a fine‐grained characterization of the evolution of sparsity patterns along the solution path. Thorough numerical studies are provided to validate the theoretical results.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1111/rssb.12291

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jorssb:v:80:y:2018:i:5:p:1057-1086

Ordering information: This journal article can be ordered from
http://ordering.onli ... 1111/(ISSN)1467-9868

Access Statistics for this article

Journal of the Royal Statistical Society Series B is currently edited by P. Fryzlewicz and I. Van Keilegom

More articles in Journal of the Royal Statistical Society Series B from Royal Statistical Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().