The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
This provides a more efficient and accurate solution for machine learning practitioners dealing with high-dimensional data, though it appears incremental as it builds on existing embedding methods.
The paper tackles the problem of improving performance in dimensionality reduction and kernel approximation by introducing structured random orthogonal embeddings with complex entries, achieving guaranteed improvements in accuracy and/or speed compared to earlier methods for applications like the Johnson-Lindenstrauss transform and angular kernel.
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.