# Random embeddings and hashing

See also matrix factorisations, and discuss random projections and their role in motivating compressed sensing etc.

Cover’s Theorem (Cove65)

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.

I am especially interested in random embeddings for kernel approximation.

Over at compressed sensing we mention some other random projection results, such as the Johnson-Lindenstrauss lemma, and these ideas are closely related, in the probabilistic setting, to concentration inequalities.

Landweber etc al (LaLP16) have an example of a converse result about your continuous random embeddings. (TBD)