<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 SVD is one of the matrix factorization tecniques. It factors a matrix into three parts with which we can reconstruct the initial matrix. However, reconstructing original matrix is not mostly the primary aim. Rather, we factorize matrices in order to achive following goals
Step1:  Left singular vectors
Step2:  Singular values
Step3:  As you can see, the singular values are sorted descendingly.
Right singular values
Step4:  Reconstructing the original matrix
Step5:  We use all the dimentions to get back to the original matrix. As a result, we obtain the matrix which is almost identical. Let's calculate the difference between the two matrices.
Step6:  Expectedly, the error is infinitesimal.
However, most of the time this is not our intention. Instead of using all the dimentions(rank), we only use some of them, which have more variance, in other words, which provides more information. Let's see what we will get when using only the first three most significant dimentions.
Step7:  Again, the reconstructed matrix is very similar to the original one. And the total error is still small. 
Now we can ask the question that which rank should we pick? There is trade-off that when you use more rank, you get closer to the original matrix and have less error, however you need to keep more data. On the other hand, if you use less rank, you will have much error but save space and remove the redundant dimentions and noise.
Step8:  As it can be seen above, more rank is used, less error occur. From another perspective, we get closer to the original data by increasing rank number.
On the other hand, after a certain rank, using more rank will not contribute as much as 
Let's compare a reconstructed column to the original one by just naked eyes. Even it is reconstructed using only 4 dimention, we almost, with some error, get the original data.
<ASSISTANT_TASK:>
Python Code:
A = np.mat([
    [4, 5, 4, 1, 1],
    [5, 3, 5, 0, 0],
    [0, 1, 0, 1, 1],
    [0, 0, 0, 0, 1],
    [1, 0, 0, 4, 5],
    [0, 1, 0, 5, 4],
])
U, S, V = np.linalg.svd(A)
U.shape, S.shape, V.shape
Explanation: SVD is one of the matrix factorization tecniques. It factors a matrix into three parts with which we can reconstruct the initial matrix. However, reconstructing original matrix is not mostly the primary aim. Rather, we factorize matrices in order to achive following goals:
to find principal components
to reduce matrix size removing redundant dimentions
to find latent dimentions
visualization
In a simple terms, factorization can be defined as breaking something into its building blocks, in other terms, its factors. Using SVD, we can decompose a matrix into three separate matrices as follows:
$$ A_{m x n} = U_{m x r} * \Sigma_{r x r} * (V_{n x r})^{T} $$
where 
- U is the left singular vectors
- $\Sigma$ is the singular values sorted descending order along its diagonal, and full of zeroes elsewhere
- V is the right singular vectors
- m is the number of rows, 
- n is the number of columns(dimentions), 
- and r is the rank.
Example
End of explanation
U
Explanation: Left singular vectors
End of explanation
S
np.diag(S)
Explanation: Singular values
End of explanation
V
Explanation: As you can see, the singular values are sorted descendingly.
Right singular values
End of explanation
def reconstruct(U, S, V, rank):
    return U[:,0:rank] * np.diag(S[:rank]) * V[:rank]
r = len(S) 
reconstruct(U, S, V, r)
Explanation: Reconstructing the original matrix
End of explanation
def calcError(A, B):
    return np.sum(np.power(A - B, 2))
calcError(A, reconstruct(U, S, V, r))
Explanation: We use all the dimentions to get back to the original matrix. As a result, we obtain the matrix which is almost identical. Let's calculate the difference between the two matrices.
End of explanation
reconstruct(U, S, V, 3)
calcError(A, reconstruct(U, S, V, 3))
Explanation: Expectedly, the error is infinitesimal.
However, most of the time this is not our intention. Instead of using all the dimentions(rank), we only use some of them, which have more variance, in other words, which provides more information. Let's see what we will get when using only the first three most significant dimentions.
End of explanation
reconstruct(U, S, V, 2)
calcError(A, reconstruct(U, S, V, 2))
A = np.mat([
    [4, 5, 4, 0, 4, 0, 0, 1, 0, 1, 2, 1],
    [5, 3, 5, 5, 0, 1, 0, 0, 2, 0, 0, 2],
    [0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0],
    [0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 5, 0, 0, 4, 5, 4, 0],
    [0, 1, 1, 0, 0, 4, 3, 5, 5, 3, 4, 0],
])
def reconstruct(U, S, V, rank):
    return U[:,0:rank] * np.diag(S[:rank]) * V[:rank]
for rank in range(1, len(S)):
    rA = reconstruct(U, S, V, rank)
    error = calcError(A, rA)
    coverage = S[:rank].sum() / S.sum()
    print("with rank {}, coverage: {:.4f}, error: {:.4f}".format(rank, coverage, error))
Explanation: Again, the reconstructed matrix is very similar to the original one. And the total error is still small. 
Now we can ask the question that which rank should we pick? There is trade-off that when you use more rank, you get closer to the original matrix and have less error, however you need to keep more data. On the other hand, if you use less rank, you will have much error but save space and remove the redundant dimentions and noise.
End of explanation
print("Original:\n", A[:,10])
print("Reconstructed:\n", reconstruct(U, S, V, 4)[:,10])
imread("data/pacman.png", flatten=True).shape
A = np.mat(imread("data/pacman.png", flatten=True))
U, S, V = np.linalg.svd(A)
A.shape, U.shape, S.shape, V.shape
for rank in range(1, len(S)):
    rA = reconstruct(U, S, V, rank)
    error = calcError(A, rA)
    coverage = S[:rank].sum() / S.sum()
    print("with rank {}, coverage: {:.4f}, error: {:.4f}".format(rank, coverage, error))
for i in range(1, 50, 5):
    rA = reconstruct(U, S, V, i)
    print(rA.shape)
    plt.imshow(rA, cmap='gray')
    plt.show()
plt.imshow(data, interpolation='nearest')
128 * 128 
- (10*128*2)
from PIL import Image
A = np.mat(imread("data/noise.png", flatten=True))
img = Image.open('data/noise.png')
imggray = img.convert('LA')
imgmat = np.array(list(imggray.getdata(band=0)), float)
imgmat = np.array(list(imggray.getdata(band=0)), float)
imgmat.shape = (imggray.size[1], imggray.size[0])
imgmat = np.matrix(imgmat)
plt.figure(figsize=(9,6))
plt.imshow(imgmat, cmap='gray');
plt.show()
U, S, V = np.linalg.svd(imgmat)
for i in range(1, 10, 1):
    rA = reconstruct(U, S, V, i)
    print(rA.shape)
    plt.imshow(rA, cmap='gray');
    plt.show()
Explanation: As it can be seen above, more rank is used, less error occur. From another perspective, we get closer to the original data by increasing rank number.
On the other hand, after a certain rank, using more rank will not contribute as much as 
Let's compare a reconstructed column to the original one by just naked eyes. Even it is reconstructed using only 4 dimention, we almost, with some error, get the original data.
End of explanation
<END_TASK>