Database-friendly random projections

By Dimitris Achlioptas. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

982 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/d70c182a71aea05a145391b24d6bc3cdeede32a5

How researchers see this paper

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

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Texture Classification from Random Features (2012, methodology): “Previously, random projection has been studied as a general dimensionality reduction method for numerous clustering problems [37], [38], [39], [43] as well as for learning nonlinear manifolds [42], [48].”
Graph Sparsiﬁcation by Effective Resistances (neutral): “Lemma 6 (Achlioptas, [1] Thm. 1.1).”
Robust Face Recognition via Sparse Representation (2009, methodology): “Random projection has been previously studied as a general dimensionality-reduction method for numerous clustering problems [47], [48], [49], as well as for learning nonlinear manifolds [50], [51].”
Geometric Approximation Algorithms (2011, neutral): “This requires more involved proof [Ach01].”
Dimensionality Reduction via Matrix Factorization for Predictive Modeling from Large, Sparse Behavioral Data (2015, methodology): “Methods such as feature hashing (Shi et al. 2009) and random projections (Achlioptas 2001) provide ways of randomly selecting or combining the original data.”
Random projection in dimensionality reduction: applications to image and text data (2001, methodology): “We also presented experimental results of random projection using a sparsely populated random matrix introduced in [1].”
Leave‐Out Estimation of Variance Components (2018, positive): “We present conditions under which the limiting distribution simplifies to either a normal or a linear combination of central χ(2) random variables and discuss how these findings can be used to extend existing results on testing linear restrictions (Anatolyev, 2012; Chao et al., 2014; Cattaneo et al.”
Random Projections of Smooth Manifolds (2009, background): “In a recent paper [2], we have identified a fundamental connection between CS and the JohnsonLindenstrauss (JL) lemma [1, 15], which concerns the stable embedding of a finite point cloud under a random dimensionality-reducing projection.”
Compressed sensing and best k-term approximation (2008, background): “Namely, given any C > 1, this property will hold with constant C and ≤ 2e−βn with β = β(C) > 0; see [1] or the discussion in [2].”
Semantics-Preserving Parallelization of Stochastic Gradient Descent (2018, methodology): “This projection is inspired by the Johnson-Lindenstrauss (JL) lemma [8] and follows the treatment of Achlioptas [13].”
A Simple Proof of the Restricted Isometry Property for Random Matrices (2008, methodology): “The main point of this paper is to show that for certain random constructions of , the RIP follows in a simple way from the same concentration of measure inequalities for inner products that have been employed to prove the JL lemma [1, 13] and, in fact, can even be viewed as a straightforward conseq”
Brunn-Minkowski inequality (2000, methodology): “This requires a more involved proof [ Ach01 ].”
Simple and deterministic matrix sketching (2012, background): “Since R is a random projection matrix [24] B proj contains the m columns of A randomly projected from dimension n to dimension (cid:96) .”
Subspace clustering for high dimensional data: a review (2004, methodology): “With such datasets, random searching becomes a viable heuristic method and has been used with many of the aforementioned criteria [1; 12; 29].”
Random Projection, Margins, Kernels, and Feature-Selection (2005, background): “different forms of “random projection” are known to work (including some that are especially efficient to perform computationally, considered in [ Ach03 , AV99]).”