A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem

Details A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem

2009-01-12

arxiv.org/abs/0901.1504v2

Statistics

Machine Learning

40 pages

Scientific paper

In this paper, we consider the sparse eigenvalue problem wherein the goal is to obtain a sparse solution to the generalized eigenvalue problem. We achieve this by constraining the cardinality of the solution to the generalized eigenvalue problem and obtain sparse principal component analysis (PCA), sparse canonical correlation analysis (CCA) and sparse Fisher discriminant analysis (FDA) as special cases. Unlike the $\ell_1$-norm approximation to the cardinality constraint, which previous methods have used in the context of sparse PCA, we propose 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 \emph{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. The performance of the algorithm is empirically demonstrated on both sparse PCA (finding few relevant genes that explain as much variance as possible in a high-dimensional gene dataset) and sparse CCA (cross-language document retrieval and vocabulary selection for music retrieval) applications.

Affiliated with

Also associated with

No associations

Rating

A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A D.C. Programming Approach to the Sparse Generalized Eigenvalue Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-532055