Lecture notes: Efficient approximation of kernel functions
  These lecture notes endeavour to collect in one place the mathematical
background required to understand the properties of kernels in general and the
Random Fourier Features approximation of Rahimi and Recht (NIPS 2007) in
particular. We briefly motivate the use of kernels in Machine Learning with the
example of the support vector machine. We discuss positive definite and
conditionally negative definite kernels in some detail. After a brief
discussion of Hilbert spaces, including the Reproducing Kernel Hilbert Space
construction, we present Mercer's theorem. We discuss the Random Fourier
Features technique and then present, with proofs, scalar and matrix
concentration results that help us estimate the error incurred by the
technique. These notes are the transcription of 10 lectures given at IIT Delhi
between January and April 2020.
