[K-MOOC] Introductory Mathematics for Artificial Intelligence
Translated by
Sang-Gu LEE with Youngju NIELSEN, Yoonmee HAM
from the original Korean text written by
Sang-Gu LEE with Jae Hwa LEE, Yoonmee HAM, Kyung-Eun PARK
Part Ⅱ. AI and Matrix
6. Matrix decompositions (LU, QR, SVD)
We need to understand how our computer understands and computes data. Let's briefly introduce three matrix decompositions that
AI often uses to handle real-life data.
6.1 LU decomposition
6.2 QR decomposition
6.3 SVD (Singular value decomposition)
We have discussed vector calculations, a system of linear equations, the least-squares problem. Computer programs use matrix decompositions
to solve these problems. We introduce the 
decomposition, the 
decomposition, and the Singular Value Decomposition (SVD).
6.1 LU decomposition
For a square matrix 
, 
-decomposition refers to the factorization of 
, with proper row and/or column orderings or permutations,
using a product of two factors. Two factors are a lower triangular matrix 
and an upper triangular matrix 
. In the mathematical expression, 
.
When the coefficient matrix can be expressed as a triangular matrix, the computation cost for solving a linear system of equations
can be reduced dramatically.
and
If 
is decomposed as 
, the linear equations 
can be written as 
(where 
). Then we can solve 
and then
solve the equation 
for finding 
of 
. All computation can be done easily because 
and 
are both triangular matrices.
< Finding 
of 
>
[Step 0] Find the 
-decomposition of 
(
)
[Step 1] Write 
as 
and find 
that satisfies 
.
[Step 2] Use 
obtained in [Step 1] to find 
that satisfies 
.
Let 
. Find the 
-decomposition of 
with a code for 
)
Use 
-decomposition to solve
Answer. 
= (-1, 2, 1) ■
6.2 QR decomposition
Let 
be a 
matrix with 
. The 
-decomposition is the factorization of a matrix 
into a product 
with an orthogonal matrix 
and an upper triangular matrix 
. Any orthogonal matrix 
satisfy 
, which means that all columns are orthonormal.
Given 
, we can solve the least-squares problem, 
, as follows.
Because 
is the solution of the above least-squares problem, the following relationship holds.
<John Von Neumann> pointed out. 'If the matrix can be decomposed by 
, the least-squares solution 
can be obtained immediately,
we know computers do 
-decomposition much better than us, and now we can solve most of the linear system of equations quickly with the computer.'
Find a 
-decomposition of 
.
☞ Note To find a 
-decomposition, we use the Gram-Schmidt orthonormalization process.
The followings are the Sage codes for the 
-decomposition.
Find the least-squares solution 
using a 
decomposition.
|
◩ Open Problem 15 |
Find one system of linear equations problem from other textbooks. Then find that problem's least-squares solution
using the same method as in example 4.
(Hint: http://matrix.skku.ac.kr/2018-album/LS-QR-decom.html)
[Reference] Problem solving https://youtu.be/BC9qeR0JWis
6.3 SVD(Singular Value Decomposition)
The SVD(singular value decomposition) always exists for any sort of rectangular or square matrices. It is the key feature of SVD.
The singular value decomposition of 
matrix 
is the matrix factorization in the form of 
, where 
is an 
orthogonal matrix,
is an 
orthogonal matrix, and 
is an 
rectangular (generalized) diagonal matrix with non-negative real numbers on the main diagonal.
Regardless of the size of the matrix, any matrix can be factorized into the product of an orthogonal matrix and a generalized diagonal matrix
and the transpose of an orthogonal matrix. 
is the SVD of a given matrix. Note that 
satisfies 
, and 
satisfies 
.
is a 
invertible diagonal matrix whose main diagonal components are positive (singular values) 
’s, and this (singular) values
are arranged in descending order(
). The other entries are all zero 
. We say these 
are the singular values of 
.
Singular values are generalized concepts of eigenvalues. As mentioned earlier, diagonal components of 
are called the singular values of the matrix 
,
and columns of 
are called the left singular vectors of 
, and columns of 
are called the right singular vectors of 
. Hence, 
satisfies 
and 
satisfies 
. 
is a 
square diagonal matrix whose main diagonal entries are positive singular values of 
.
Find the SVD of 
☞ Note We can have the SVD of 
using the code above. Additionally, we can check that 
is the same as the original matrix 
.
If we modify the code above a little bit, we can have SVDs for most given matrices. In the process of obtaining an SVD,
the components of a matrix may not be an integer or a natural number. Therefore, we will define a matrix with components in the Real Double Field, RDF,
to make all operations possible.
Find an SVD of 
in RDF(Real Double Field) and check 
.
|
◩ Open Problem 16 |
Find the SVD of a matrix you found from other textbooks by using the codes above.
In the code for finding an SVD, RDF works for real matrices, and CDF works for complex matrices.
More details on matrix diagonalizations can be found in the following link: http://matrix.skku.ac.kr/LA-K/ ( particularly in http://matrix.skku.ac.kr/LA-K/Ch-8/)
■ The derivation of matrix decomposition is beyond the high-school mathematics level. Refer to the below references for more details.
[Linear Algebra Textbook] http://matrix.skku.ac.kr/LA-K/
[Ejgenvalue] http://matrix.skku.ac.kr/LA-K/Ch-4/
[Matrix Diagonalization] http://matrix.skku.ac.kr/LA-K/Ch-8/
[Math for AI Book] http://matrix.skku.ac.kr/math4ai/Math4AI.pdf
[AI and Matrix] http://matrix.skku.ac.kr/math4ai/part1/
[LU decom tool] http://matrix.skku.ac.kr/LA-K/LU-decom.html
[QR decomposition tool] http://matrix.skku.ac.kr/LA-K/LS-QR-decom.html
[SVD Tool] http://matrix.skku.ac.kr/LA-K/SVD.html
[SVD Theory] http://matrix.skku.ac.kr/knou-knowls/cla-week-12-sec-8-6.html
[SVD Lecture] http://youtu.be/7-qG-A8nXmo
|
◩ Open Problem 1 |
Sketch the graph of three polynomial functions found in your other math books.
|
◩ Open Problem 2 |
Make the sketch of the graph for the function 
.
[ Hint: plot(x*sin(1/x), (x, -2, 2), ymin = -1.5, ymax = 1.5) ]
Practice in http://matrix.skku.ac.kr/KOFAC/
|
◩ Open Problem 3 |
Choose a composite function from the functions that you already learned and draw a graph of it.
[Hint: plot(sin(e^(1/3)^x), (x, -1.2, 10))]
Practice in http://matrix.skku.ac.kr/KOFAC/
|
◩ Open Problem 4 |
Find (approximate) solutions to various equations from other textbooks that you have used.
Practice in https://www.mathsisfun.com/algebra/approximate-solutions.html
http://matrix.skku.ac.kr/math4ai/PBL-Record/ http://matrix.skku.ac.kr/2020-Math4AI-PBL/
|
◩ Open Problem 5 |
Perform matrix operation by applying the operations on vectors and matrices you have learned in this book to matrices
you find in other textbooks. [http://matrix.skku.ac.kr/KOFAC/]
|
◩ Open Problem 6 |
Find bigger than 
matrix from the internet or other textbooks and check whether transpose and inverse matrices exist.
If those exist, find out what those are.
|
◩ Open Problem 7 |
What kinds of data can you apply the similarity measures we just discussed?
|
◩ Open Problem 8 |
What kind of data you cannot use this similarity measure using the distance? Any other measures that you can think of?
(Hint: Vectors/Data in the same directions)
|
◩ Open Problem 9 |
Make (randomly generate) two 7-dimensional vectors and then calculate the distance between two vectors.
(Hint: Lab <Distance similarity>) http://matrix.skku.ac.kr/math4AI-tools/distance_similarity/
|
◩ Open Problem 10 |
What kinds of data can you apply the cosine similarity to?
|
◩ Open Problem 11 |
Make two 5-dimensional vectors and find the inner product and the angle 
of two vectors.
( Hint: http://matrix.skku.ac.kr/math4AI-tools/cosine_similarity)
|
◩ Open Problem 12 |
Find a system of linear equations from other textbooks. Find a solution to that by using the code that you learned.
( Hint: http://matrix.skku.ac.kr/2018-album/LA-Sec-3-5-lab.html )
|
◩ Open Problem 13 |
Explain how and what we can determine for a given linear system of equations with a unique solution
or infinitely many solutions, or no solutions. Use RREF of 
to do this. Explain to others what you understand.
|
◩ Open Problem 14 |
Discuss the conditions for the existence of the inverse matrix of 
and find a least-squares solution
for the given 6-points in 
to make the curve of 
.
|
◩ Open Problem 15 |
Find a system of linear equations problem from other textbooks. Then find that problem's least-squares solution
using the same method as in example 4.
( Hint: http://matrix.skku.ac.kr/2018-album/LS-QR-decom.html )
|
◩ Open Problem 16 |
Find the SVD for a matrix from the other textbook by using the codes above.
Copyright @ 2021 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
