# The Uniformly Rotated Mondrian Kernel

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 6 Feb 2025.

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

- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Mondrian Forests: Efficient Online Random Forests](https://mlsanity.com/paper/1406.2673/) (2014)
- [The Mondrian Kernel](https://mlsanity.com/paper/1606.05241/) (2016)
- [Random Tessellation Forests](https://mlsanity.com/paper/1906.05440/) (2019)
- [Stochastic geometry to generalize the Mondrian Process](https://mlsanity.com/paper/2002.00797/) (2020)
- [Inference with Mondrian Random Forests](https://mlsanity.com/paper/2310.09702/) (2023)
- [Revisiting Random Binning Features: Fast Convergence and Strong Parallelizability](https://mlsanity.com/paper/1809.05247/) (2018)
- [Minimax Rates for High-Dimensional Random Tessellation Forests](https://mlsanity.com/paper/2109.10541/) (2021)
- [The Mondrian Process for Machine Learning](https://mlsanity.com/paper/1507.05181/) (2015)
- [TrIM: Transformed Iterative Mondrian Forests for Gradient-based Dimension Reduction and High-Dimensional Regression](https://mlsanity.com/paper/2407.09964/) (2024)

## Abstract (arXiv)

Random feature maps are used to decrease the computational cost of kernel machines in large-scale problems. The Mondrian kernel is one such example of a fast random feature approximation of the Laplace kernel, generated by a computationally efficient hierarchical random partition of the input space known as the Mondrian process. In this work, we study a variation of this random feature map by applying a uniform random rotation to the input space before running the Mondrian process to approximate a kernel that is invariant under rotations. We obtain a closed-form expression for the isotropic kernel that is approximated, as well as a uniform convergence rate of the uniformly rotated Mondrian kernel to this limit. To this end, we utilize techniques from the theory of stationary random tessellations in stochastic geometry and prove a new result on the geometry of the typical cell of the superposition of uniformly rotated Mondrian tessellations. Finally, we test the empirical performance of this random feature map on both synthetic and real-world datasets, demonstrating its improved performance over the Mondrian kernel on a dataset that is debiased from the standard coordinate axes.