Data mining - Homework 1: Dimensionality reduction,

Johnson-Lindenstrauss Transform and angular kernel

October 6, 2018

1 Problem 1: Dot-product kernel & dimensionality reduction (30

points)

Consider an estimator of the dot-product kernel obtained as follows. Let : Rn ! Rm (for m < n)

be dened as:

(x) =

1

p

m

Sx; (1)

where S 2 Rmn is a matrix with entries taken independently and uniformly at random from the

two-element set f