K K Singh

SVD
K K Singh
• Singular Value Decomposition
The word decomposition means , it expresses a matrix (A) as a product of three matrices (U, Σ, V)
The non-negative diagonal entries (of Σ ) are called the singular values of the matrix A, hence the
name singular value decomposition.
A = U Σ VT , U and V are orthonormal and Unitary matrix
UUT = I, VVT = I
• Each singular value σᵢ is amplifying the vectors in the vᵢ ( in Rn space) and mapping them
into the uᵢ (in Rm space).
• In SVD, the singular values are sorted as σ₁ ≥ σ₂ ≥ … ≥ σp.
• This means that a vector in the v₁ direction will be most amplified/ important vector and
mapped into the u₁ direction
• The relative importance of ith direction is σᵢ.

• U and V are eigen vectors of AAT, ATA respectively with eigen values Σ 2
• Proof
Let A = U Σ VT and AT = V Σ UT
ATA= V Σ UT U Σ VT AV = U Σ => AV =b means V gives row space (A) + null space(A)
A AV= V Σ
T 2 ATU =VΣ => ATU =b means U gives column space(A) + left null space(A)
2. Compute eigen vector u1 and u2 for at λ1= 25 and
λ 2= 9 at AAT
1. Compute ATA AAT , which ever lesser in

dimension first 3. Compute eigen vector v1 and v2 for at 25 and 9
Using AAT - λ I=0 or using vi = ATui / σi
and compute v3, such that v3.v1=0, and v3.v2=0

σi = sqrt( λi)
V=
• we can imagine v₁, v₂, …, vp as a set of axes in the n-dimensional space. And each singular
value σᵢ is amplifying the vectors vᵢ axis in the n-dimensional space and mapping them into
the uᵢ axis in the m-dimensional space.
1
Illustration of the singular value decomposition UΣV ⁎
of a real 2×2 matrix M.
Let us have a unit disc D with the two canonical unit

vectors e1 and e2. 2 4
1. The action of M, indicated by its effect on e1 and e2
3
2. The action of V , a rotation, on D.
⁎
3. The action of Σ, a scaling by the singular values

σ1 horizontally and σ2 vertically.
4. The action of U, another rotation.

Singular Value Decomposition in a Movie Recommender System
• How Netflix (or other OTT) figures out
which movie you want to watch next?
• The recommender systems are the top
secrets of the media companies,
• There are still some fundamental ideas in
mathematics that will help us understand
how those recommender systems work.
• One such idea is called the Singular Value
Decomposition (SVD),
• Let us have the Movie rating data as a
SF- Scientific fiction, Rom- Romantic
matrix
In this matrix, each row corresponds to each user, and each column to each movie.
There are two distinguishable groups of users: the sci-fi fans and rom-com fans.
Example, our “User 3” looks like a sci-fi fan. And given high ratings to sci-fi movies, but not to the
romantic comedy movies, as highlighted in the matrix,
• In this dataset, there are two groups of users, the sci-fi fans and the rom-com fans,
• And also two types of movies, the sci-fi movies and the rom-com movies.
• Thus, the key takeaways of SVD, we expect to see the sci-fi direction and the rom-com direction in both the movie space
and the user space.
• And how the singular values shows the relative importance of each direction.
• The absolute values of Σ are important. The +,- signs happen kind of randomly from how the computer
code calculates the eigenvectors for us.)
• We can see that the sci-fi importance is roughly twice larger than the rom-com
importance factor, and that makes sense because, in this simple dataset, there
are twice more sci-fi fans than there are rom-com fans.
• In summary. The movie ratings matrix maps movies to the users, The V matrix
figures out which ones are the sci-fi movies (v1) and which ones are the rom-
com movies(v2)
• Then the Σ matrix multiplies the relative importance to each genres of movies.
• The U matrix maps each genres of movies to the fans of the genres.
• The users pointed by the u₁ vector receives the sci-fi movies, and the u₂ users
the rom-com movies.
Movie Ratings Prediction with SVD
• The key point is to reconstruct the movie ratings matrix A from the
key features that SVD has detected from the matrix.
• This means that we can reconstruct the matrix A with only using the
fans of each genre, u₁ and u₂, and the importance factors, σ₁ and σ₂,
and the movies of each genre, v₁ and v₂.
In mathematics, this technique is called

the low rank approximation. It captures
the most important dimensions in a given
matrix and recreates the matrix with that
dimensions only.
Forget about the un-important features
because they only add noises from random
variances in the fans and the movies
Movie Ratings Prediction with SVD
• Let us add a new user-7 with partial information (5, - , - , 1, - ).
• let’s just fill in the empty ratings with 3 = (5 + 1)/2 as a placeholder,
which is the average of all available ratings given by the user.
We can see that the prediction matrix indeed gives high ratings to the sci-fi movies that
“User 7” has not seen before and a low rating to the unseen rom-com movie
Practical Challenges and Solutions
• The movie ratings matrix will be so much larger
• The majority of the values in the movie ratings matrix will be missing
(sparse matrix)
• Source:
https://yeunun-choo.medium.com/singular-value-decomposition-in-a-
movie-recommender-system-e3565ed42066
The Four fundamental Subspaces using SVD
• Suppose that A is a m -by- n matrix that maps vectors in Rn to vectors
in Rm
• A: Rn -> Rm
• Let r = rank(A)
polar decomposition
• In mathematics, the polar decomposition of a square real/complex matrix A
is a factorization of the form A= UP ,
where U is a unitary matrix and P is a positive semi-definite Hermitian matrix
• Intuitively, if a real (n, n) matrix A is interpreted as a linear transformation of n-
dimensional space Rn ,
• The polar decomposition separates it into a rotation or reflection U of Rn , and
a scaling of the space along a set of n orthogonal axes.
• The polar decomposition of a square matrix A always exists.
• If A is invertible, the decomposition is unique, and the factor P will be positive-definite.
• In terms of the singular value decomposition (SVD) of A as
• A=WΣV T
= (W Σ WT ) (W VT ) =(W VT) (VΣ VT )
Example

K K Singh

Uploaded by

Copyright:

Available Formats

K K Singh

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

K K Singh

Uploaded by

Copyright:

Available Formats

SVD

• The relative importance of ith direction is σᵢ.

ATA= V Σ UT U Σ VT AV = U Σ => AV =b means V gives row space (A) + null space(A)

1. Compute ATA AAT , which ever lesser in

and compute v3, such that v3.v1=0, and v3.v2=0

of a real 2×2 matrix M.

Let us have a unit disc D with the two canonical unit

3. The action of Σ, a scaling by the singular values

4. The action of U, another rotation.

In mathematics, this technique is called

You might also like