The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Very sparse random projections
Abstract
There has been considerable interest in random projections, an approximate algorithm for estimating distances between pairs of points in a high-dimensional vector space. Let A in Rn x D be our n points in D dimensions. The method multiplies A by a random matrix R in RD x k, reducing the D dimensions down to just k for speeding up the computation. R typically consists of entries of standard normal N(0,1). It is well known that random projections preserve pairwise distances (in the expectation). Achlioptas proposed sparse random projections by replacing the N(0,1) entries in R with entries in -1,0,1 with probabilities 1/6, 2/3, 1/6, achieving a threefold speedup in processing time.We recommend using R of entries in -1,0,1 with probabilities 1/2√D, 1-1√D, 1/2√D for achieving a significant √D-fold speedup, with little loss in accuracy.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Modern Applied Statistics with S
Venables, W. N., & Ripley, B. D. (2002) · Statistics and Computing · doi:10.1007/978-0-387-21706-2 · Cited by 24,305
Foundations of statistical natural language processing
Manning, C. D., & Schütze, H. (1999) · Cited by 9,816
Term-weighting approaches in automatic text retrieval
Salton, G., & Buckley, C. (1988) · Information Processing & Management · doi:10.1016/0306-4573(88)90021-0 · Cited by 9,740
Newman (2005) · doi:10.1080/00107510500052444 · Cited by 5,749
On the self-similar nature of Ethernet traffic (extended version)
Leland, W. E., Taqqu, M. S., Willinger, W., & Wilson, D. V. (1994) · IEEE/ACM Transactions on Networking · doi:10.1109/90.282603 · Cited by 5,233
Ziegel, E. R., Lehmann, E. L., & Casella, G. (1999) · Technometrics · doi:10.2307/1270597 · Cited by 4,203
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Probability: Theory and Examples.
Prewitt, K., & Durrett, R. (1992) · Journal of the American Statistical Association · doi:10.2307/2290301 · Cited by 3,085
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
Random projection in dimensionality reduction: applications to image and text data
Bingham, E., & Mannila, H. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502546 · Cited by 1,274
An Introduction to Probability Theory and Its Applications, Volume II
Grubbs, F. E., & Feller, W. (1967) · Technometrics · doi:10.2307/1266435 · Cited by 1,097
Tackling the poor assumptions of naive bayes text classifiers
Rennie, J. D. M., Shih, L., Teevan, J. B., & Karger, D. R. (2003) · Cited by 977
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10073 · Cited by 932
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
Probability: Theory and Examples.
Durrett, R. (1993) · Biometrics · doi:10.2307/2532227 · Cited by 857
The space complexity of approximating the frequency moments
Alon, N., Matias, Y., & Szegedy, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237823 · Cited by 822
Random projection for high dimensional data clustering: a cluster ensemble approach
Fern, X. Z., & Brodley, C. E. (2003) · Cited by 595
Improving the retrieval of information from external sources
Dumais, S. T. (1991) · Behavior Research Methods, Instruments, & Computers · doi:10.3758/bf03203370 · Cited by 579
Liu, K., Kargupta, H., & Ryan, J. (2006) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2006.14 · Cited by 554
Vempala, S. (2005) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/065 · Cited by 538
Finding Motifs Using Random Projections
Buhler, J., & Tompa, M. (2002) · Journal of Computational Biology · doi:10.1089/10665270252935430 · Cited by 532
Text categorization with support vector machines
Joachims, T. (1997) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-5097 · Cited by 507
Text Categorization with Support Vector Machines. How to Represent Texts in Input Space?
Leopold, E., & Kindermann, J. (2002) · Machine Learning · doi:10.1023/a:1012491419635 · Cited by 403
Dimensionality reduction by random mapping: fast similarity computation for clustering
Kaski, S. (2002) · 1998 IEEE International Joint Conference on Neural Networks Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98CH36227) · doi:10.1109/ijcnn.1998.682302 · Cited by 388
An algorithmic theory of learning: Robust concepts and random projection
Arriaga, R. I., & Vempala, S. (2006) · Machine Learning · doi:10.1007/s10994-006-6265-7 · Cited by 316
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 299
On the Rate of Convergence in the Multivariate CLT
Gotze, F. (1991) · The Annals of Probability · doi:10.1214/aop/1176990448 · Cited by 288
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering
Ravichandran, D., Pantel, P., & Hovy, E. (2005) · Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics - ACL '05 · doi:10.3115/1219840.1219917 · Cited by 208
Experiments with random projections for machine learning
Fradkin, D., & Madigan, D. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956812 · Cited by 201
Face recognition experiments with random projection
Goel, N., Bebis, G., & Nefian, A. (2005) · SPIE Proceedings · doi:10.1117/12.605553 · Cited by 182
Sampling Techniques for Kernel Methods
Achlioptas, D., McSherry, F., & Schölkopf, B. (2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.003.0048 · Cited by 156
Lan, M., Tan, C.-L., Low, H.-B., & Sung, S.-Y. (2005) · International World Wide Web Conference (WWW) · doi:10.1145/1062745.1062854 · Cited by 138
Discovering unexpected information from your competitors' web sites
Liu, B., Ma, Y., & Yu, P. S. (2001) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502534 · Cited by 84
On scaling latent semantic indexing for large peer-to-peer systems
Tang, C., Dwarkadas, S., & Xu, Z. (2004) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1008992.1009014 · Cited by 71
Improving Random Projections Using Marginal Information
Li, P., Hastie, T. J., & Church, K. (2006) · Lecture notes in computer science · doi:10.1007/11776420_46 · Cited by 64
Self-citationLimit distributions of Studentized means
Chistyakov, G. P., & Götze, F. (2004) · The Annals of Probability · doi:10.1214/aop/1078415828 · Cited by 43
Cited by
Dictionary learning for integrative, multimodal and scalable single-cell analysis
Hao, Y., Stuart, T., Kowalski, M. H., Choudhary, S., Hoffman, P., Hartman, A., Srivastava, A., Molla, G., Madad, S., Fernandez-Granda, C., et al. (2024) · Nature Biotechnology · doi:10.1038/s41587-023-01767-y · Cited by 5,631
Real-Time Compressive Tracking
Zhang, K., Zhang, L., & Yang, M.-H. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33712-3_62 · Cited by 1,427
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 971
Gao, Y., Beijbom, O., Zhang, N., & Darrell, T. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.41 · Cited by 871
A Multi-View Deep Learning Approach for Cross Domain User Modeling in Recommendation Systems
Elkahky, A. M., Song, Y., & He, X. (2015) · Proceedings of the 24th International Conference on World Wide Web · doi:10.1145/2736277.2741667 · Cited by 704
Metadata
- Authors
- Li, P., Hastie, T. J., & Church, K. W.
- Venue
- Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2006-08-20
- Pages
- 287-296
- OpenAlex
- W2041836310
- Cited by
- 621
- References
- 40
- FWCI
- 6.72
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.