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

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).

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.

I am especially interested in random embeddings for kernel approximation.

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

## References

*Journal of Computer and System Sciences*, Special Issue on PODS 2001, 66 (4): 671β87.

*SIAM Journal on Computing*39 (1): 302β22.

*arXiv:1411.0306 [Cs, Stat]*, November.

*47th Annual IEEE Symposium on Foundations of Computer Science, 2006. FOCS β06*, 51:459β68.

*arXiv:1306.1547 [Cs]*, June.

*arXiv:1501.01062 [Cs]*, January.

*arXiv:1507.05910 [Cs, Stat]*, July.

*arXiv Preprint arXiv:1502.06800*.

*Constructive Approximation*28 (3): 253β63.

*Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, 245β50. KDD β01. New York, NY, USA: ACM.

*Proceedings of The 8th Asian Conference on Machine Learning*, 110β25.

*IEEE Transactions on Information Theory*52 (12): 5406β25.

*IEEE Transactions on Audio, Speech, and Language Processing*16 (5): 1015β28.

*arXiv:1703.00864 [Stat]*, March.

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

*IEEE Transactions on Electronic Computers*EC-14 (3): 326β34.

*Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence*, 143β51. UAIβ00. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

*Random Structures & Algorithms*22 (1): 60β65.

*Proceedings of the Twentieth Annual Symposium on Computational Geometry*, 253β62. SCG β04. New York, NY, USA: ACM.

*Advances in Neural Information Processing Systems 28*, 1414β22. NIPSβ15. Cambridge, MA, USA: MIT Press.

*Applied and Computational Harmonic Analysis*35 (1): 111β29.

*arXiv:1609.06347 [Nlin, Stat]*, September.

*Advances in Neural Information Processing Systems*, 473β80.

*Machine Learning*63 (1): 3β42.

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

*IEEE Transactions on Signal Processing*64 (13): 3444β57.

*arXiv:1610.00494 [Cs, Stat]*, October.

*arXiv:2007.07383 [Physics, Stat]*, July.

*The Annals of Statistics*21 (2): 867β89.

*arXiv:1701.08290 [Stat]*, January.

*arXiv:2007.10683 [Cs, Math]*, November.

*Journal of the ACM*61 (1): 1β23.

*Artificial Intelligence and Statistics*, 583β91. PMLR.

*Bernoulli*6 (1): 113β67.

*arXiv:1612.04111 [Cs, Stat]*, December.

*Advances in Neural Information Processing Systems 29*, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 1750β58. Curran Associates, Inc.

*IEEE Transactions on Pattern Analysis and Machine Intelligence*34 (6): 1092β1104.

*American Mathematical Monthly*123 (4): 392β97.

*Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, 287β96. KDD β06. New York, NY, USA: ACM.

*Advances in Neural Information Processing Systems*, 985β92.

*Advances in Neural Information Processing Systems 29*.

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

*Advances in Neural Information Processing Systems*, 1177β84. Curran Associates, Inc.

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

*Transactions on Machine Learning Research*, January.

*Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery*7 (2).

*Advances in Neural Information Processing Systems 29*, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 1298β1306. Curran Associates, Inc.

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

*arXiv:1409.2344 [Math, Stat]*, September.

*Proceedings of the 26th Annual International Conference on Machine Learning*, 1113β20. ICML β09. New York, NY, USA: ACM.

*Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval*, 18β25. SIGIR β10. New York, NY, USA: ACM.

## No comments yet. Why not leave one?