Scribd Logo
Upload

Welcome to Scribd!

  • 38 views

    Lecture Notes On SVD For Math 54

    Uploaded by

    Brad
    1. The singular value decomposition (SVD) transforms a matrix A into the product of three matrices: A = UΣV^T, where U and V are orthogonal matrices and Σ is a diagonal matrix of singular values. 2. To find the SVD, diagonalize the symmetric matrix S = A^TA to obtain an orthonormal basis of eigenvectors. 3. Reorder the eigenvalues of S so that they are nonnegative and in non-increasing order. The singular values are the nonnegative square roots of the eigenvalues. 4. Extend the eigenvectors to orthonormal bases U and V of the row and column spaces. The SVD is then A = UΣV^

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture Notes On SVD For Math 54

    Uploaded by

    Brad
    38 views5 pages
    1. The singular value decomposition (SVD) transforms a matrix A into the product of three matrices: A = UΣV^T, where U and V are orthogonal matrices and Σ is a diagonal matrix of singular values. 2. To find the SVD, diagonalize the symmetric matrix S = A^TA to obtain an orthonormal basis of eigenvectors. 3. Reorder the eigenvalues of S so that they are nonnegative and in non-increasing order. The singular values are the nonnegative square roots of the eigenvalues. 4. Extend the eigenvectors to orthonormal bases U and V of the row and column spaces. The SVD is then A = UΣV^

    Original Title

    Lecture Notes on SVD for Math 54

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The singular value decomposition (SVD) transforms a matrix A into the product of three matrices: A = UΣV^T, where U and V are orthogonal matrices and Σ is a diagonal matrix of singular values. 2. To find the SVD, diagonalize the symmetric matrix S = A^TA to obtain an orthonormal basis of eigenvectors. 3. Reorder the eigenvalues of S so that they are nonnegative and in non-increasing order. The singular values are the nonnegative square roots of the eigenvalues. 4. Extend the eigenvectors to orthonormal bases U and V of the row and column spaces. The SVD is then A = UΣV^

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    38 views5 pages

    Lecture Notes On SVD For Math 54

    Uploaded by

    Brad
    1. The singular value decomposition (SVD) transforms a matrix A into the product of three matrices: A = UΣV^T, where U and V are orthogonal matrices and Σ is a diagonal matrix of singular values. 2. To find the SVD, diagonalize the symmetric matrix S = A^TA to obtain an orthonormal basis of eigenvectors. 3. Reorder the eigenvalues of S so that they are nonnegative and in non-increasing order. The singular values are the nonnegative square roots of the eigenvalues. 4. Extend the eigenvectors to orthonormal bases U and V of the row and column spaces. The SVD is then A = UΣV^

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    SINGULAR VALUE DECOMPOSITION

    Notes for Math 54, UC Berkeley

    Let A be an m × n matrix. We discuss in these notes how to transform


    the perhaps complicated A into a simpler form, by multiplying it on the left
    and right by appropriate orthogonal matrices. This is important for many
    interesting applications.

    LEMMA 1. The matrix


    S = AT A
    is a symmetric n × n matrix.

    Proof. We recall the matrix formula (BC)T = C T B T , which implies that

    S T = (AT A)T = AT (AT )T = AT A = S.

    The transpose AT is an n × m matrix and thus S is n × n.

    Since S is symmetric, it has real eigenvalues λ1 , . . . , λn and corresponding


    eigenvectors {v1 , . . . , vn } so that

    (1) AT Avj = Svj = λj vj (j = 1, . . . , n)

    and
    {v1 , . . . , vn } is an orthonormal basis of Rn .

    LEMMA 2. (i) The following identities hold:

    (2) Avi · Avj = λj δij (i, j = 1, . . . , n),

    where (
    1 if i = j
    δij =
    0 6 j.
    if i =
    (ii) Furthermore, the eigenvalues of S = AT A are nonnegative:

    λj ≥ 0 (j = 1, . . . , n).

    1
    Proof. We use (1) to calculate that

    Avi · Avj = (Avi )T Avj = viT AT Avj = λj viT vj = λj vi · vj = λj δij ,

    since {v1 , . . . , vn } is orthonormal. In particular, λj = ||Avj ||2 ≥ 0.

    Let us now reorder, if necessary, the eigenvalues so that

    λ1 ≥ · · · ≥ λr > λr+1 = · · · = λn = 0.

    DEFINITION. The singular values of A are the numbers


    p
    σj = λj (j = 1, . . . , n).

    Then

    (3) σ1 ≥ · · · ≥ σr > σr+1 = · · · = σn = 0,

    and formula (2) implies

    (4) ||Avj || = σj (j = 1, . . . , n).

    DEFINITION. We write
    1
    ui = Avi (i = 1, . . . , r).
    σi

    It follows from (2) and (4) that {u1 , . . . , ur } is orthonormal in Rm , and


    thus
    0 ≤ r ≤ min{n, m}.
    We can now use the Gram-Schmidt process to find further vectors {ur+1 , . . . , um }
    so that
    {u1 , . . . , um } is an orthonormal basis of Rm .

    The key point is that we can use the orthonomal basis {u1 , . . . , um }
    of Rm and the orthonormal basis {v1 , . . . , vn } of Rn to convert our
    matrix A into a simpler form. Here is how to do it:

    2
    NOTATION. Introduce the m × m orthogonal matrix
    U = (u1 |u2 | . . . |um ),
    whose ith column is ui (i = 1, . . . , m). Likewise, introduce the n × n orthog-
    onal matrix
    V = (v1 |v2 | . . . |vn ).
    Then
    (5) U U T = U T U = I, V V T = V T V = I.

    THEOREM 1. We have
     
    σ1 0 ... 0
     0 σ2 ... 0 
     
    (6) U T AV =  ... ... ..
    .
    .. .
     
     . O
    0 0 . . . σr 
    O O

    REMARK. Thus if we write Σ for the m × n matrix on the right hand side
    of (6), we obtain using (5) the singular value decomposition (SVD)

    (7) A = U ΣV T
    of our matrix A.
    This is similar to the familiar orthogonal diagonalization formula for a
    symmetric n × n matrix, but in (6) and (7) the matrix A need not be
    symmetric nor square.

    Proof. Since
    AV = A(v1 |v2 | . . . |vn ) = (Av1 |Av2 | . . . |Avn ),
    it follows that
     
    u1 · Av1 u1 · Av2 . . . u1 · Avn
     u2 · Av1 u2 · Av2 . . . u2 · Avn 
    (8) U T AV =  .
     
    .. .. ... ..
     . . . 
    um · Av1 um · Av2 . . . um · Avn

    3
    Now if j ∈ {r + 1, . . . , n}, then Avj = 0. If j ∈ {1, . . . , r} and i ∈ {r +
    1, . . . , m}, then
    ui · Avj = σj ui · uj = 0.
    Finally, if i, j ∈ {1, . . . , r}, then
    1 λi
    ui · Avj = Avi · Avj = vi · vj = σi δij .
    σi σi
    Using these formulas in (8) gives (6).

    SUMMARY: HOW TO FIND THE SVD

    1. Diagonalize S = AT A, to find an orthonormal basis of Rn of eigenvec-


    tors {v1 , . . . , vn }.

    2. Reorder the eigenvalues of S so that λ1 ≥ · · · ≥ λn ≥ 0.

    3. Let 1
    σj = λj2 (j = 1, . . . , n);
    then
    σ1 ≥ · · · ≥ σr > σr+1 = · · · = σn = 0.

    4. Define
    1
    ui = Avi (i = 1, . . . , r).
    σi
    5. Extend {u1 , . . . , ur } to an orthonormal basis {u1 , . . . , um } of Rm .

    6. Write U, V and Σ, as above; then A = U ΣV T is the corresponding


    singular value decomposition of the matrix A.

    EXAMPLE. Find the SVD for the non-symmetric matrix


     
    −4 6
    A= .
    3 8

    We compute  
    T 1 0
    S = A A = 25 .
    0 4

    4
    The eigenvalues of S are λ1 = 100, λ2 = 25, with corresponding orthonormal
    eigenvectors    
    0 1
    v1 = , v2 = .
    1 0
    Therefore
    σ1 = 10, σ2 = 5
    and    
    1 1 3 1 1 −4
    u1 = Av1 = , u2 = Av2 = .
    σ1 5 4 σ2 5 3
    So      
    0 1 1 3 −4 10 0
    V = , U= , Σ= .
    1 0 5 4 3 0 5

    We check that U, V are orthogonal matrices, and


         
    T 1 3 −4 10 0 0 1 −4 6
    U ΣV = = = A.
    5 4 3 0 5 1 0 3 8

    You might also like