[Math] Use SVD to reduce condition number of matrix

condition numberpythonsvd

I need to compute the inverse of an ill-conditioned matrix. Since condition number is ratio of high/low singular values. I am approximating the matrix by removing small singular values. But the conditioned number of obtained matrix is even higher. The python code is:

UU,SS,VV=scipy.linalg.svd(A) # A is 100 x 150 
Sigma = numpy.zeros((70, A.shape[1]))
Sigma[:70, :70] = numpy.diag(SS[0:70])
numpy.linalg.cond(numpy.matmul(numpy.matmul(UU[:,0:70],Sigma),numpy.transpose(VV)))

The condition number of A is 3391639000000000.0 but after removing singular values it becomes 1.712286461590629e+23

Best Answer

What you're doing is equivalent to setting all but the top 70 singular values equal to $0$, as the code below illustrates. The resulting matrix is singular.

import numpy as np
import scipy as sp

numRows = 100
numCols = 150
numKeep = 70
A = np.random.randn(numRows,numCols)

U,S,VT = sp.linalg.svd(A)  

# This is how we recover A from U, S, and VT
Sigma = np.zeros((numRows,numCols))
for i in range(numRows):
    Sigma[i,i] = S[i]

A_check = U @ Sigma @ VT
print("Is A equal to A_check?")
print(np.allclose(A,A_check))

#Now compute B using method 1, "removing smaller singular values"
Sigma = np.zeros((numKeep, numCols))
for i in range(numKeep):
    Sigma[i,i] = S[i]

B = U[:,0:numKeep] @ Sigma @ VT

# Now compute B using method 2, 
# by setting all but top 70 singular values set equal to 0.
Sigma = np.zeros((numRows,numCols))
for i in range(numKeep):
    Sigma[i,i] = S[i]

B_check = U @ Sigma @ VT
print("Is B equal to B_check?")
print(numpy.allclose(B,B_check))
Related Question