PaperlayerView exact revision on arXiv

Source-linked AI summary

Orthogonal Random Features

Felix X. Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel Holtmann-Rice, Sanjiv Kumar

arXiv:1610.09072v1cs.LGstat.ML

TL;DR

Kernel approximation seeks scalable alternatives to computationally expensive nonlinear kernel methods. The paper introduces ORF by imposing orthogonality on random features and SORF using structured orthogonal matrices. ORF lowers Gaussian-kernel approximation error, while SORF substantially reduces computation with almost identical approximation quality to ORF.

  • Problem

    Kernel methods are computationally expensive for large datasets, while random-feature approximation faces transformation costs O(Dd) and often requires D larger than d for low error.

  • Method

    The paper replaces random Gaussian transformations with properly scaled random orthogonal matrices in ORF, then uses binary diagonal and Walsh-Hadamard products in SORF.

  • Results

    ORF achieves significantly lower Gaussian-kernel approximation error than RFF, while SORF has almost identical MSE to ORF and fast computation O(D log d).

  • Takeaways & Limitations

    Structured orthogonal features provide nearly ORF-level kernel approximation quality with substantially lower computation and memory cost.

  • Takeaways & Limitations

    Tight variance and concentration guarantees for SORF comparable to ORF remain an open question.

Abstract

from arXiv · show

We present an intriguing discovery related to Random Fourier Features: in Gaussian kernel approximation, replacing the random Gaussian matrix 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 this behavior. Motivated by this 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 applications.

1 Introduction

Kernel approximation makes nonlinear kernel methods scalable by mapping inputs into features whose dot products approximate the kernel. This paper addresses approximation quality and computational cost by introducing orthogonal and structured orthogonal random features.

  • Kernel methods are computationally expensive for large datasets, motivating scalable kernel approximation.
  • Random Fourier Features approximate smooth, shift-invariant kernels through Monte Carlo sampling from the kernel’s Fourier density.
  • The transformation matrix W determines how closely the estimated kernel converges to the actual kernel.
  • The transformation Wx costs O(Dd) time and space, and low approximation error often requires D larger than d.
  • ORF reduces kernel approximation error by enforcing orthogonality on W, while SORF uses structured orthogonal matrices for faster computation.

2 Related Works

Prior work develops nonlinear random features and structured matrices for kernel approximation, while this paper focuses on Gaussian kernels within the RFF framework. It proposes ORF and SORF as more effective alternatives to RFF, with SORF emphasizing both lower approximation error and efficiency.

  • Gaussian-kernel approximation: Gaussian-kernel approximation in this paper follows the extensively studied Random Fourier Features framework.RFF is presented as the paper’s central baseline for Gaussian kernels.
  • Random-feature sequences: Deterministic or data-dependent sequence design has been explored to improve Monte Carlo convergence or produce more compact random-feature maps.Earlier work includes low-displacement rank sequences and data-dependent sequence optimization.
  • Structured matrices: Structured randomness can slightly reduce kernel-approximation accuracy while enabling faster FFT-like computation and substantial model compression.Structured matrices have also been applied to dimensionality reduction, binary embedding, and deep neural networks.
  • Space and time costs: SORF has O(D) degrees of freedom and can use O(1) extra space through in-place computation with fixed random seeds.The comparison assumes D ≥ d.
  • Proposed methods: SORF and ORF are proposed as more effective than RFF, with SORF specifically achieving lower approximation error and better efficiency than RFF.The paper directs Table 1 to compare the space and time costs of these techniques.

3 Orthogonal Random Features

Orthogonal Random Features replaces independent Gaussian transformations with properly scaled random orthogonal matrices, preserving unbiased Gaussian-kernel estimation while reducing variance. The analysis explains this improvement and shows that the benefit is especially strong for nearby data points and remains substantial in practical dimensionality settings.

  • ORF construction: ORF constructs its transformation as SQ, where Q is uniformly random orthogonal and S supplies independent χ-distributed row norms.This scaling matches the row-norm distribution of the original Gaussian matrix, unlike an unscaled orthogonal replacement.
  • Theoretical properties: KORF is an unbiased estimator of the Gaussian kernel and has lower variance than conventional RFF.The paper establishes unbiasedness theoretically and compares the resulting estimator directly with RFF.
  • Variance reduction: The variance ratio Var(KORF)/Var(KRFF) is always below 1 when D = d and d is large, with the strongest gains at small z = ||x − y||/σ.As z → 0 and d → ∞, the ratio is roughly z^2, indicating an especially large relative error reduction for nearby points.
  • Empirical validation: For d ≥ 32, empirical variance ratios are close to the d = ∞ result, and ORF′ remains nearly unbiased even at relatively small d.The simulations use 20,000 random-matrix choices per curve and show close agreement with the asymptotic behavior.
  • Practical regime: With σ set to the mean distance of 50th-nearest neighbors, datasets concentrate mostly in z < 2, where ORF provides substantial variance reduction.This regime corresponds to preserving kernel values especially well for close data points and retaining local dataset structure.
  • Feature dimensionality: When D > d, the method applies independently generated transformations multiple times and concatenates the resulting random features.The main variance analysis first assumes D ≤ d; larger feature counts are handled by independent blocks.

4 Structured Orthogonal Random Features

SORF replaces expensive random orthogonal matrices with structured Walsh-Hadamard constructions, retaining nearly ORF-level kernel approximation quality while reducing computation and memory costs.

  • Structured Orthogonal Random Features: For fixed D, SORF and ORF have overlapping Gaussian-kernel MSE curves, while ORF′ has similar MSE to ORF empirically.The ORF′ analysis reports low variance for large d and variance close to its d = ∞ ratio when d ≥ 32.
  • Structured Orthogonal Random Features: SORF replaces ORF's random orthogonal matrix with products of binary diagonal and Walsh-Hadamard matrices.The diagonal matrices use Rademacher sign flips, while the normalized Walsh-Hadamard matrix supplies the structured orthogonal transform.
  • Structured Orthogonal Random Features: O(d log d) computation and almost no extra memory make SORF suitable for high-dimensional data.Sign flipping and Walsh-Hadamard transformations can be implemented efficiently in place.
  • Structured Orthogonal Random Features: When d > 32, SORF's kernel estimation is almost unbiased and its variance ratio converges to ORF's.The paper reports almost identical kernel approximation quality between SORF and ORF at larger dimensions.
  • Structured Orthogonal Random Features: SORF provides competitive classification accuracy while being faster than RFF and ORF by O(d/ log d).On gisette with D = 2d, the reported speedup is 10 times compared with RFF and ORF.

5 Experiments

Experiments across six datasets show that orthogonal features improve kernel approximation, while SORF preserves ORF-quality error with substantially better efficiency and competitive classification accuracy.

  • Kernel Approximation: SORF ≃ ORF < QMC < RFF < other fast kernel approximations in kernel approximation MSE for fixed D.DigitalNet is the best-performing quasi-Monte Carlo method but remains less accurate than ORF and SORF.
  • Kernel Approximation: SORF has almost identical MSE to ORF, while circulant and FastFood approximations have higher MSE.The experiments compare these methods on Gaussian-kernel approximation across six datasets.
  • Kernel Approximation: SORF combines better computational efficiency with higher kernel approximation quality than other methods.The reported comparison concerns the methods evaluated at fixed transformation count D.
  • Classification: SORF is competitive with or better than RFF in classification accuracy while reducing time and space costs.The classification experiments use a linear SVM with different kernel approximation techniques.
  • Simplifying SORF: Reducing SORF from three Hadamard-Diagonal blocks to two gives similar performance, whereas one block causes large error.This simplification result is reported on the mnist dataset.

6 Analysis and General Applicability of the Hadamard-Diagonal Structure

SORF is nearly unbiased for Gaussian-kernel approximation at large dimensionality, while its structured Hadamard-Diagonal construction supports fast computation and near-orthogonal projections. The same structure is also discussed for applications beyond kernel approximation.

  • For large d, SORF is an unbiased estimator of the Gaussian kernel.
  • SORF uses products of binary diagonal and Walsh-Hadamard matrices to replace random orthogonal matrices.
  • SORF's near-orthogonal structure yields projections that behave near-independently through a vector with independent sub-Gaussian elements.
  • The transformed representation has rows with norm ||z||2 and pairwise inner products bounded by t||z||2 with high probability.
  • The Hadamard-Diagonal structure is also empirically applied to angle estimation with a non-smooth sign(·) map.

7 Conclusions

The paper concludes that orthogonality can substantially reduce Gaussian-kernel approximation error, while structured orthogonal matrices lower computation and memory costs. It also indicates broader applicability and possible generalization to other kernels.

  • Imposing orthogonality on the transformation matrix greatly reduces Random Fourier Features' Gaussian-kernel approximation MSE.
  • Structured orthogonal matrices provide substantially lower computation and memory costs than unstructured orthogonal transformations.
  • Hadamard-Diagonal blocks can generally replace random Gaussian matrices in a broader range of applications.
  • The method can be generalized to general shift-invariant and polynomial kernels using Schoenberg's characterization.

A.3 Proof of Lemma 2

The proof of Lemma 2 analyzes cosine-product expectations for projections onto orthogonal directions, using rotational invariance, Taylor expansions, and Gaussian and chi-distribution moments.

  • Lemma 4 supplies convexity-based bounds that are combined to obtain the lemma's stated result.
  • The proof reduces projections onto random orthogonal vectors to projections onto the first coordinates of a uniformly spherical vector by rotation invariance.
  • The argument expands cosine terms in Taylor series and evaluates their moments using chi and Gaussian distributions.
  • A uniformly distributed point on a sphere is constructed by normalizing independent standard Gaussian coordinates.

Appendix B Proof of Theorem 2

The proof of Theorem 2 bounds the bias and variance of the orthogonal-feature estimator. It uses spherical symmetry and Taylor-series moment calculations to establish the required expectations and variance bound.

  • The proof first separates the analysis into a bias bound and a variance bound.
  • By rotational symmetry, the vector z can be aligned with the first coordinate, reducing wTz to a scalar multiple of the first spherical coordinate.
  • Spherical coordinates are represented by normalized independent Gaussian variables to calculate the relevant expectations.
  • Taylor expansion of cosine reduces the calculation to expectations of individual terms and their moments.
  • For the variance, the proof evaluates cosine products involving two orthogonal projections and applies the preceding bounds.

Appendix C Proof of Theorem 3

The proof of Theorem 3 uses Stein-type arguments to relate structured Hadamard-diagonal transformations to Gaussian behavior and establish the kernel-bias bound. It then invokes Bochner’s theorem for the Gaussian kernel.

  • Lemma 7: Lemma 7 bounds the difference between expectations under a Gaussian variable and a normalized Rademacher sum for functions with bounded value and derivative.The proof uses Stein’s lemma, Taylor approximation, independence, and zero-mean Rademacher variables.
  • Lemma 7: The proof combines the intermediate expectation and moment bounds to obtain the lemma’s result.The supplied proof states that the equations are combined and the bound on the second moment of f is substituted.
  • Theorem 3: For the structured transformation, √dHD1HD2 is shown to behave like a Gaussian matrix when computing the bias.The argument relates expectations under the structured transformation to expectations under a Gaussian distribution.
  • Theorem 3: Theorem 3 follows from Bochner’s theorem and the fact that the cosine function satisfies the lemma’s requirements.The theorem applies to dHD1HD2 itself; the third component HD3 is unnecessary for bounding the bias.

Appendix D Proof of Theorem 4

Theorem 4 is proved by applying Hanson-Wright concentration to the structured Hadamard-diagonal construction. The proof controls the relevant Frobenius and spectral norms using orthogonality, norm preservation, and a bound on the maximum coordinate.

  • Theorem 4: Theorem 4 uses the Hanson-Wright inequality for quadratic forms of independent subGaussian variables.The proof identifies the diagonal entries of D2 as independent subGaussian components and invokes the inequality for concentration.
  • Theorem 4: The proof represents the structured vectors through v = HD3z and u = HD2v = Hdiag(v)vec(D2).This representation makes the quadratic-form structure explicit for applying Hanson-Wright.
  • Theorem 4: Orthogonality of the Hadamard matrices and norm preservation imply that every row of the transformed matrix has norm ||z||2.The proof separately establishes row orthogonality by analyzing off-diagonal inner products.
  • Theorem 4: The Frobenius norm is bounded using diagonal scaling and Hadamard norm preservation, while the spectral norm is bounded using rotation invariance and the maximum diagonal magnitude.The proof uses bounds involving ||v||2 and ||v||∞ for the respective norms.
  • Experiments: On a 16384-dimensional natural-image dataset, HDHDHD achieves higher recall and lower angular MSE than the compared hashing methods.The comparison includes random projection LSH, Circulant Binary Embedding, and Kronecker Binary Embedding.
  • Theorem 4: With probability ≥1−2de−dϵ2/2, ||v||∞≤ϵ||z||2, and choosing ϵ = (t/d)1/3 yields the theorem.The maximum-coordinate bound follows from McDiarmid’s inequality before applying Hanson-Wright.
Loading 1610.09072v1…