# Large-Scale Learning with Fourier Features and Tensor Decompositions

arXiv: https://arxiv.org/abs/2109.01545 · HTML: https://mlsanity.com/paper/2109.01545/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 48 references that are in the map.
- First posted on arXiv 3 Sep 2021.

## Builds on (most cited first, 17 of 17)

- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Scalable Variational Gaussian Process Classification](https://mlsanity.com/paper/1411.2005/) (2014)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Deep Convolutional Networks as shallow Gaussian Processes](https://mlsanity.com/paper/1808.05587/) (2018)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Hilbert Space Methods for Reduced-Rank Gaussian Process Regression](https://mlsanity.com/paper/1401.5508/) (2014)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017)
- [Sparse Gaussian Processes with Spherical Harmonic Features](https://mlsanity.com/paper/2006.16649/) (2020)
- [Compressing Recurrent Neural Network with Tensor Train](https://mlsanity.com/paper/1705.08052/) (2017)
- [Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition](https://mlsanity.com/paper/1710.07324/) (2017)
- [Gaussian Quadrature for Kernel Features](https://mlsanity.com/paper/1709.02605/) (2017)
- [Parallelized Tensor Train Learning of Polynomial Classifiers](https://mlsanity.com/paper/1612.06505/) (2016)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)

## Built on by (most cited first, 14 of 14)

- [Privacy-preserving machine learning with tensor networks](https://mlsanity.com/paper/2202.12319/) (2022)
- [Quantized Fourier and Polynomial Features for more Expressive Tensor Network Models](https://mlsanity.com/paper/2309.05436/) (2023)
- [Position: Tensor Networks are a Valuable Asset for Green AI](https://mlsanity.com/paper/2205.12961/) (2022)
- [Tensor Network-Constrained Kernel Machines as Gaussian Processes](https://mlsanity.com/paper/2403.19500/) (2024)
- [Interpretable Bayesian Tensor Network Kernel Machines with Automatic Rank and Feature Selection](https://mlsanity.com/paper/2507.11136/) (2025)
- [Tensor Network Based Feature Learning Model](https://mlsanity.com/paper/2512.02547/) (2025)
- [Projecting basis functions with tensor networks for Gaussian process regression](https://mlsanity.com/paper/2310.20630/) (2023)
- [Efficient Patient Fine-Tuned Seizure Detection with a Tensor Kernel Machine](https://mlsanity.com/paper/2408.00437/) (2024)
- [A Guide to Bayesian Optimization in Bioprocess Engineering](https://mlsanity.com/paper/2508.10642/) (2025)
- [Laplace Approximation for Bayesian Tensor Network Kernel Machines](https://mlsanity.com/paper/2604.26673/) (2026)
- [Constructing structured tensor priors for Bayesian inverse problems](https://mlsanity.com/paper/2406.17597/) (2024)
- [Tensor network square root Kalman filter for online Gaussian process regression](https://mlsanity.com/paper/2409.03276/) (2024)
- [Adapting Tensor Kernel Machines to Enable Efficient Transfer Learning for Seizure Detection](https://mlsanity.com/paper/2512.02626/) (2025)
- [Tensor Network Kernel Machines: A JAX Framework for Machine Learning and Nonlinear System Identification](https://mlsanity.com/paper/2608.07043/) (2026)

## Abstract (arXiv)

Random Fourier features provide a way to tackle large-scale machine learning problems with kernel methods. Their slow Monte Carlo convergence rate has motivated the research of deterministic Fourier features whose approximation error can decrease exponentially in the number of basis functions. However, due to their tensor product extension to multiple dimensions, these methods suffer heavily from the curse of dimensionality, limiting their applicability to one, two or three-dimensional scenarios. In our approach we overcome said curse of dimensionality by exploiting the tensor product structure of deterministic Fourier features, which enables us to represent the model parameters as a low-rank tensor decomposition. We derive a monotonically converging block coordinate descent algorithm with linear complexity in both the sample size and the dimensionality of the inputs for a regularized squared loss function, allowing to learn a parsimonious model in decomposed form using deterministic Fourier features. We demonstrate by means of numerical experiments how our low-rank tensor approach obtains the same performance of the corresponding nonparametric model, consistently outperforming random Fourier features.