FOUNDATIONS OF ML: LINEAR ALGEBRA EXERCISES
1. What is the exercise sheet for?
The language of contemporary machine learning is applied linear algebra – we talk about feature vectors, dimensionality reduction of data by projections and so on. These are mathematical expressions borrowed from linear algebra. You will reinforce your learning of the fundamental concepts in linear algebra by working through this exercise sheet.
2. Linear dependence
(1) Isthevectorv2R3 inthespanofthesetfw ;w ;w g?
123 01010101
@xA @1A @0A @0A v= y ;w1= 1 ;w2= 1 andw3= 0 ?
z111
Solution For v to be in the span of fw1; w2; w3g, there exists a1; a2; a3 2 R
suchthatv=aw +aw +aw 112233
010101010 1
@xA @1A @0A @0A @ a1
y =a1 1 +a2 1 +a3 0 = a1+a2
z 1 1 1 a1+a2+a3
Finding a1; a2; a3 in terms of x; y; z is straightforward.
(2) The singular value decomposition of a matrix A expresses it as 3 matrices A = UVT where U and V are orthogonal matrices non-zero matrix elements of are along the diagonal. An example
A
a product of
and the only follows where the entries of the matrix (A)ij could indicate the preference of user i for movie
j:
0111 ppp
22 010p1B111C pp B00C
:
0 0 1 0 0 1 1T pp
□
@01001App3000060230
B 0CB CB C
C:
010
| {z }| {z }| {z }@q2 2A
21
A U |300{zp0}
3 VT
(a) Let the columns of U be denoted u1, u2 and u3, and those of V denoted vi, i = 1; : : : ; 5. Show that these singular vectors fuig and fvig form orthonormal sets.
1
00101 =@ 2 0 2A@0 p2000AB
623 22 B111C
11 ppp
11 10010 00100B0p00pC
2
FOUNDATIONS OF ML: LINEAR ALGEBRA EXERCISES
Solution. Straightforward algebra: for example,
0B 1 1C > 0B 1 1C 0B 1 1C > 0B 1 1C
pp pp 22 22
>11>11 uu=@p A@p A=0;uu=@p A@p A=1:
13221122 00 00
The rest should be checked in the same way. □ (b) Calculate UUT , UT U, VVT and VT V.
Solution. The matrix elements of the matrix product A = UU> are aij = (A)ij = X(U)ik(U>)kj = X(U)ik(U)jk;
kk
where the last expression is the dot product of rows i and j of U. Similarly, X(U>)ik(U)kj = X(U)ki(U)kj;
kk
which is the dot product of columns i and j of U. Hence, each of the products gives the identity matrix.
□
(c) Express original basis vectors eb 2 R3 and eb 2 R5 as linear combinations 23
of these singular vectors. In other words, for
01 0B01C @0A B0C
eb2 ≜ 1 and eb3 ≜ B@ 1 CA 00
0
Find eb =(2)u +(2)u +(2)u and eb =(3)v ++(3)v . 2112233311 55
Solution. Similar to the first problem. Use the orthogonality of the fuig
and fv g basis: i
XX
v>eb =v> (3)v ++(3)v = (3)(v>v )= (3) =(3): i 3 i 1 1 5 5 j i j j ij i
jj
Therefore, we can project eb along each column v of V: 031i
pp 01001
B1 011 0C Bp p p C
22
ppp B60230C
623
(3) B1 1 1 C
=ebV=B0p 00pC=p;0;p;p;0
B22C
111
>11
i3
Bq p C623
@20010A B33C
i
□
|{z} |{z} |{z} |{z} |{z} v1 v2 v3 v4 v5
FOUNDATIONS OF ML: LINEAR ALGEBRA EXERCISES 3
31
The answer f(A) is a matrix.
□
3. Matrix polynomials
(1)ForA= 4 2 ,andf(x)=x2+3x10,calculatef(A).
3A is a matrix.
The number 10 in f (x) has to be multiplied by the 2 2 identity matrix to
make it a matrix.
22 6 9 7
Hint: Verify A2 =
(2) Solve for x: f(x)=x2 +3x10=0: Call the solutions x and x .
.
Solution. f(x)=(x+5)(x2), so x1 =5 and x2 =2.
(3) Define the matrices B1 = Ax1I and B2 = Ax2I where I is the 22 identity matrix. Evaluate the determinants of B1 and B2 They should both be zero.
(4) The columns of B1 and B2 must thus (from the vanishing determinant condition)
be linearly dependent. Find numbers v1 and v2 such that v1 (B1)col 1 + v2 (B1)col 2 = 0:
Similarly, find numbers w1 and w2 such that
w1 (B2)col 1 + w2 (B2)col 2 = 0:
(5) Partial answer: v1 = 2, v2 = 1.
Solution. The point of this exercise is to illustrate the fact that these coeffi-
□
cients are the components of the eigenvector corresponding to x = 5:
A v1 = 4 2 2 =(5) 2
1
tors x and eigenvalues .
(1) Find the eigenvalues and eigenvectors of
v2 311 1
4. Computing eigenvalues and eigenvectors
The eigenvalue problem Ax = x is the following: find, for a matrix A, the eigenvec-
0@ 2 2 3 1A A= 0 13
2 2 4
STEP I: Compute the characteristic polynomial of A and find its roots. Verify:
A()=det(AI)=3 2 +10+10
and note that A() = (2 10)( + 1). What are the eigenvalues of A?
12
4
FOUNDATIONS OF ML: LINEAR ALGEBRA EXERCISES
STEP II:
For each eigenvalue i, i = 1;2;3, we need to compute the corresponding eigenvectors. Find x; y; z so that
0@ 2 2 3 1A 0@ x 1A 0@ x 1A 013 y=iy: 224z z
Solution: The 3 eigenvectors are:
0B p 1C 0B p 1C 0 1
3 104 3 4+ 10 @0A 11
p@2 3 A;p @2 3 A;3
(1)
(2)
For a symmetric matrix A = AT 2 Rdd, let the eigenvectors be ui, correspond- ing to eigenvalues i for i = 1; : : : ; d. Let the diagonal matrix have entries ()ii = i, and the d d-matrix U has columns (u1; u2; : : : ; ud). Show that AU = U.
Solution. The point of this exercise is to learn how to combine all the eigenvalue-eigenvector equations into one matrix equation, and to note that comes last.
□
If a matrix A = VDV1 where D is a diagonal matrix with diagonal entries (D)ii = di and the n-th power of A, is written in terms of another matrix C thus
An = VCV1 what are the matrix elements of C?
Solution. Write out the matrix product An in terms of the factors of A: An =(VDV1)(VDV1)(VDV1):
Since matrix multiplication is associative A(BC) = (AB)C, place the brackets around every V1V pair. Since V1V = I, this results in
An =VDIDIIDV1 =VDnV1:
Therefore C = dn is a diagonal matrix whose diagonal entries contains the
1+10 p 101 p
1+ 10 101
5. Matrix products and eigenvector basis
2
ij iij
n-th power of the diagonal entries of D.
For a matrix X:
1 2 1 3
6. Singular Value Decomposition
X=; 2131
□
FOUNDATIONS OF ML: LINEAR ALGEBRA EXERCISES 5
the singular value decomposition (SVD) of X is written as X = UVT where 0q1
U =
(1)
(2)
(3)
(4)
(5)
!!
B 3 2 3 3 7 C
p B1111C
3115
ppp
14
11 22BqpC
p p p p p p
11 21000B42237C
; = and V = B 2
0300 p
C
0 pp@qpA
225
2 2 21 3 22212
213
15 6 . The negative off- 6 15
37
pp 337
Calculate C = XXT . You will find that C =
diagonal elements of C capture the observation that for most cases, the elements of each column of X are of opposite sign.
Note. This last remark is a nod to the fact that if X were a matrix of data points, with either a row or a column containing the deviations of the features from the feature average (which it isn’t, in this example), then one could get the covariance matrix of features as XX> or X>X.
□
Compute the eigenvalues of C. Solve for the equation that sets the characteristic polynomial of C to zero. In other words,
calculate C(x) := det(C xI) and find the values x = x1; x2 such that C(x1) = C(x2) = 0.
Hint: You will find that C(x) = x2 30x + 189, and you should use the observation that 189 = 21 9.
Solution. The eigenvalues of C are 21;9. The singular values of X are pp
21; 9.
How do the eigenvalues x1;2 relate to the diagonal entries of ?
□
Solution. The eigenvalues of C are 21;9. The singular values of X are pp
□
and find the nullspace for each, i.e., find v1 and v2 such that Divi = 0. These vis are the eigenvectors of C. Normalise them and compare with U.
Solution. The sum or difference of each row of Di is zero. Hence the eigen- vectors will be (1; 1)> or (1; 1)>.
□
You might want the help of some software for this, e.g., numpy.linalg.eig. You
can check that
21; 9.
Verify that the matrices D = C x I are proportional to
ii 11 11
1 1 and 1 1 ;
01 B 5 0 7 5 C
XTX=@0 5 1 5A; 7 1 10 6
5 5 6 10
6
FOUNDATIONS OF ML: LINEAR ALGEBRA EXERCISES
which should have 4 eigenvalues. Two of them should be the same as those of C. What about the other two? Verify that the un-normalised eigenvectors of XT X are
(3;1;4;4)T;(1;3;2;2)T;(1;1;0;1)T;(7;1;5;0)T;
and that normalising them will yield the columns of V. 7. Low-rank approximation
We can construct the rank-1 approximation X~ 1 of X by setting X~ 1 = u11v1T . (1) Using (from the previous exercise)
1p1
u=p(1;1)T;= 21;v=p (3;1;4;4)T 111
2 42 confirm that the rank-1 approximation is !
3 1 2 2 X~=22 :
1 3122 22
In particular, note that the rows are not independent.
(2) Compute the rank one approximation to C as C~ = X~ X~T. This should be
1 1
:
Given X~ 1, why is this not a surprise? What are its eigenvalues and eigenvectors?
proportional to
(3) Verify that X~ T1 X~ 1 is
B 9 3 6 6 C
1 1
01
111
@3 1 22A: B2222 C
6 2 8 8 6 2 8 8
What would you expect its eigenvalues to be? Check that all the rows and columns are are multiples of ( 3 ; 1 ; 2; 2). Relate this observation to the
22
eigenvalue spectrum and the definition of rank.