TR2006-046

Generalized Spectral Bounds for Sparse LDA


    •  Moghaddam, B., Weiss, Y., Avidan, S., "Generalized Spectral Bounds for Sparse LDA", Tech. Rep. TR2006-046, Mitsubishi Electric Research Laboratories, Cambridge, MA, June 2006.
      BibTeX Download PDF
      • @techreport{MERL_TR2006-046,
      • author = {Moghaddam, B. and Weiss, Y. and Avidan, S.},
      • title = {Generalized Spectral Bounds for Sparse LDA},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR2006-046},
      • month = jun,
      • year = 2006,
      • url = {http://www.merl.com/publications/TR2006-046/}
      • }
  • Research Area:

    Data Analytics


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.