Abstract

Scalable approximation algorithms for kernel matrices

George Biros
University of Texas at Austin

I will present a parallel algorithm for approximating an N-by-N kernel matrix. The factorization and evaluation cost 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.

I will present a review of ASKIT (approximate skeletonization kernel independent treecode), a method that we recently developed in my group for approximating kernel matrices and their inverses. The main feature of ASKIT is its dependence on the local intrinsic dimension of the dataset as opposed to the dimension of the ambient space of the dataset. We will compare ASKIT with the Nystrom method and discuss its application to learning problems in high-dimensions. As a highlight, we will report results for Gaussian kernel matrices with 100 million points in 64 dimensions, and for eight million points in 1000 dimensions.