• 
• 
• 
• 
• 
• 

Generalized Spectral Bounds for Sparse LDA

Date:
June 2006

MERL Contact: Joseph Katz

Authors: Moghaddam, B.; Weiss, Y.; Avidan, S.

Where Published: International Conference on Machine Learning (ICML'06)

Abstract: We present a discrete spectral framework for the sparse or cardinality-constrained solution of a generalized Rayleigh quotient. This NP-hard combinatorial optimization problem is central to supervised learning tasks such as sparse LDA, feature selection and relevance ranking for classification. We derive a new generalized form of the Inclusion Principle for variational eigenvalue bounds, leading to exact and optimal sparse linear discriminants using branch-and-bound search. An efficient greedy (approximate) technique is also presented. The generalization performance of our sparse LDA algorithms is demonstrated with real-world UCI ML benchmarks and compared to a leading SVM-based gene selection algorithm for cancer classification.

Read the full technical report (PDF: 176.8 kB)