A majorization-minimization approach to the sparse generalized eigenvalue problem

作者：Sriperumbudur Bharath K^*; Torres David A; Lanckriet Gert R G

来源：Machine Learning, 2011, 85(1-2): 3-39.

DOI：10.1007/s10994-010-5226-3

• Generalized eigenvalue problem
• Principal component analysis
• Canonical correlation analysis
• Fisher discriminant analysis
• Sparsity
• D.c. program
• Majorization-minimization
• Zangwill's theory of global convergence
• Music annotation
• Cross-language document retrieval

Generalized eigenvalue (GEV) problems have applications in many areas of science and engineering. For example, principal component analysis (PCA), canonical correlation analysis (CCA) and Fisher discriminant analysis (FDA) are specific instances of GEV problems, that are widely used in statistical data analysis. The main contribution of this work is to formulate a general, efficient algorithm to obtain sparse solutions to a GEV problem. Specific instances of sparse GEV problems can then be solved by specific instances of this algorithm. We achieve this by solving the GEV problem while constraining the cardinality of the solution. Instead of relaxing the cardinality constraint using a a"" (1)-norm approximation, we consider a tighter approximation that is related to the negative log-likelihood of a Student's t-distribution. The problem is then framed as a d.c. (difference of convex functions) program and is solved as a sequence of convex programs by invoking the majorization-minimization method. The resulting algorithm is proved to exhibit global convergence behavior, i.e., for any random initialization, the sequence (subsequence) of iterates generated by the algorithm converges to a stationary point of the d.c. program. Finally, we illustrate the merits of this general sparse GEV algorithm with three specific examples of sparse GEV problems: sparse PCA, sparse CCA and sparse FDA. Empirical evidence for these examples suggests that the proposed sparse GEV algorithm, which offers a general framework to solve any sparse GEV problem, will give rise to competitive algorithms for a variety of applications where specific instances of GEV problems arise.

• 出版日期2011-10