The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
Abstract
We examine a class of embeddings based on structured random matrices with orthogonal rows which can be applied in many machine learning applications including dimensionality reduction and kernel approximation. For both the Johnson-Lindenstrauss transform and the angular kernel, we show that we can select matrices yielding guaranteed improved performance in accuracy and/or speed compared to earlier methods. We introduce matrices with complex entries which give significant further accuracy improvement. We provide geometric and Markov chain-based perspectives to help understand the benefits, and empirical results which suggest that the approach is helpful in a wider range of applications.
Cite
Text
Choromanski et al. "The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings." Neural Information Processing Systems, 2017.Markdown
[Choromanski et al. "The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/choromanski2017neurips-unreasonable/)BibTeX
@inproceedings{choromanski2017neurips-unreasonable,
title = {{The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings}},
author = {Choromanski, Krzysztof M and Rowland, Mark and Weller, Adrian},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {219-228},
url = {https://mlanthology.org/neurips/2017/choromanski2017neurips-unreasonable/}
}