ML p(r)ior | Inv-ASKIT: A Parallel Fast Diret Solver for Kernel Matrices

### Inv-ASKIT: A Parallel Fast Diret Solver for Kernel Matrices

2016-02-03
1602.01376 | cs.NA
We present a parallel algorithm for computing the approximate factorization of an $N$-by-$N$ kernel matrix. Once this factorization has been constructed (with $N \log^2 N$ work), we can solve linear systems with this matrix with $N \log N$ work. Kernel matrices represent pairwise interactions of points in metric spaces. They appear in machine learning, approximation theory, and computational physics. Kernel matrices are typically dense (matrix multiplication scales quadratically with $N$) and ill-conditioned (solves can require 100s of Krylov iterations). Thus, fast algorithms for matrix multiplication and factorization are critical for scalability. Recently we introduced ASKIT, a new method for approximating a kernel matrix that resembles N-body methods. Here we introduce INV-ASKIT, a factorization scheme based on ASKIT. We describe the new method, derive complexity estimates, and conduct an empirical study of its accuracy and scalability. We report results on real-world datasets including "COVTYPE" ($0.5$M points in 54 dimensions), "SUSY" ($4.5$M points in 8 dimensions) and "MNIST" (2M points in 784 dimensions) using shared and distributed memory parallelism. In our largest run we approximately factorize a dense matrix of size 32M $\times$ 32M (generated from points in 64 dimensions) on 4,096 Sandy-Bridge cores. To our knowledge these results improve the state of the art by several orders of magnitude.

Highlights - Most important sentences from the article

# Related Articles

2016-09-28
1609.09154 | cs.DC

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank fact… show more

Highlights - Most important sentences from the article

2018-10-29
1810.12283 | cs.LG

Gaussian processes (GPs) with derivatives are useful in many applications, including Bayesian optimi… show more

Highlights - Most important sentences from the article

2018-07-05
1807.02125 | stat.ML

We introduce a kernel approximation strategy that enables computation of the Gaussian process log ma… show more

Highlights - Most important sentences from the article

2018-09-28
1809.11165 | cs.LG

Despite advances in scalable models, the inference tools used for Gaussian processes (GPs) have yet … show more

Highlights - Most important sentences from the article

2019-03-06
1903.02343 | math.NA

Highlights - Most important sentences from the article

2018-12-18
1812.07152 | cs.DC

We present MatRox, a novel model-based algorithm and implementation of Hierarchically Semi-Separable… show more

Highlights - Most important sentences from the article

2019-01-23
1901.07993 | cs.NA

We present three methods for distributed memory parallel inverse factorization of block-sparse Hermi… show more

Highlights - Most important sentences from the article

2015-10-26
1510.07363 | math.NA

Inversion of sparse matrices with standard direct solve schemes is robust, but computationally expen… show more

Highlights - Most important sentences from the article

2017-06-09
1706.02803 | cs.LG

Kernel $k$-means clustering can correctly identify and extract a far more varied collection of clust… show more

Highlights - Most important sentences from the article

2019-02-05
1902.01829 | cs.DS

Hierarchical matrices are space and time efficient representations of dense matrices that exploit th… show more

Highlights - Most important sentences from the article

2019-03-06
1903.02153 | cs.MS

This paper presents PBBFMM3D: a parallel black-box fast multipole method that accelerates kernel mat… show more

Highlights - Most important sentences from the article

2014-02-16
1402.3849 | cs.CV

Kernel-based clustering algorithms have the ability to capture the non-linear structure in real worl… show more

Highlights - Most important sentences from the article

2018-08-14
1808.04580 | cs.LG

The graph Laplacian is a standard tool in data science, machine learning, and image processing. The … show more

Highlights - Most important sentences from the article

2018-10-09
1810.04125 | cs.NA

We present new algorithms for the randomized construction of hierarchically semi-separable matrices,… show more

Highlights - Most important sentences from the article

2019-06-11
1906.04705 | cs.LG

Least-mean squares (LMS) solvers such as Linear / Ridge / Lasso-Regression, SVD and Elastic-Net not … show more

Highlights - Most important sentences from the article