
CMUCS04110
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS04110
Fast Kernel MatrixVector Multiplication
with Application to Gaussian Process Learning
Alexander Gray
February 2004
CMUCS04110.ps
CMUCS04110.pdf
Keywords: Gaussian processes, kernel matrix, matrixvector
multiplication, fast algorithms
A number of core computational problems in machine learning, both old
and new, can be cast as a matrixvector multiplication between a
kernel matrix or classprobability matrix and a vector of weights.
This arises prominently, for example, in the kernel estimation methods
of nonparametric statistics, many common probabilistic graphical
models, and the more recent kernel machines. After highlighting the
existence of this computational problem in several wellknown machine
learning methods, we focus on a solution for one specific example for
clarity, Gaussian process (GP) prediction  one whose applicability
has been particularly hindered by this computational barrier. We
demonstrate the application of a recent Nbody approach developed
specifically for statistical problems, employing adaptive
computational geometry and finitedifference approximation.
This core algorithm reduces the O(N^2) matrixvector
multiplications within GP learning to O(N), making the resulting
overall learning algorithm O(N). GP learning for N = 1 million points
is demonstrated.
9 pages
