Homework 2
1. Let (V,k · k) be a normed vector space.
(a) Prove that, for all x,y ∈ V ,
|kxk − kyk| ≤ kx − yk.
(b) Let {xk}k∈N be a convergent sequence in V with limit x ∈ V . Prove that
.
(Hint: Use part (a).)
(c) Let {x(k)}k∈N be a sequence in V and x,y ∈ V . Prove that, if
x(k) → x, and x(k) → y,
then x = y. (In other words, the limit of the same sequence in a normed vector space is unique.)
2. Let V be a vector space, and h·,·i be an inner product on V . Use the definition of inner product to prove the following.
(a) Prove that h0,xi = hx,0i = 0 for any x ∈ V . Here 0 is the zero vector in V .
(b) Prove that the second condition
hαx1 + βx2,yi = αhx1,yi + βhx2,yi, ∀ x1,x2,y ∈ V ,α,β ∈ R
is equivalent to
hx1 + x2,yi = hx1,yi + hx2,yi and hαx,yi = αhx,yi, ∀ x1,x2,x,y ∈ V, α ∈ R.
3. Rm×n is a vector space over R. Show that hA,Bi = trace(ATB) for A,B ∈ Rm×n is an inner product on Rm×n. Here trace(·) is the trace of a matrix, i.e., the sum of all diagonal entries.
4. Consider the polynomial kernel K(x,y) = (xTy + 1)2 for x,y ∈ R2. Find an explicit feature map φ : R2 → R6 satisfying hφ(x),φ(y)i = K(x,y), where the inner product the standard inner product in R6.
5. (You don’t need to do anything for this question.) A good Matlab code and demonstration of kernel K-means can be found at http://www.dcs.gla.ac.uk/~srogers/firstcourseml/matlab/chapter6/kernelkmeans.html Read the code. Run the code in Matlab, if possible, to see how kernel K-means works for nonlinear data.
1
