Random Projections for Linear Support Vector Machines
Saurabh Paul, Christos Boutsidis, Malik Magdon‐Ismail, Petros Drineas · ACM Transactions on Knowledge Discovery from Data · 2014
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.