Singular Value Decomposition

Mathematical Proof of Singular Decomposition 

Singular Value Decomposition mathematically states that for any matrix A∈R n×m A∈Rn×m, we have A=UΣV⊤ , where

U∈Rn×n is an orthogonal matrix whose columns are the eigenvectors of AA⊤

(AA^T = UDV^TVDU^T = UD²U^T ) 

V∈Rm×m is an orthogonal matrix whose columns are the eigenvectors of A⊤A

(A^TA = VDU^TUDV^T = VD²V^T)

Σ∈Rn×m is an all-zero matrix except for the first r diagonal elements σi=Σii, i=1,…,r (called singular values) that are the square roots of the eigenvalues of A⊤A and of AA⊤ (these two matrices have the same eigenvalues).

D = diag( 1 , 2 ,..., n ) ordered so that 1 ≥ 2 ≥ ... ≥ n (if is a singular value of A, it’s square is an eigenvalue of A T A) - If U = (u1 u2 ... un ) and V = (v1 v2 ... vn ), then

The sum here goes from 1 to r, where r is the rank of the A here.

As shown above, the singular values are sorted in descending order, and the eigenvectors are sorted in decreasing order of their eigenvalues.

Let’s understand this with the help of an example stated below: 

Let’s take a matrix A: 

   The eigenvalues of AA^T , A^TA are: 

   The eigenvectors of AA^T , A^TA are:

 

The expansion of A is: 

Based on the above formulae, we get: 

Implementation of Singular Value Decomposition 

We can understand the implementation of singular value code with this simple example stated below. 

Step 1: We import the required libraries. We use the most popular libraries that are numpy and linear algebra libraries, part of numpy. 

We use eigh, which is used to find the hermitian matrixes for eigenvalues and eigenvectors. We use the norm function to find the norm of a vector.  

import numpy as np
from numpy.linalg import eigh, norm

 

Step 2: We create an array as you can see if you have arrays inside an array that's like a

 matrix because each of these arrays of numbers is thought of as rows of a matrix, and you put commas and then enclose them again by brackets that give you a two-dimensional array and which is a matrix.  

A = np.array([[-5, 2, 3],
              [2, 5, 1],
              [-3, 1, -5]])

 

Step 3: Perform the matrix multiplication, which in the case of standard value decomposition is: 

A.T@A

 

Output: 

array([[38, -3,  2],
       [-3, 30,  6],
       [ 2,  6, 35]])

 

We use the symbol ‘@’ for matrix multiplication here, and we find a symmetric matrix indeed.  

Step 4: We take the eigenvalues and eigenvectors here. 

eigh(A.T@A)

 

Output: 

(array([25., 39., 39.]), array([[ 0.26726124, -0.96362411,  0.        ],
        [ 0.80178373,  0.22237479,  0.5547002 ],
        [-0.53452248, -0.14824986,  0.83205029]]))

 

This gives us some integer eigenvalues, and the same procedure can be used for any matrix size. 

Step 5: We assign the second matrix of arrays to a variable V here, and we print V to see the values taken here. 

ev, V =eigh(A.T@A)
V

 

Output:

array([[ 0.26726124, -0.96362411,  0.        ],
       [ 0.80178373,  0.22237479,  0.5547002 ],
       [-0.53452248, -0.14824986,  0.83205029]])

 

Each of the columns here is the eigenvectors for A.T@A. 

Step 6: We find the first eigenvector here using the following code. This gives us row vectors of the column vector.  

V[:,0]

 

Output: 

array([ 0.26726124,  0.80178373, -0.53452248])

 

Step 7: Define the matrix U, and we do it starting from the Oth index. We apply A to the column vector of V and divide it by its size. 

u0 =A@V[:,0]/norm(A@V[:,0])
u1 =A@V[:,1]/norm(A@V[:,1])
u2 =A@V[:,2]/norm(A@V[:,2])

 

Step 8: We create U as a 2-dimensional matrix, and we divide it with its transpose cause we want columns here and not rows, so these are taken as column vectors.  

U=np.array([u0,u1,u2]).T

 

Using the below code, we get a diagonal matrix we round it to five decimal places to make our observations look simpler. 

np.round(U.T@A@V, decimals=5)

 

Output: 

array([[ 5.   ,  0.   , -0.   ],
       [-0.   ,  6.245,  0.   ],
       [-0.   , -0.   ,  6.245]])

 

Step 9: When we multiply T and V to the other size, we get the SVD of our equation. We print U to take a look at what U looks like. 

#A = U@D@V.T is the SVD
U

 

Output:

array([[-0.26726124,  0.77151675,  0.57735027],
       [ 0.80178373, -0.15430335,  0.57735027],
       [ 0.53452248,  0.6172134 , -0.57735027]])

 

We have successfully found the SVD here of the given matrix using python. Now let’s jump to some real-world applications of SVD. 

Application of Singular Value Decomposition 

1. Dimensionality Reduction
   The first and most essential application is to reduce data dimensionality; the SVD is a very convenient method, and PCA is identical to the SVD. You may wish to decrease the dimensionality of your data for the following reasons: 
   → You want to visualize your data in 2D or 3D; 
   → The method you're going to employ works much better in the lower dimensional space;
   → For performance reasons, reducing dimensions makes your algorithm quicker.
   → It's usually worth trying to use the SVD before an ML technique in many machine learning tasks.
    
2. Image Compression
   We can take advantage of this. A digitized image is just a large number matrix. For example, in a black-and-white image, they may be the gray levels, or in a color image, the color levels. Let's imagine our image has a resolution of 1000 x 2000 pixels. This necessitates the use of two million numbers. 
   We would only need to keep ten u's (10000 numbers), ten v's (20000 numbers), and 10's if the picture could be adequately represented by, say, a tenth term SVD decomposition (10 numbers). Our storage costs reduce, resulting in a compression ratio of more than 650:1.
    
3. Web-Searching 
   Google and other search engines employ massive matrices of cross-references to figure out which pages connect to which other pages and what phrases appear on each page. When you run a Google search, the pages with your key terms that have a lot of links to them generally rank higher. 
   However, there are many trillions of web pages out there, and keeping a billion-by-billion matrix, much alone navigating through it, is difficult. This is where SVD shines. When it comes to searching, the fundamental dimensions that the Digital world is taking are all that matter. 
   As a result, the first few single values give a very excellent approximation for the vast matrix, can be searched fast (only a few billion entries), and provide compression algorithms of millions to one. 
    
4. Latent Semantic Indexing
   When processing a corpus of text, we can decompose it into a term x document matrix, which can then be decomposed using the SVD. 
   The lowered estimation encapsulates (in some way) the ambiguity in our text, which has several advantages such as noise filtering, fixing the issue of synonyms, and so on. This has a wide range of applications in the field of information retrieval.

Frequently Asked Questions

1. Is SVD applicable to all matrices?
   Unlike the more often used spectral decomposition in Linear Algebra, singular value decomposition is specified for all matrices (rectangular or square). 
   Those who are conversant with eigenvectors and eigenvalues Recognize that requirements on the matrix are required to guarantee that the eigenvectors are orthogonal.  
    
2. Is SVD persistent in all matrices? 
   The SVD is always true for every rectangular or square matrix, but the eigendecomposition is only valid for square matrices; it isn't always true among even square matrices. 
    
3. Is SVD essential for persistent matrix reduction? 
   Significant is the fraction of a vector's linear transformation corresponding to a substantial single value. Positive singular values can be utilized to establish the effectual rank of matrix A by counting smaller values as zeros, in addition to what you mention in your query.  

Conclusion

Going through this article, we can conclude that Singular Value Decomposition (SVD) is a popular approach for decomposing a matrix into many component matrices, revealing many of the original matrix's valuable and intriguing features. 

Recommended Problems:

• Find the Good Matrix
• Ninja and the rows
• Set Matrix zeros
• Rotate Matrix clockwise
   

We can use SVD to identify the matrix's rank, measure a linear system's susceptibility to numerical error, or find the best lower-rank estimate to the matrix.
To learn more about similar concepts, follow our blogs to understand deep in machine learning.