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.
Introduction
In modern machine learning, high-dimensional data often needs to be projected into lower-dimensional spaces or mapped into higher-dimensional "feature spaces" to facilitate kernel methods. For years, the standard approach was to use matrices filled with independent, identically distributed (i.i.d.) Gaussian random variables. While robust, these "unstructured" choices are computationally expensive and statistically sub-optimal.
This paper demonstrates that structure is not merely a shortcut for speed; it is a mathematical advantage. By utilizing Random Ortho-Matrices (ROMs), researchers can achieve embeddings that are both faster to compute and more accurate than standard i.i.d. Gaussian methods.
The Problem with Unstructured Randomness
Two fundamental techniques in ML—the Johnson-Lindenstrauss Transform (JLT) for dimensionality reduction and Random Feature Maps for kernel approximation—traditionally rely on random Gaussian matrices. These matrices require $O(nm)$ time for multiplication and often exhibit high variance.
Previous attempts to use structured matrices (like the Fast Walsh-Hadamard Transform) aimed to reduce complexity to $O(n \log n)$, but it was widely assumed that this structure was a "necessary evil" that might degrade statistical accuracy. This research flips that script, proving that structure actually improves accuracy.
Methodology: Structured Orthogonality
The authors introduce a family of Random Ortho-Matrices (ROMs) in two primary forms:
- $G_{ort}$: A Gaussian matrix conditioned such that its rows are perfectly orthogonal.
- SD-product matrices: Highly structured matrices formed by taking a fixed, fast-to-compute orthogonal matrix $S$ (e.g., a Hadamard matrix) and multiplying it by a random diagonal matrix $D$ (typically Rademacher variables). These can be stacked into $k$ blocks: $M = SD_k \dots SD_1$.
A key innovation is the S-Hybrid variant, which utilizes complex numbers (roots of unity) on the diagonal of the final block, significantly reducing estimation error.
Geometric Insights
Geometric perspective of the projection onto the plane defined by vectors x and y. Source, p. 7
The superiority of ROMs stems from how they distribute randomness. By forcing rows to be orthogonal, the "randomness" is spread more evenly across the space. This prevents the "clumping" inherent in i.i.d. matrices, where random rows might accidentally align, leading to redundant information and higher Mean Squared Error (MSE). The authors use Markov chain theory to show that just three blocks ($k=3$) of Hadamard-Rademacher products are sufficient to "mix" and approach the performance of perfectly random orthogonal matrices.
Empirical Results
The theoretical proofs were validated across several benchmarks, including the g50c, LETTER, and USPS datasets. The results consistently showed that structured orthogonal matrices outperform their unstructured counterparts.
Key findings include:
- Guaranteed Accuracy: The Orthogonal JLT (OJLT) has strictly smaller MSE than the standard unstructured JLT.
- Computational Speedup: Hadamard-based ROMs allow for embeddings in $O(n \log n)$ time, a massive practical win for high-dimensional data.
- The "Complex" Advantage: The S-Hybrid method, by allowing complex diagonal elements, can effectively halve the MSE of the estimator compared to real-valued versions without increasing parameter count.
Conclusion and Future Work
While ROMs offer significant benefits, the authors note that deterministic row selection in structured matrices could potentially be exploited by adversarial data; sub-sampling without replacement is recommended for safety. Future work may extend these theoretical guarantees to a wider class of Pointwise Nonlinear Gaussian (PNG) kernels beyond the angular kernel explored here.
Summary updated