Random Projections for Linear Support Vector Machines
Abstract
Let X be a data matrix of rank ρ, whose rows represent n points in d -dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1-norm soft margin. We develop a new oblivious dimension reduction technique that is precomputed and can be applied to any input matrix X . We prove that, with high probability, the margin and minimum enclosing ball in the feature space are preserved to within ϵ-relative error, ensuring comparable generalization as in the original space in the case of classification. For regression, we show that the margin is preserved to ϵ-relative error with high probability. We present extensive experiments with real and synthetic data to support our theory.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 29, 2014
- Source ID
- 10.1145/2641760
Entities
People
- Christos Boutsidis
- Malik Magdon-ismail
- Petros Drineas
- Saurabh Paul
Organizations
- Air Force Research Laboratory
- Defense Advanced Research Projects Agency
- Division of Computing and Communication Foundations
- National Science Foundation Division of Mathematical Sciences
- Rensselaer Polytechnic Institute
- Yahoo! Labs