Description

Homework 3
1. This question is about the inner product representation of bounded linear functions.
(a) Consider the function Est : Rn×n → R defined by Est(X) = xst, where X = [xij]ni,j=1, i.e., Est obtains the (s,t)-entry of a matrix. Find a matrix A ∈ Rn×n such that Est(X) = hA,Xi for all X ∈ Rn×n.
(b) Consider the trace function Tr : Rn×n → R defined by Tr(X) = , where X = [xij]ni,j=1. Find a matrix A ∈ Rn×n such that Tr(X) = hA,Xi for all X ∈ Rn×n.
(c) Given a ∈ Rn, consider the quadratic function f : Rn → R defined by f(x) = |ha,xi|2 for any x ∈ Rn. Obviously f is NOT linear. Nevertheless, we can convert it to a linear function on the “lifted” matrix xxT ∈ Rn×n. More precisely, there exists a linear function F : Rn×n → R satisfying f(x) = F(xxT). Find the inner product representation of F (i.e., find A ∈ Rn×n such that f(x) = F(xxT) = hA,xxTi.) (This “lifting” technique is quite useful in, e.g., imaging and signal processing, machine learning.)
2. Let V be a Hilbert space. Let S1 and S2 be two hyperplanes in V defined by
S1 = {x ∈ V | ha1,xi = b1}, S2 = {x ∈ V | ha2,xi = b2}.
Let y ∈ V be given. We consider the projection of y onto S1 ∩ S2, i.e., the solution of
. (1)
x
(a) Prove that S1 ∩ S2 is a plane, i.e., if x,z ∈ S1 ∩ S2, then (1 + t)z − tx ∈ S1 ∩ S2 for any t ∈ R. (b) Prove that z is a solution of (1) if and only if z ∈ S1 ∩ S2 and
hz − y,z − xi = 0, ∀x ∈ S1 ∩ S2. (2)
(c) Find an explicit solution of (1).
(d) Prove the solution found in part (c) is unique.
3. Let be given with xi ∈ Rn and yi ∈ R. Assume N < n, and xi, i = 1,2,…,N, are linearly independent. Consider the ridge regression
N minnX(ha,xii − yi)2 + λkak22,
a∈R i=1
where λ ∈ R is a regularization parameter, and we set the bias b = 0 for simplicity.
(a) Prove that the solution must be in the form of a for some c = [c1,c2,…,cN]T ∈ RN.
(Hint: Similar to the proof of the representer theorem.)
(b) Re-express the minimization in terms of c ∈ RN, which has fewer unknowns than the original formulation.
1