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
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.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2016-09-28

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

Highlights - Most important sentences from the article

2018-10-29

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

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
PDF

Highlights - Most important sentences from the article

2018-09-28

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

Highlights - Most important sentences from the article

2019-03-06

In this work, we consider two types of large-scale quadratic matrix equations: Continuous-time algeb… show more
PDF

Highlights - Most important sentences from the article

2018-12-18

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

Highlights - Most important sentences from the article

2019-01-23

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

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
PDF

Highlights - Most important sentences from the article

2017-06-09

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

Highlights - Most important sentences from the article

2019-02-05

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

Highlights - Most important sentences from the article

2019-03-06

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

Highlights - Most important sentences from the article

2014-02-16

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

Highlights - Most important sentences from the article

2018-08-14

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

Highlights - Most important sentences from the article

2018-10-09

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

Highlights - Most important sentences from the article

2019-06-11

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

Highlights - Most important sentences from the article