Quantized Random Projections and Non-Linear Estimation of Cosine Similarity
Random projections constitute a simple, yet effective technique for dimensionality reduction with applications in learning and search problems. In the present paper, we consider the problem of estimating cosine similarities when the projected data undergo scalar quantization to $b$ bits. We here argue that the maximum likelihood estimator (MLE) is a principled approach to deal with the non-linearity resulting from quantization, and subsequently study its computational and statistical properties. A specific focus is on the on the trade-off between bit depth and the number of projections given a fixed budget of bits for storage or transmission. Along the way, we also touch upon the existence of a qualitative counterpart to the Johnson-Lindenstrauss lemma in the presence of quantization.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionLEMMAQuantizationSimilar Papers 제목 키워드 기반
Simple strategies for recovering inner products from coarsely quantized random projections
Random projections have been increasingly adopted for a diverse set of tasks in machine learning involving dimensionality reduction. One specific line of research on this topic has investigated the use of quantization su…
Data CompressionDimensionality ReductionQuantizationSign Stable Random Projections for Large-Scale Learning
We study the use of "sign $\alpha$-stable random projections" (where $0<\alpha\leq 2$) for building basic data processing tools in the context of large-scale machine learning applications (e.g., classification, regressio…
ARCClusteringGeneral ClassificationRandom Projections with Asymmetric Quantization
The method of random projection has been a popular tool for data compression, similarity search, and machine learning. In many practical scenarios, applying quantization on randomly projected data could be very helpful t…
Data CompressionQuantizationNode Similarities under Random Projections: Limits and Pathological Cases
Random Projections have been widely used to generate embeddings for various graph learning tasks due to their computational efficiency. The majority of applications have been justified through the Johnson-Lindenstrauss L…
Computational EfficiencyGraph LearningLEMMABreaking the waves: asymmetric random periodic features for low-bitrate kernel machines
Many signal processing and machine learning applications are built from evaluating a kernel on pairs of signals, e.g. to assess the similarity of an incoming query to a database of known signals. This nonlinear evaluatio…
Quantization