A Caltech Library Service

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

Schäfer, F. and Sullivan, T. J. and Owhadi, H. (2017) Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Dense kernel matrices Θ∈R^(N×N) obtained from point evaluations of a covariance function G at locations {x_i}1≤i≤N arise in statistics, machine learning, and numerical analysis. For covariance functions that are Green's functions elliptic boundary value problems and approximately equally spaced sampling points, we show how to identify a subset S⊂{1,…,N}×{1,…,N}, with #S=O(Nlog(N)log^d(N/ϵ)), such that the zero fill-in block-incomplete Cholesky decomposition of Θ_(i,j)1_((i,j)∈S) is an ϵ-approximation of Θ. This block-factorisation can provably be obtained in O(Nlog^2(N)(log(1/ϵ)+log^2(N))^(4d+1)) complexity in time. Numerical evidence further suggests that element-wise Cholesky decomposition with the same ordering constitutes an O(Nlog^2(N)log^(2d)(N/ϵ)) solver. The algorithm only needs to know the spatial configuration of the x_i and does not require an analytic representation of G. Furthermore, an approximate PCA with optimal rate of convergence in the operator norm can be easily read off from this decomposition. Hence, by using only subsampling and the incomplete Cholesky decomposition, 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 decomposition we also obtain a near-linear-time solver for elliptic PDEs.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Owhadi, H.0000-0002-5677-1600
Additional Information:(Submitted on 7 Jun 2017) FS and HO gratefully acknowledge support by the Air Force Office of Scientific Research and the DARPA EQUiPS Program under award number FA9550-16-1-0054 (Computational Information Games). TJS is supported by the Free University of Berlin within the Excellence Initiative of the German Research Foundation (DFG). We would like to thank Chris Oates and Peter Schröder for helpful discussions.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0054
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
Subject Keywords:Cholesky decomposition, covariance function, gamblet transform, kernel matrix, sparsity, principal component analysis
Classification Code:2010 MSC: 65F30 (42C40, 65F50, 65N55, 65N75, 60G42, 68Q25, 68W40)
Record Number:CaltechAUTHORS:20170710-083743909
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78882
Deposited By: Ruth Sustaita
Deposited On:10 Jul 2017 16:52
Last Modified:03 Oct 2019 18:13

Repository Staff Only: item control page