The Library
Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
Tools
Tools
Tools
Schäfer, Florian, Sullivan, T. J. and Owhadi, Houman (2021) Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity. Multiscale Modeling & Simulation, 19 (2). pp. 688-730. doi:10.1137/19M129526X ISSN 1540-3459.
|
PDF
WRAP-compression-inversion-approximate-PCA-dense-kernel-matrices-near-linear-computational-complexity-Sullivan-2021.pdf - Published Version - Requires a PDF viewer. Download (6Mb) | Preview |
Official URL: https://doi.org/10.1137/19M129526X
Abstract
Dense kernel matrices $\Theta \in \mathbb{R}^{N \times N}$ obtained from point evaluations of a covariance function $G$ at locations $\{ x_{i} \}_{1 \leq i \leq N} \subset \mathbb{R}^{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 = \mathcal{O} ( N \log (N) \log^{d} ( N /\epsilon ) )$, such that the zero fill-in incomplete Cholesky factorization of the sparse matrix $\Theta_{ij} \mathbf{1}_{( i, j ) \in S}$ is an $\epsilon$-approximation of $\Theta$. This factorization can provably be obtained in complexity $\mathcal{O} ( N \log( N ) \log^{d}( N /\epsilon) )$ in space and $\mathcal{O} ( N \log^{2}( N ) \log^{2d}( N /\epsilon) )$ 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_{i}$ 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 $\mathcal{O} ( N \log^{d}( N /\epsilon) )$ in space and $\mathcal{O} ( N \log^{2d}( N /\epsilon) )$ in time, improving upon the state of the art for general elliptic operators.
| Item Type: | Journal Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Analysis of covariance, Sparse matrices, Decomposition (Mathematics), Algebras, Linear | |||||||||||||||
| Journal or Publication Title: | Multiscale Modeling & Simulation | |||||||||||||||
| Publisher: | Society for Industrial and Applied Mathematics | |||||||||||||||
| ISSN: | 1540-3459 | |||||||||||||||
| Official Date: | 2021 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 19 | |||||||||||||||
| Number: | 2 | |||||||||||||||
| Page Range: | pp. 688-730 | |||||||||||||||
| DOI: | 10.1137/19M129526X | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Reuse Statement (publisher, data, author rights): | First Published in Multiscale Modeling & Simulation in Vol. 19, No. 2, pp. 688--730, published by the Society for Industrial and Applied Mathematics (SIAM) Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | |||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
| Date of first compliant deposit: | 27 April 2021 | |||||||||||||||
| Date of first compliant Open Access: | 27 April 2021 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
