The Random Projection Method

By Santosh Srinivas Vempala. 2005

567 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Scaling provable adversarial defenses (2018, methodology): “Note that for an `2 norm bounded adversarial perturbation, the dual norm is also an `2 norm, so we can use traditional random projections [Vempala, 2005].”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “The body of work on the JL transform is by now so extensive that only a book may survey it properly [29].”
Random Projection, Margins, Kernels, and Feature-Selection (2005, methodology): “The use of Johnson-Lindenstrauss type results in the context of learning was first proposed by Arriaga and Vempala [AV99], and a number of uses of random projection in learning are discussed in [Vem04].”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, background): “One approach to quantization is with random projections (Charikar, 2002; Vempala, 2005; Li & Li, 2019).”
Very sparse random projections (2006, methodology): “See the monograph by Vempala [43] for further references.”
Sliced Wasserstein Distance for Learning Gaussian Mixture Models (2017, background): “We note that the idea of characterizing a high-dimensional distribution via its random projections has been studied in various work before [51, 25].”
Learning Convex Bodies is Hard (2009, background): “, [12, 8]), where one is given samples generated according to (say) the Gaussian distribution and each sample is labeled “positive” or “negative” depending on whether it belongs to the body.”
Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning (2019, methodology): “According to the Johnson-Lindenstrauss lemma (Vempala, 2005), this transformation preserves the inner product between g and the rows of C † and C T with high probability if k is not too small.”
Simple and deterministic matrix sketching (2012, background): “The second approach is to randomly combine matrix rows [25][28][27][21].”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, background): “, see the book [27] and references therein).”
An Analysis of Random Projection for Changeable and Privacy-Preserving Biometric Verification (2010, methodology): “Vempala [30] also introduced an RP method for mapping high-dimensional binary vectors to low-dimensional ones with the Hamming distance between the binary vectors approximately preserved.”
A More Powerful Two-Sample Test in High Dimensions using Random Projection (2011, methodology): “distributions. From this geometric point of view, it is natural to exploit the fact that random projections can simultaneously reduce dimension and approximately preserve length with high probability [16]. If a projection matrix P⊤ k ∈ R k×p is used to project data from Rp to Rk, and the classical H”
A sparse Johnson: Lindenstrauss transform (2010, unknown): “…applications including nearest-neighbor search [2, 19], compressed sensing [11], data stream computations [5], computational geometry [13], numerical linear algebra [14,17,26,28], machine learning [8,33], graph sparsiﬁcation [30], and more; see the monograph [32] for further applications.”
No Training Required: Exploring Random Encoders for Sentence Classification (2019, methodology): “2 Random features in machine learning are often used for low-rank approximation (Vempala, 2005), as per the Johnson-Lindenstrauss lemma; exploiting the useful properties of random matrices (Mehta, 2004).”
Coding for Random Projections (2013, methodology): “1 Introduction The method of random projections has become popular for larg e-scale machine learning applications such as classification, regression, matrix factorization, sing ular value decomposition, near neighbor search, bioinformatics, and more [22, 6, 1, 3, 10, 18, 11, 24, 7, 16, 25].”
RAPTT: An Exact Two-Sample Test in High Dimensions Using Random Projections (2014, background): “ the results that the random projection of a vector can reduce its dimension and the norm of the projected vector can be made arbitrarily close to that of the original vector with high 4 probability (Vempala, 2004). We project the high dimensional data into a lower dimensional space through a p × k ”