Machine Learning
ECE 2195 (Fall 2019)
Lecture 5-1 Linear Algebra Review
Heng Huang, Ph.D.
Department of Electrical and Computer Engineering
Linear Algebra Review
• Vector-Vector Products
– Inner product or dot product
– Outer product
Fall 2019 Heng Huang Machine Learning 2
Linear Algebra Review
• Identity matrix
• Diagonal matrix
• Transpose
Fall 2019 Heng Huang Machine Learning 3
Linear Algebra Review
• Symmetric matrix
• Trace
?
Fall 2019 Heng Huang Machine Learning 4
Linear Algebra Review
• Norm
Fall 2019 Heng Huang Machine Learning 5
Linear Algebra Review
• Inverse: invertible or non-singular
• Orthogonal matrix
Fall 2019 Heng Huang Machine Learning 6
Linear Algebra Review
• Quadratic form
i.e., only the symmetric part of A contributes to the quadratic form. For this
reason, we often implicitly assume that the matrices appearing in a quadratic
form are symmetric.
• Positive definite, positive semidefinite, negative definite
One important property of positive definite and negative definite matrices is that
they are always full rank, and hence, invertible.
Fall 2019 Heng Huang Machine Learning 7
Linear Algebra Review
• Gram matrix
– Positive semidefinite
• Eigenvectors and eigenvalues
?
?
Fall 2019 Heng Huang Machine Learning 8
Linear Algebra Review
• Derivatives of matrix Derivatives of trace
• Exercise
Fall 2019 Heng Huang Machine Learning 9
Convex Function
f(t x + (1-t) y) <= t f(x) + (1-t) f(y)
Fall 2019 Heng Huang Machine Learning 10
Convex Set
Region above a convex function is a convex set.
Fall 2019 Heng Huang Machine Learning 11
Programming
• Objective function to be minimized/maximized.
• Constraints to be satisfied.
Example
Objective function
Constraints
Fall 2019 Heng Huang Machine Learning 12
Convex Programming
• Convex optimization function
• Convex feasible region
• Why is it so important ???
• Global optimum can be found in polynomial time.
• Many practical problems are convex
• Non-convex problems can be relaxed to convex ones.
Fall 2019 Heng Huang Machine Learning 13
Quadratic Programming
Fall 2019 Heng Huang Machine Learning 14