Linear Algebra Review
(Adapted from ’s slides)
Introduction to Machine Learning (CSC 311) Spring 2020
University of Toronto
Copyright By PowCoder代写 加微信 powcoder
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 1 / 28
Matrix Decomposition
We can decompose an integer into its prime factors, e.g., 12 = 2 ⇥ 2 ⇥ 3.
Similarly, matrices can be decomposed into product of other matrices.
A = Vdiag( )V 1
Examples are Eigendecomposition, SVD, Schur decomposition, LU
decomposition, . . . .
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 15 / 28
Eigenvectors
An eigenvector of a square matrix A is a nonzero vector v such that multiplication by A only changes the scale of v.
Av = v The scalar is known as the eigenvalue.
If v is an eigenvector of A, so is any rescaled vector sv. Moreover, sv still has the same eigenvalue. Thus, we constrain the eigenvector to be of unit length:
||v||2 = 1
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 16 / 28
Characteristic Polynomial(1)
Eigenvalue equation of matrix A.
Av = v v Av = 0 ( I A)v = 0
If nonzero solution for v exists, then it must be the case that: det( I A) = 0
Unpacking the determinant as a function of , we get: PA( )=det( I A)=1⇥ n +cn 1 ⇥ n 1 +…+c0
This is called the characterisitc polynomial of A.
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 17 / 28
Characteristic Polynomial(2)
If 1, 2,…, n are roots of the charactQeristic polynomial, they are eigenvaluePs of A and we have PA( ) = ni=1( i).
cn 1 = ni=1 i = tr(A). This means that the sum of eigenvalues equals to the trace of the matrix.
c0 = ( 1)n Qni=1 i = ( 1)ndet(A). The determinant is equal to the product of eigenvalues.
Roots might be complex. If a root has multiplicity of rj > 1 (This is called the algebraic dimension of eigenvalue), then the geometric dimension of eigenspace for that eigenvalue might be less than rj (or equal but never more). But for every eigenvalue, one eigenvector is guaranteed.
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 18 / 28
Consider the matrix:
A = 2 1 12
The characteristic polynomial is:
det( I A)=det 2 1 =3 4 + 2 =0
It has roots = 1 and = 3 which are the two eigenvalues of A.
We can then solve for eigenvectors using Av = v: v =1 = [1, 1]> and v =3 = [1, 1]>
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 19 / 28
Eigendecomposition
Suppose that n ⇥ n matrix A has n linearly independent eigenvectors {v(1), . . . , v(n)} with eigenvalues { 1, . . . , n}.
Concatenate eigenvectors (as columns) to form matrix V.
Concatenate eigenvalues to form vector = [ 1, . . . , n]>.
The eigendecomposition of A is given by:
AV = Vdiag( ) =) A = Vdiag( )V 1
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 20 / 28
Symmetric Matrices
Every symmetric (hermitian) matrix of dimension n has a set of (not necessarily unique) n orthogonal eigenvectors. Furthermore, all eigenvalues are real.
Every real symmetric matrix A can be decomposed into real-valued eigenvectors and eigenvalues:
Q is an orthogonal matrix of the eigenvectors of A, and ⇤ is a
diagonal matrix of eigenvalues.
We can think of A as scaling space by i in direction v(i).
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 21 / 28
Eigendecomposition is not Unique
Decomposition is not unique when two eigenvalues are the same.
By convention, order entries of ⇤ in descending order. Then, eigendecomposition is unique if all eigenvalues have multiplicity equal to one.
If any eigenvalue is zero, then the matrix is singular. Because if v is the corresponding eigenvector we have: Av = 0v = 0.
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 22 / 28
Positive Definite Matrix
If a symmetric matrix A has the property:
x>Ax > 0 for any nonzero vector x
Then A is called positive definite.
If the above inequality is not strict then A is called positive
semidefinite.
For positive (semi)definite matrices all eigenvalues are positive(non
negative).
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 23 / 28
Singular Value Decomposition (SVD)
If A is not square, eigendecomposition is undefined. SVD is a decomposition of the form A = UDV>. SVD is more general than eigendecomposition. Every real matrix has a SVD.
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 24 / 28
SVD Definition (1)
Write A as a product of three matrices: A = UDV>.
If A is m ⇥ n, then U is m ⇥ m, D is m ⇥ n, and V is n ⇥ n.
U and V are orthogonal matrices, and D is a diagonal matrix (not necessarily square).
Diagonal entries of D are called singular values of A. Columns of U are the left singular vectors, and columns of V
are the right singular vectors.
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 25 / 28
SVD Definition (2)
SVD can be interpreted in terms of eigendecompostion.
Left singular vectors of A are the eigenvectors of AA>.
Right singular vectors of A are the eigenvectors of A>A.
Nonzero singular values of A are square roots of eigenvalues of A>A and AA>.
Numbers on the diagonal of D are sorted largest to smallest and are non-negative (A>A and AA> are semipositive definite.).
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 26 / 28
Matrix norms
We may define norms for matrices too. We can either treat a matrix as a vector, and define a norm based on an entrywise norm (example: Frobenius norm). Or we may use a vector norm to “induce” a norm on matrices.
Frobenius norm:
sX 2 kAkF = ai,j.
Vector-induced (or operator, or spectral) norm: kAk2 = sup kAxk2 .
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 27 / 28
SVD Optimality
Given a matrix A, SVD allows us to find its “best” (to be defined) rank-r approximation Ar. P
>Pn> WecanwriteA=UDV asA= i=1diuivi .
For r n, construct Ar = ri=1 diuivi>.
The matrix Ar is a rank-r approximation of A. Moreover, it is the best approximation of rank r by many norms:
When considering the operator (or spectral) norm, it is optimal. This means that kA Ark2 kA Bk2 for any rank r matrix B. When considering Frobenius norm, it is optimal. This means that kA ArkF kA BkF foranyrankrmatrixB. Onewayto interpret this inequality is that rows (or columns) of Ar are the projection of rows (or columns) of A on the best r dimensional subspace, in the sense that this projection minimizes the sum of squared distances.
Intro ML (UofT) CSC311 – Tut 2 – Linear Algebra 28 / 28
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com