Generalized Spectral Bounds for Sparse LDA
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.
Cite
Text
Moghaddam et al. "Generalized Spectral Bounds for Sparse LDA." International Conference on Machine Learning, 2006. doi:10.1145/1143844.1143925Markdown
[Moghaddam et al. "Generalized Spectral Bounds for Sparse LDA." International Conference on Machine Learning, 2006.](https://mlanthology.org/icml/2006/moghaddam2006icml-generalized/) doi:10.1145/1143844.1143925BibTeX
@inproceedings{moghaddam2006icml-generalized,
title = {{Generalized Spectral Bounds for Sparse LDA}},
author = {Moghaddam, Baback and Weiss, Yair and Avidan, Shai},
booktitle = {International Conference on Machine Learning},
year = {2006},
pages = {641-648},
doi = {10.1145/1143844.1143925},
url = {https://mlanthology.org/icml/2006/moghaddam2006icml-generalized/}
}