A0283
Title: Johnson & Lindenstrauss meet Hilbert at a Kernel
Authors: Bharath Sriperumbudur - Pennsylvania State University (United States) [presenting]
Abstract: Johnson-Lindenstrauss (J-L) lemma is a famous result about the almost-isometric embeddability of a finite set in Euclidean space into a Euclidean space of a much smaller dimension. This result has applications in fast dimensionality reduction through random projections and has led to many randomized algorithms that achieve fast matrix computations. In this work, we extend this idea of random projections to an infinite-dimensional reproducing kernel Hilbert space (RKHS), wherein a finite-dimensional representation is obtained for each function in the RKHS by projecting it along certain random directions. Using this finite-dimensional representation, we obtain a J-L type lemma by showing that certain weighted distances and inner products are preserved. We show the random projection in RKHS to be closely related to Gaussian sketching and discuss its implications in speeding up the kernel algorithms. (Joint work with Samory Kpotufe, Columbia University)
