Timezone: »

 
Poster
Orthogonal Random Features
Felix Xinnan Yu · Ananda Theertha Suresh · Krzysztof M Choromanski · Daniel Holtmann-Rice · Sanjiv Kumar

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #184
in Wednesday Posters »
We present an intriguing discovery related to Random Fourier Features: replacing multiplication by a random Gaussian matrix with multiplication by a properly scaled random orthogonal matrix significantly decreases kernel approximation error. We call this technique Orthogonal Random Features (ORF), and provide theoretical and empirical justification for its effectiveness. Motivated by the discovery, we further propose Structured Orthogonal Random Features (SORF), which uses a class of structured discrete orthogonal matrices to speed up the computation. The method reduces the time cost from $\mathcal{O}(d^2)$ to $\mathcal{O}(d \log d)$, where $d$ is the data dimensionality, with almost no compromise in kernel approximation quality compared to ORF. Experiments on several datasets verify the effectiveness of ORF and SORF over the existing methods. We also provide discussions on using the same type of discrete orthogonal structure for a broader range of kernels and applications.
Keywords: Kernel Methods · Large Scale Learning and Big Data · Nonlinear Dimension Reduction and Manifold Learning
[ PDF] 

Author Information

Felix Xinnan Yu (Google Research)
Ananda Theertha Suresh (University of California, San Diego)
Krzysztof M Choromanski (Google Brain Robotics)
Daniel Holtmann-Rice (Google Inc)
Sanjiv Kumar (Google)

More from the Same Authors