An N log N Parallel Fast Direct Solver for Kernel Matrices
An N log N Parallel Fast Direct Solver for Kernel Matrices
Kernel matrices appear in machine learning and non-parametric statistics. Given N points in d dimensions and a kernel function that requires O(d) work to evaluate, we present an O(dN log N)-work algorithm for the approximate factorization of a regularized kernel matrix, a common computational bottleneck in the training phase of …