# Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2017.

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

- [Solving and Learning Nonlinear PDEs with Gaussian Processes](https://mlsanity.com/paper/2103.12959/) (2021)
- [A Mathematical Guide to Operator Learning](https://mlsanity.com/paper/2312.14688/) (2023)
- [Kernel Methods are Competitive for Operator Learning](https://mlsanity.com/paper/2304.13202/) (2023)
- [Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian Processes](https://mlsanity.com/paper/2304.01294/) (2023)
- [Learning elliptic partial differential equations with randomized linear algebra](https://mlsanity.com/paper/2102.00491/) (2021)
- [Elliptic PDE learning is provably data-efficient](https://mlsanity.com/paper/2302.12888/) (2023)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Error Analysis of Kernel/GP Methods for Nonlinear and Parametric PDEs](https://mlsanity.com/paper/2305.04962/) (2023)
- [Bayesian Numerical Methods for Nonlinear Partial Differential Equations](https://mlsanity.com/paper/2104.12587/) (2021)
- [Scalable Gaussian-process regression and variable selection using Vecchia approximations](https://mlsanity.com/paper/2202.12981/) (2022)
- [Data-Efficient Kernel Methods for Learning Differential Equations and Their Solution Operators: Algorithms and Error Analysis](https://mlsanity.com/paper/2503.01036/) (2025)
- [Operator Learning at Machine Precision](https://mlsanity.com/paper/2511.19980/) (2025)
- [Operator learning for hyperbolic partial differential equations](https://mlsanity.com/paper/2312.17489/) (2023)
- [Gaussian Process Hydrodynamics](https://mlsanity.com/paper/2209.10707/) (2022)
- [Variational sparse inverse Cholesky approximation for latent Gaussian processes via double Kullback-Leibler minimization](https://mlsanity.com/paper/2301.13303/) (2023)
- [Gaussian Measures Conditioned on Nonlinear Observations: Consistency, MAP Estimators, and Simulation](https://mlsanity.com/paper/2405.13149/) (2024)
- [Iterative Methods for Full-Scale Gaussian Process Approximations for Large Spatial Data](https://mlsanity.com/paper/2405.14492/) (2024)
- [Learning non-Gaussian spatial distributions via Bayesian transport maps with parametric shrinkage](https://mlsanity.com/paper/2409.19208/) (2024)
- [Black Box Probabilistic Numerics](https://mlsanity.com/paper/2106.13718/) (2021)
- [Vecchia-Inducing-Points Full-Scale Approximations for Gaussian Processes](https://mlsanity.com/paper/2507.05064/) (2025)
- [Novel Pivoted Cholesky Decompositions for Efficient Gaussian Process Inference](https://mlsanity.com/paper/2507.20678/) (2025)
- [Extrapolating from Regularised Solutions for Solving Ill-Conditioned Linear Systems in Machine Learning](https://mlsanity.com/paper/2606.30328/) (2026)
- [Adaptive multi-resolution Gaussian processes: Scalable exact inference with naturally data-sparse covariance matrices](https://mlsanity.com/paper/2609.30348/) (2026)

## Abstract (arXiv)

Dense kernel matrices Theta ∈ ℝN × N obtained from point evaluations of a covariance function G at locations  xi 1 ≤ i ≤ N subset ℝd arise in statistics, machine learning, and numerical analysis. For covariance functions that are Green's functions of elliptic boundary value problems and homogeneously-distributed sampling points, we show how to identify a subset S subset  1 , dots , N 2, with # S = O ( N log (N) logd ( N /ε ) ), such that the zero fill-in incomplete Cholesky factorisation of the sparse matrix Thetaij 1( i, j ) ∈ S is an ε-approximation of Theta. This factorisation can provably be obtained in complexity O ( N log( N ) logd( N /ε) ) in space and O ( N log2( N ) log2d( N /ε) ) in time, improving upon the state of the art for general elliptic operators; we further present numerical evidence that d can be taken to be the intrinsic dimension of the data set rather than that of the ambient space. The algorithm only needs to know the spatial configuration of the xi and does not require an analytic representation of G. Furthermore, this factorization straightforwardly provides an approximate sparse PCA with optimal rate of convergence in the operator norm. Hence, by using only subsampling and the incomplete Cholesky factorization, we obtain, at nearly linear complexity, the compression, inversion and approximate PCA of a large class of covariance matrices. By inverting the order of the Cholesky factorization we also obtain a solver for elliptic PDE with complexity O ( N logd( N /ε) ) in space and O ( N log2d( N /ε) ) in time, improving upon the state of the art for general elliptic operators.