Improved Bounds on the Dot Product under Random Projection and Random Sign Projection

No abstract is available for this paper.

• Publication year

  2015

• Venue

  Knowledge Discovery and Data Mining

• Publication date

  2015-08-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2783258.2783364
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Classification with Sign Random Projections

  2014cited by this paper
• An Analysis of Random Projections in Cancelable Biometrics

  2014cited by this paper
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

  2014cited by this paper
• New Bounds on Compressive Linear Least Squares Regression

  2014cited by this paper
• Sharp Generalization Error Bounds for Randomly-projected Classifiers

  2013influential reference
• Random Projections for Linear Support Vector Machines

  2012influential reference
• Disentangling Gaussians

  2012cited by this paper
• Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

  2012cited by this paper
• Compressed Sensing

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

  2012influential reference
• Explicit Dimension Reduction and Its Applications

  2011cited by this paper
• Concentration of Measure for the Analysis of Randomized Algorithms

  2009influential reference
• Compressed Learning : Universal Sparse Dimensionality Reduction and Learning in the Measurement Domain

  2009influential reference
• Neural networks with sigmoidal activation functions—dimension reduction using normal random projection

  2009cited by this paper
• The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors

  2009cited by this paper
• A Simple Proof of the Restricted Isometry Property for Random Matrices

  2008cited by this paper
• On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization

  2008cited by this paper
• A Randomized Algorithm for Large Scale Support Vector Learning

  2007influential reference
• An incremental data-stream sketch using sparse random projections

  2007cited by this paper
• Kernels as features: On kernels, margins, and low-dimensional mappings

  2006cited by this paper
• Detection and estimation with compressive measurements

  2006cited by this paper
• Random projection-based multiplicative data perturbation for privacy preserving distributed data mining

  2006cited by this paper
• Improving Random Projections Using Marginal Information

  2006influential reference
• Random Projection, Margins, Kernels, and Feature-Selection

  2005cited by this paper
• Integration and Optimization of Multivariate Polynomials by Restriction onto a Random Subspace

  2005influential reference
• Problems and results in extremal combinatorics--I

  2003cited by this paper
• Experiments with random projections for machine learning

  2003cited by this paper
• An elementary proof of a theorem of Johnson and Lindenstrauss

  2003cited by this paper
• Similarity estimation techniques from rounding algorithms

  2002cited by this paper
• Problems and results in Extremal Combinatorics , Part

  2002cited by this paper
• Random projection in dimensionality reduction: applications to image and text data

  2001cited by this paper
• Metric characterization of random variables and random processes

  2000cited by this paper
• An elementary proof of the Johnson-Lindenstrauss Lemma

  1999cited by this paper
• An algorithmic theory of learning: Robust concepts and random projection

  1999influential reference
• Learning mixtures of Gaussians

  1999cited by this paper
• Dimensionality reduction by random mapping: fast similarity computation for clustering

  1998cited by this paper
• Two algorithms for nearest-neighbor search in high dimensions

  1997cited by this paper
• Toward a Usable Theory of Chernoff Bounds for Heterogeneous and Partially Dependent Random Variables

  1995cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper

• Structure discovery in PAC-learning by random projections

  2024cites this paper
• Non-Oblivious Performance of Random Projections

  2024cites this paper
• Node Similarities under Random Projections: Limits and Pathological Cases

  2024influential citation
• On the Expressive Flexibility of Self-Attention Matrices

  2023influential citation
• Improved Bound on Generalization Error of Compressed KNN Estimator

  2023influential citation
• Recasting Self-Attention with Holographic Reduced Representations

  2023cites this paper
• Secure Sampling with Sublinear Communication

  2022influential citation
• Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights

  2022influential citation
• Bayesian Non-stationary Linear Bandits for Large-Scale Recommender Systems

  2022cites this paper
• Data-Efficient Learning via Minimizing Hyperspherical Energy

  2022cites this paper
• Bayesian Linear Bandits for Large-Scale Recommender Systems

  2022cites this paper
• Dimensionality reduction in the context of dynamic social media data streams

  2021cites this paper
• On the Expressive Power of Self-Attention Matrices

  2021influential citation
• Design of Resilient Smart Highway Systems with Data-Driven Monitoring from Networked Cameras

  2021cites this paper
• Correlations between random projections and the bivariate normal

  2021cites this paper
• Norm Adjusted Proximity Graph for Fast Inner Product Retrieval

  2021cites this paper
• Simple Yet Efficient Algorithms for Maximum Inner Product Search via Extreme Order Statistics

  2021cites this paper
• Efficient High-Dimensional Kernel k-Means++ with Random Projection

  2021influential citation
• Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics

  2020influential citation
• Fast Approximate CoSimRanks via Random Projections

  2020cites this paper
• Towards robust neural networks via orthogonal diversity

  2020influential citation
• Ensemble learning of high dimension datasets

  2020cites this paper
• Structure from Randomness in Halfspace Learning with the Zero-One Loss

  2020influential citation
• Improving Random Projections With Extra Vectors to Approximate Inner Products

  2020cites this paper
• University of Birmingham Structure from Randomness in Halfspace Learning with the Zero-One Loss

  2020influential citation
• Fast Approximate All Pairwise CoSimRanks via Random Projection

  2020cites this paper
• Random Projection in the Presence of Concept Drift in Supervised Environments

  2020cites this paper
• Contextual Bandits with Random Projection

  2019cites this paper
• University of Birmingham Compressive learning of multi-layer perceptrons

  2019cites this paper
• Compressive Hyperspherical Energy Minimization

  2019cites this paper
• Regularizing Neural Networks via Minimizing Hyperspherical Energy

  2019cites this paper
• Compressive Learning of Multi-layer Perceptrons: An Error Analysis

  2019cites this paper
• Tighter Guarantees for the Compressive Multi-layer Perceptron

  2018cites this paper
• Extreme Graph Kernels for Online Learning on a Memory Budget

  2018cites this paper
• Data-independent Random Projections from the feature-space of the homogeneous polynomial kernel

  2018cites this paper
• University of Birmingham Tighter guarantees for the compressive multi-layer perceptron

  2018cites this paper
• Scalable FRaC Variants: Anomaly Detection for Precision Medicine

  2017cites this paper
• Linear dimensionality reduction in linear time: Johnson-Lindenstrauss-type guarantees for random subspace

  2017cites this paper
• CBRAP: Contextual Bandits with RAndom Projection

  2017influential citation
• Similarity preserving compressions of high dimensional sparse data

  2016influential citation
• Real-Valued Embeddings and Sketches for Fast Distance and Similarity Estimation

  2016cites this paper