Scribd
Upload
46 views15 pages

The Singular Value Decomposition Let A Be

Uploaded by

tranthaongan7epct
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
46 views15 pages

The Singular Value Decomposition Let A Be

Uploaded by

tranthaongan7epct
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

THE SINGULAR VALUE DECOMPOSITION

 Theorem: The Singular Value Decomposition Let A be


an 𝑚 × 𝑛 matrix with rank r. Then there exists an 𝑚 × 𝑛
diagonal matrix Σ whose diagonal entries are non-
negative (the first r singular values of A, 𝜎1 ≥ 𝜎2 ≥ ⋯ ≥
𝜎𝑟 > 0), and there exist an 𝑚 × 𝑚 orthogonal matrix U
and an 𝑛 × 𝑛 orthogonal matrix V such that

𝐴 = 𝑈Σ𝑉𝑇
THE SINGULAR VALUE DECOMPOSITION

 The columns of U in such a decomposition are called left


singular vectors of A, and the columns of V are called
right singular vectors of A.
 The diagonal entries of Σ are called the singular values
of A
𝐴 = 𝑈Σ𝑉𝑇
THE SINGULAR VALUE DECOMPOSITION
 Proof Let 𝜆𝑖 and vi be as in Theorem , so that {Av1, . . . , Avr} is
an orthogonal basis for Col A.
 Normalize each Avi to obtain an orthonormal basis {u1, . . . , ur},
where
1 1
𝑢𝑖 = 𝐴𝑣𝑖 = 𝐴𝑣𝑖
𝐴𝑣𝑖 𝜎1
 And (*)
𝐴𝑣𝑖 = 𝜎𝑖𝑢𝑖 (1 ≤ i ≤ r)
 Now extend {u1, . . . , ur} to an orthonormal basis {u1, . . . , um}
of ℝ𝑚 , and let
𝑈 = [𝑢1 𝑢2 . . . 𝑢𝑚] and 𝑉 = [𝑣1 𝑣2 . . . 𝑣𝑚]

 By construction, U and V are orthogonal matrices.


THE SINGULAR VALUE DECOMPOSITION
 Also, from (*),
𝐴𝑉 = 𝐴𝑥1 … 𝐴𝑣𝑟 0 … 0 = [𝜎1𝑢1 . . . 𝜎𝑟𝑢𝑟 0 . . . 0]
 Let D be the diagonal matrix with diagonal entries
𝜎1,...,𝜎𝑟, and let Σ be as follow. Then

 Since V is an orthogonal matrix, 𝑈Σ𝑉𝑇 = 𝐴𝑉𝑉𝑇 = 𝐴.


THE SINGULAR VALUE DECOMPOSITION
 Example Construct a singular value decomposition of
1 1 0
𝐴=
0 0 1
Solution A construction can be divided into three steps.
 Step 1. Find an orthogonal diagonalization of ATA. That is,
find the eigenvalues of ATA and a corresponding orthonormal
set of eigenvectors
 Step 2. Set up V and 𝜮. Arrange the eigenvalues of ATA in
decreasing order.
 Step 3. Construct U. When A has rank r, the first r columns of
U are the normalized vectors obtained from Av1, . . . , Avr.
THE SINGULAR VALUE DECOMPOSITION
 Example Construct a singular value decomposition of
1 1 0
𝐴=
0 0 1
 Step 1. Find an orthogonal diagonalization of ATA.
1 0 1 10
1 1 0
ATA= 1 0 = 1 1 0
0 0 1
0 1 0 01
det(ATA-𝛌𝐈)=0

The eigenvalues are λ =2, λ =1, and λ =0


THE SINGULAR VALUE DECOMPOSITION
 Example Construct a singular value decomposition of
1 1 0
𝐴=
0 0 1
 Step 1. Find an orthogonal diagonalization of ATA.
1 10
ATA= 1 1 0 det(ATA-𝛌𝐈)=0
0 01
1/ 2
 Basis for λ = 2: v1 = 1/ 2
0
0 −1/ 2
 Basis for λ = 1: v2 = 0 and Basis for λ = 0: v3 = 1/ 2
1 0
THE SINGULAR VALUE DECOMPOSITION

 Step 2. Set up V and 𝜮. Arrange the eigenvalues of ATA in


decreasing order. The corresponding unit eigenvectors, v1,
v2, and v3, are the right singular vectors of A.
1/ 2 0 −1/ 2
𝑉 = 𝑣1 𝑣2 𝑣3 = 1/ 2 0 1/ 2
0 1 0

 The square roots of the eigenvalues are the singular values:


𝜎1 = 2, 𝜎2 = 1, 𝜎3 = 0
THE SINGULAR VALUE DECOMPOSITION
 The matrix Σ is

2 0 0 2 0 0
Σ = 0 1 0 , Σ=
0 1 0
0 0 0
 Step 3. Construct U. When A has rank r, the first r columns of
U are the normalized vectors obtained from Av1, . . . , Avr.
𝐴 = 𝑈Σ𝑉𝑇 𝐴𝑉 = 𝑈Σ
THE SINGULAR VALUE DECOMPOSITION
 Thus
1 1
𝑢1 = 𝐴𝑣1 =
𝜎1 0
1 0
𝑢2 = 𝐴𝑣2 =
𝜎2 1
 Note that {u1, u2} is already a basis for ℝ2 . Thus no
additional vectors are needed for U, and U = [u1 u2]. The
singular value decomposition of A is
1/ 2 1/ 2 0
1 0 2 0 0
𝐴= 0 0 1
0 1 0 1 0
−1/ 2 1/ 2 0
THE SINGULAR VALUE DECOMPOSITION
 Example Construct a singular value decomposition of
4 11 14
𝐴=
8 7 −2
The Singular Value Decomposition
Image Compression
The Singular Value Decomposition

Image Compression

You might also like