# Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 64 references that are in the map.
- First posted on arXiv 24 Dec 2022.

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

- [AUTM Flow: Atomic Unrestricted Time Machine for Monotonic Normalizing Flows](https://mlsanity.com/paper/2206.02102/) (2022)
- [Low-rank approximation in the Frobenius norm by column and row subset selection](https://mlsanity.com/paper/1908.06059/) (2019)

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

- [Posterior Covariance Structures in Gaussian Processes](https://mlsanity.com/paper/2408.07379/) (2024)
- [Preconditioned Additive Gaussian Processes with Fourier Acceleration](https://mlsanity.com/paper/2504.00480/) (2025)

## Abstract (arXiv)

A general, em rectangular kernel matrix may be defined as Kij = kappa(xi,yj) where kappa(x,y) is a kernel function and where X=xii=1m and Y=yii=1n are two sets of points. In this paper, we seek a low-rank approximation to a kernel matrix where the sets of points X and Y are large and are arbitrarily distributed, such as away from each other, ``intermingled'', identical, etc. Such rectangular kernel matrices may arise, for example, in Gaussian process regression where X corresponds to the training data and Y corresponds to the test data. In this case, the points are often high-dimensional. Since the point sets are large, we must exploit the fact that the matrix arises from a kernel function, and avoid forming the matrix, and thus ruling out most algebraic techniques. In particular, we seek methods that can scale linearly or nearly linear with respect to the size of data for a fixed approximation rank. The main idea in this paper is to em geometrically select appropriate subsets of points to construct a low rank approximation. An analysis in this paper guides how this selection should be performed.