Singular Value Decomposition(SVD) in python from scratch
Singular Value Decomposition in python from scratch
According to wikipedia, SVD is a factorization of a real or complex matrix. For more information, please go through this wiki link.
A matrix M can be written in terms of factorization as under. $$ M = UΣV^T $$
Where M is (mxn) matrix.
Steps to compute SVD :
- Columns of V are eigen vectors of $M^TM$.
- Columns of U are eigne vectors of $MM^T$.
- The singular values in $Σ$ are the square root of eignen values from $M^TM$ or $MM^T$. They are in the diagonal of Σ matrix and arranged in decreasing order.
Python implementation:
A = np.asarray([[2, 4], [1,3], [0, 0], [0, 0]])
# write A as A=UΣ(V.T)
# Assume that A is a full rank matrix.
# For more information, I have given a link in the reference section. Do checkout.
AA_T = A.dot(A.T)
print(AA_T.shape)
u_eval, u_evect = np.linalg.eig(AA_T)
print(u_eval.shape, u_evect.shape)
U = u_evect
# V.T
A_TA = A.T.dot(A)
print(A_TA.shape)
v_eval, v_evect = np.linalg.eig(A_TA)
print(v_eval.shape, v_evect.shape)
V_T = v_evect
outputs:
U=
array([[ 0.81741556, -0.57604844, 0. , 0. ],
[ 0.57604844, 0.81741556, 0. , 0. ],
[ 0. , 0. , 1. , 0. ],
[ 0. , 0. , 0. , 1. ]])
V=
array([[-0.9145143 , -0.40455358],
[ 0.40455358, -0.9145143 ]])
Note that V is not transposed yet. (in case you need a transpose one, make sure you do that yourself.)
eigen values of $A^TA$ : (you can take either of $A^TA$ or $AA^T$)
array([0.36596619, 5.4649857 ]))
Let’s cross check using numpy inbuilt linear algebra module.
u, sigma, vh = np.linalg.svd(a)
Output:
U=
array([[-0.81741556, -0.57604844, 0. , 0. ],
[-0.57604844, 0.81741556, 0. , 0. ],
[ 0. , 0. , 1. , 0. ],
[ 0. , 0. , 0. , 1. ]])
V.T =
array([[-0.40455358, -0.9145143 ],
[-0.9145143 , 0.40455358]])
singular values=
array([5.4649857 , 0.36596619])
Negative sign means the direction of eigen vectors gets reversed while keeping the magnitude as a liinear function of singular values.