Random Projections for Linear Support Vector Machines

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.

• Publication year

  2012

• Venue

  TKDD

• Publication date

  2012-11-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2641760arXiv 1211.6085
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Statistical Learning Theory

  2021cited by this paper
• Low-Rank Approximation and Regression in Input Sparsity Time

  2012influential reference
• OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

  2012influential reference
• Low rank approximation and regression in input sparsity time

  2012cited by this paper
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

  2012influential reference
• Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

  2012cited by this paper
• Is margin preserved after random projection?

  2012cited by this paper
• Recovering the Optimal Solution by Dual Random Projection

  2012cited by this paper
• Random Projections for Support Vector Machines

  2012cited by this paper
• LIBSVM: A library for support vector machines

  2011cited by this paper
• Ancestry informative markers for fine-scale individual assignment to worldwide populations

  2010cited by this paper
• Low rank matrix-valued chernoff bounds and approximate matrix multiplication

  2010influential reference
• Randomized Algorithms for Large scale SVMs

  2009cited by this paper
• Hash Kernels for Structured Data

  2009influential reference
• LIBLINEAR: A Library for Large Linear Classification

  2008influential reference
• A Randomized Algorithm for Large Scale Support Vector Learning

  2007cited by this paper
• Faster least squares approximation

  2007cited by this paper
• Orthogonal Laplacianfaces for Face Recognition

  2006cited by this paper
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

  2006cited by this paper
• Very sparse random projections

  2006cited by this paper
• Random Projection, Margins, Kernels, and Feature-Selection

  2005cited by this paper
• RCV1: A New Benchmark Collection for Text Categorization Research

  2004cited by this paper
• Parameterized generation of labeled datasets for text categorization based on a hierarchical directory

  2004influential reference
• An elementary proof of a theorem of Johnson and Lindenstrauss

  2003cited by this paper
• On the Learnability and Design of Output Codes for Multiclass Problems

  2002cited by this paper
• Provably Fast Support Vector Regression Using Random Sampling ∗

  2002cited by this paper
• A Random Sampling Technique for Training Support Vector Machines

  2001cited by this paper
• Systematic variation in gene expression patterns in human cancer cell lines

  2000cited by this paper
• An Introduction to Support Vector Machines and Other Kernel-based Learning Methods

  2000cited by this paper
• Statistical learning theory

  1998cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper
• Supporting Online Material Materials and Methods Figs. S1 to S3 Tables S1 to S5 References Worldwide Human Relationships Inferred from Genome-wide Patterns of Variation

  year unknowncited by this paper

• Predicting Protein Subcellular Localization of E. coli Bacteria Using Machine Learning Classifiers

  2024cites this paper
• Feature Space Sketching for Logistic Regression

  2023cites this paper
• Random projection using random quantum circuits

  2023cites this paper
• Subsampled Randomized Hadamard Transformation-based Ensemble Extreme Learning Machine for Human Activity Recognition

  2023cites this paper
• Sketching in High-Dimensional Regression With Big Data Using Gaussian Scale Mixture Priors

  2022cites this paper
• A model aggregation approach for high-dimensional large-scale optimization

  2022cites this paper
• Consistent, Balanced, and Overlapping Label Trees for Extreme Multi-label Learning

  2022cites this paper
• Jointly evolving and compressing fuzzy system for feature reduction and classification

  2021cites this paper
• Super Learner Implementation in Corrosion Rate Prediction

  2021cites this paper
• The Product of Gaussian Matrices is Close to Gaussian

  2021cites this paper
• An Introduction to Johnson-Lindenstrauss Transforms

  2021cites this paper
• The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery

  2020cites this paper
• The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization with Outliers

  2020cites this paper
• Stable Sparse Subspace Embedding for Dimensionality Reduction

  2020cites this paper
• Effective and Sparse Count-Sketch via k-means clustering

  2020cites this paper
• Random projections for quadratic programs

  2020cites this paper
• Big data aggregation in the case of heterogeneity: a feasibility study for digital health

  2019cites this paper
• A Data-Independent Reusable Projection (DIRP) Technique for Dimension Reduction in Big Data Classification Using k-Nearest Neighbor (k-NN)

  2019cites this paper
• Pattern Recognition

  2019cites this paper
• Random projections for quadratic programs 1

  2019cites this paper
• On the optimal solution to maximum margin projection pursuit

  2019cites this paper
• A Framework for Bayesian Optimization in Embedded Subspaces

  2019cites this paper
• An Efficient Method for NMR Data Compression Based on Fast Singular Value Decomposition

  2019cites this paper
• Random Projection for Linear 2-norm Support Vector Machine

  2018influential citation
• Training neural networks on high-dimensional data using random projection

  2018cites this paper
• Fully Understanding the Hashing Trick

  2018cites this paper
• Improved Random Projection with $K$-Means Clustering for Hyperspectral Image Classification

  2018cites this paper
• Random Projection in Deep Neural Networks

  2018cites this paper
• Fast Fisher discriminant analysis with randomized algorithms

  2017cites this paper
• Random Hadamard Projections for Hyperspectral Unmixing

  2017cites this paper
• Integrating a weighted-average method into the random walk framework to generate individual friend recommendations

  2017cites this paper
• MREKLM: A fast multiple empirical kernel learning machine

  2017cites this paper
• Dual Random Projection for Linear Support Vector Machine

  2017cites this paper
• Random Projection for Linear Twin Support Vector Machine

  2017influential citation
• Fast Constrained Spectral Clustering and Cluster Ensemble with Random Projection

  2017cites this paper
• Fast approximate solution of large dense linear programs

  2016cites this paper
• Large-scale strategic games and adversarial machine learning

  2016cites this paper
• Nuclear Norm Regularized Randomized Neural Network

  2016cites this paper
• Hadamard-Walsh random projection for hyperspectral image classification

  2016cites this paper
• Fast SVD With Random Hadamard Projection for Hyperspectral Dimensionality Reduction

  2016cites this paper
• How to Fake Multiply by a Gaussian Matrix

  2016influential citation
• Random-projection-based nonnegative least squares for hyperspectral image unmixing

  2016cites this paper
• Random projections for Bayesian regression

  2015cites this paper
• Improved Bounds on the Dot Product under Random Projection and Random Sign Projection

  2015influential citation
• Convergence analysis of the approximate proximal splitting method for non-smooth convex optimization

  2014cites this paper
• Feature selection for linear SVM with provable guarantees

  2014cites this paper
• Lower Bounds for Oblivious Subspace Embeddings

  2013cites this paper
• Sharp Generalization Error Bounds for Randomly-projected Classifiers

  2013cites this paper
• Recovering the Optimal Solution by Dual Random Projection

  2012cites this paper
• Low rank approximation and regression in input sparsity time

  2012cites this paper
• Low-Rank Approximation and Regression in Input Sparsity Time

  2012cites this paper
• The Product of Gaussian Matrices is Close to 1 Gaussian 2

  year unknowncites this paper