Orthogonal Random Features

• DOI: 10.48550/arxiv.1610.09072
• Publication Date: 2016-01-01
• Authors: Felix X. Yu; Ananda Theertha S...; Krzysztof Choroma...; Daniel Holtmann-Rice; Sanjiv Kumar
• Keywords: Kernel (algebra); Matrix (chemical analysis)

We present an intriguing discovery related to Random Fourier Features: in Gaussian kernel approximation, replacing the random matrix by a properly scaled orthogonal significantly decreases approximation error. call this technique Orthogonal Features (ORF), and provide theoretical empirical justification for behavior. Motivated discovery, we further propose Structured (SORF), which uses class of structured discrete matrices speed up computation. The method reduces time cost from $\mathcal{O}(d^2)$ $\mathcal{O}(d \log d)$, where $d$ is data dimensionality, with almost no compromise quality compared ORF. Experiments on several datasets verify effectiveness ORF SORF over existing methods. also discussions using same type structure broader range applications.