2015 ImprovedBoundsontheDotProductun

• (Kaban, 2015) ⇒ Ata Kaban. (2015). “Improved Bounds on the Dot Product under Random Projection and Random Sign Projection.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783364

Subject Headings: Random Projection.

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Improved+Bounds+on+the+Dot+Product+under+Random+Projection+and+Random+Sign+Projection
• http://dl.acm.org/citation.cfm?id=2783258.2783364&preflayout=flat#citedby

Quotes

Author Keywords

• Compressive classification; dot product preservation; general; margin preservation; random projection

Abstract

Dot product is a key building block in a number of data mining algorithms from classification, regression, correlation clustering, to information retrieval and many others. When data is high dimensional, the use of random projections may serve as a universal dimensionality reduction method that provides both low distortion guarantees and computational savings. Yet, contrary to the optimal guarantees that are known on the preservation of the Euclidean distance cf. the Johnson-Lindenstrauss lemma, the existing guarantees on the dot product under random projection are loose and incomplete in the current data mining and machine learning literature. Some recent literature even suggested that the dot product may not be preserved when the angle between the original vectors is obtuse.

In this paper we provide improved bounds on the dot product under random projection that matches the optimal bounds on the Euclidean distance. As a corollary, we elucidate the impact of the angle between the original vectors on the relative distortion of the dot product under random projection, and we show that the obtuse vs. acute angles behave symmetrically in the same way. In a further corollary we make a link to sign random projection, where we generalise earlier results. Numerical simulations confirm our theoretical results. Finally we give an application of our results to bounding the generalisation error of compressive linear classifiers under the margin loss.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 ImprovedBoundsontheDotProductun	Ata Kaban			Improved Bounds on the Dot Product under Random Projection and Random Sign Projection				10.1145/2783258.2783364		2015