Statistical Seminar: Every Monday at 2:00 pm.
Time: 2:00 pm – 3:15 pm
Date: 19th of April 2021
Place: Visio
Bharath SRIPERUMBUDUR (Pennsylvania State University) – “Johnson & Lindenstrauss meet Hilbert at a Kernel”

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 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)

Organizers:
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Zoltan SZABO (CMAP)
Sponsors:
CREST-CMAP