# Random embeddings and hashing

December 6, 2016 — December 1, 2020

See also matrix factorisations, for some extra ideas on why random projections have a role in motivating compressed sensing, randomised regressions etc.

## 1 Random projections

I am especially interested in random projections for kernel approximation.

Occasionally we might use non-linear projections to *increase* the dimensionality of our data in the hope of making a non-linear regression approximately linear, which dates back to (Cover 1965).

### 1.1 Low-dimensional embeddings

Over at compressed sensing we mention some useful tools for these problems, such as the Johnson-Lindenstrauss lemma.

See low-d projections.

## 2 Locality-sensitive hashing

TBD

## 3 Nonlinear embeddings

Cover’s Theorem (Cover 1965):

It was shown that, for a random set of linear inequalities in \(d\) unknowns, the expected number of extreme inequalities, which are necessary and sufficient to imply the entire set, tends to \(2d\) as the number of consistent inequalities tends to infinity, thus bounding the expected necessary storage capacity for linear decision algorithms in separable problems. The results, even those dealing with randomly positioned points, have been combinatorial in nature, and have been essentially independent of the configuration of the set of points in the space.

TBC

## 4 References

*Journal of Computer and System Sciences*, Special Issue on PODS 2001,.

*SIAM Journal on Computing*.

*arXiv:1411.0306 [Cs, Stat]*.

*47th Annual IEEE Symposium on Foundations of Computer Science, 2006. FOCS ’06*.

*arXiv:1306.1547 [Cs]*.

*arXiv:1501.01062 [Cs]*.

*arXiv:1507.05910 [Cs, Stat]*.

*Constructive Approximation*.

*Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*. KDD ’01.

*Proceedings of The 8th Asian Conference on Machine Learning*.

*IEEE Transactions on Information Theory*.

*IEEE Transactions on Audio, Speech, and Language Processing*.

*arXiv:1703.00864 [Stat]*.

*arXiv:1902.06687 [Cs, Eess, Stat]*.

*IEEE Transactions on Electronic Computers*.

*Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence*. UAI’00.

*Random Structures & Algorithms*.

*Proceedings of the Twentieth Annual Symposium on Computational Geometry*. SCG ’04.

*Advances in Neural Information Processing Systems 28*. NIPS’15.

*Applied and Computational Harmonic Analysis*.

*arXiv:1609.06347 [Nlin, Stat]*.

*Advances in Neural Information Processing Systems*.

*Machine Learning*.

*arXiv:2108.04172 [Cs, Math, Stat]*.

*IEEE Transactions on Signal Processing*.

*arXiv:1610.00494 [Cs, Stat]*.

*arXiv:2007.07383 [Physics, Stat]*.

*The Annals of Statistics*.

*arXiv:1701.08290 [Stat]*.

*arXiv:2007.10683 [Cs, Math]*.

*Journal of the ACM*.

*Artificial Intelligence and Statistics*.

*Bernoulli*.

*arXiv:1612.04111 [Cs, Stat]*.

*Advances in Neural Information Processing Systems 29*.

*IEEE Transactions on Pattern Analysis and Machine Intelligence*.

*American Mathematical Monthly*.

*Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*. KDD ’06.

*Advances in Neural Information Processing Systems*.

*Advances in Neural Information Processing Systems 29*.

*arXiv:1511.09433 [Cs, Math, Stat]*.

*Advances in Neural Information Processing Systems*.

*2008 46th Annual Allerton Conference on Communication, Control, and Computing*.

*Transactions on Machine Learning Research*.

*Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery*.

*Advances in Neural Information Processing Systems 29*.

*arXiv:2105.08875 [Cs, Math, Stat]*.

*arXiv:1409.2344 [Math, Stat]*.

*Proceedings of the 26th Annual International Conference on Machine Learning*. ICML ’09.

*Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval*. SIGIR ’10.