Papers › Compression, inversion, and approximate PCA of dense kernel matrices at near-linear...
Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
Florian Schäfer, T. J. Sullivan, Houman Owhadi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Dense kernel matrices Θ∈ℝ^(N ×N) obtained from point evaluations of a covariance function G at locations { xᵢ }_(1 ≤i ≤N) ⊂ℝᵈ 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 ⊂{ 1 , …, N }², with # S = O ( N log(N) logᵈ ( N /ϵ) ), such that the zero fill-in incomplete Cholesky factorisation of the sparse matrix Θᵢⱼ 1_(( i, j ) ∈S) is an ϵ-approximation of Θ. This factorisation can provably be obtained in complexity O ( N log( N ) logᵈ( N /ϵ) ) in space and O ( N log²( N ) log²ᵈ( 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 xᵢ 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 logᵈ( N /ϵ) ) in space and O ( N log²ᵈ( N /ϵ) ) in time, improving upon the state of the art for general elliptic operators.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections