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

## Reviews

There are no reviews yet.