 # Refresher Course on Matrix Analysis and Optimization

## Part I: Matrix Analysis

Franck Iutzeler Jerome Malick

# 1- Linear Systems Resolution with applications to Regression¶

In this example, we use linear algebra to extract information from data; more precisely, we predict final notes of a group of student from their profiles with the Student Performance dataset which includes secondary education students of two Portuguese schools.

Profiles include features such as student grades, demographic, social and school related features and were collected by using school reports and questionnaires. There are $m = 395$ students (examples) and we selected $n = 27$ features (see data/student.txt for the features description and datat/student-mat.csv for the csv dataset.)

Our goal is to predict a target feature (the $28$-th) which is the final grade of the student from the other features (the first $27$). We assume that the final grade can be explained by a linear combination of the other features. We are going to learn from this data using linear regression over the $m_{learn} = 300$ students (called the learning set). We will check our prediction by comparing the results for the other $m_{test} = 95$ students (the testing set).

In :
import numpy as np

A_learn = dat_file['A_learn']
b_learn = dat_file['b_learn']
A_test = dat_file['A_test']
b_test = dat_file['b_test']

m = 395 # number of read examples (total:395)
n = 27 # features
m_learn = 300


Mathematically, from the $m_{learn} \times (n+1)$ learning matrix (the number of columns is $n+1$ as a column of ones, called intercept for statistical reasons). $A_{learn}$ comprising of the features values of each training student in line, and the vector of the values of the target features $b_{learn}$; we seek a size-$n+1$ regression vector that minimizes the squared error between $A_{learn} x$ and $b_{learn}$. This problem boils down to the following least square problem: $$\min_{x\in\mathbb{R}^{n+1}} \| A_{learn} x - b_{learn} \|_2^2 .$$

Question a: Compute (numerically!) the rank of the $m_{learn} \times (n+1)$ matrix $A_{learn}$. Does it have full (row, column) rank? Conclude about the existence and uniqueness of solutions of the problem.

In :
np.linalg.matrix_rank(A_learn)

Out:
28
In :
A_learn.shape

Out:
(300, 28)

Question b: Compute the solution of the minimization problem using:

1. the least square solver of Numpy lstsq
• the Singular Value Decomposition svd to solve $A_{learn}^{\top} \left( A_{learn} x - b_{learn} \right) = 0$. (see the course)

Compare both solutions.

In :
np.linalg.lstsq(A_learn,b_learn)

/tmp/ipykernel_76258/112070344.py:1: FutureWarning: rcond parameter will change to the default of machine precision times max(M, N) where M and N are the input matrix dimensions.
To use the future default and silence this warning we advise to pass rcond=None, to keep using the old, explicitly pass rcond=-1.
np.linalg.lstsq(A_learn,b_learn)

Out:
(array([ 2.21118747e-02,  2.44244170e-02,  1.57703207e-02,  5.79639062e-02,
1.56997199e-01,  1.52433811e-01, -2.19629756e-01,  2.80629653e-02,
-1.42717475e-01, -1.42735887e-01, -1.02683521e-01, -9.49573125e-02,
-6.72715015e-03,  9.62766220e-02,  1.11278660e-01, -2.19567464e-01,
1.27339462e-01,  7.03440311e-02,  3.77977322e-01,  5.92079169e-02,
-1.35174789e-01, -1.53248471e-01,  2.65903317e-01,  1.78026448e-02,
1.82980997e-01,  4.27422550e-01,  3.64008731e+00,  1.05696009e+01]),
array([746.80803112]),
28,
array([31.62777221, 26.8633118 , 23.77193056, 22.30260626, 20.62934119,
20.39983621, 19.79555279, 19.20858476, 18.31263277, 17.97404027,
17.5316525 , 16.89961264, 16.45070916, 15.9352539 , 15.59583452,
15.31077008, 14.99750352, 14.63024836, 13.98118247, 13.46476179,
13.10758039, 12.71374841, 12.56332451, 11.68258293, 10.86338553,
9.83811592,  8.95177506,  6.45127672]))
In :
x_lstsq = np.linalg.lstsq(A_learn,b_learn)

/tmp/ipykernel_76258/3904722398.py:1: FutureWarning: rcond parameter will change to the default of machine precision times max(M, N) where M and N are the input matrix dimensions.
To use the future default and silence this warning we advise to pass rcond=None, to keep using the old, explicitly pass rcond=-1.
x_lstsq = np.linalg.lstsq(A_learn,b_learn)

In :
x_lstsq

Out:
array([ 2.21118747e-02,  2.44244170e-02,  1.57703207e-02,  5.79639062e-02,
1.56997199e-01,  1.52433811e-01, -2.19629756e-01,  2.80629653e-02,
-1.42717475e-01, -1.42735887e-01, -1.02683521e-01, -9.49573125e-02,
-6.72715015e-03,  9.62766220e-02,  1.11278660e-01, -2.19567464e-01,
1.27339462e-01,  7.03440311e-02,  3.77977322e-01,  5.92079169e-02,
-1.35174789e-01, -1.53248471e-01,  2.65903317e-01,  1.78026448e-02,
1.82980997e-01,  4.27422550e-01,  3.64008731e+00,  1.05696009e+01])
In :
U,s,Vh = np.linalg.svd(A_learn,full_matrices=False)

In :
U.shape

Out:
(300, 28)
In :
x_svd = np.dot(np.dot(np.dot(Vh.T,np.diag(1/s)),U.T),b_learn)

In :
x_svd

Out:
array([ 2.21118747e-02,  2.44244170e-02,  1.57703207e-02,  5.79639062e-02,
1.56997199e-01,  1.52433811e-01, -2.19629756e-01,  2.80629653e-02,
-1.42717475e-01, -1.42735887e-01, -1.02683521e-01, -9.49573125e-02,
-6.72715015e-03,  9.62766220e-02,  1.11278660e-01, -2.19567464e-01,
1.27339462e-01,  7.03440311e-02,  3.77977322e-01,  5.92079169e-02,
-1.35174789e-01, -1.53248471e-01,  2.65903317e-01,  1.78026448e-02,
1.82980997e-01,  4.27422550e-01,  3.64008731e+00,  1.05696009e+01])
In :
np.linalg.norm(x_lstsq-x_svd)

Out:
7.988180666723686e-15

Store the solution of the minimization problem in a variable x_reg. The grade prediction for the students in the test set is simply $$p = A_{test} x_{reg} .$$

In :
x_reg = np.copy(x_lstsq)


Question c: The test matrix $A_{test}$ has $m_{test} = 95$ rows (students) and $n+1 = 28$ columns (features+intercept). Compare the predicted grades with the actual observed grades in $b_{test}$

In :
b_pred = A_test.dot(x_reg)

In :
print("Pred \tTrue")
for i in range(b_pred.size):
print("{:.0f}  \t{:.0f}".format(b_pred[i],b_test[i]))

Pred 	True
10  	11
11  	10
12  	14
18  	18
14  	13
12  	12
20  	18
9  	8
12  	12
11  	10
8  	0
12  	13
11  	11
11  	11
13  	13
11  	11
8  	0
9  	9
11  	10
11  	11
15  	13
9  	9
10  	11
14  	15
14  	15
11  	11
15  	16
10  	10
9  	9
14  	14
7  	8
13  	14
-1  	0
7  	0
8  	0
15  	15
15  	13
8  	0
15  	17
10  	10
11  	11
9  	0
15  	15
8  	0
10  	10
13  	14
16  	16
10  	9
15  	15
13  	13
7  	8
13  	13
5  	8
8  	8
11  	11
9  	9
13  	13
11  	11
10  	10
17  	16
13  	13
11  	12
11  	10
14  	15
11  	12
10  	10
12  	13
6  	0
10  	10
12  	11
6  	9
11  	12
10  	11
4  	5
18  	19
8  	10
15  	15
9  	10
15  	15
11  	10
14  	14
6  	7
10  	10
5  	0
5  	5
10  	10
4  	6
5  	0
8  	8
3  	0
10  	9
16  	16
9  	7
13  	10
8  	9


Question d: Compare the relative values of the coefficients of the predictor x_reg. What can you observe about the relative importance of the features in the prediction?

In :
for i,x in enumerate(x_reg):
print("{:d}\t{:.3f}".format(i+1,x))

1	0.022
2	0.024
3	0.016
4	0.058
5	0.157
6	0.152
7	-0.220
8	0.028
9	-0.143
10	-0.143
11	-0.103
12	-0.095
13	-0.007
14	0.096
15	0.111
16	-0.220
17	0.127
18	0.070
19	0.378
20	0.059
21	-0.135
22	-0.153
23	0.266
24	0.018
25	0.183
26	0.427
27	3.640
28	10.570


# 2- Singular Value Decomposition and Image Compression¶

The goal of this exercise is to investigate the computational aspects of the SVD; and, more importantly, observing the fact that the greater the magnitude of the singular value, the greater the importance of the associated vectors in the matrix coefficients. Investigating on this latter property will be done through the SVD of the following image seen as an array of grayscale values. In :
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import matplotlib.cm as cm
%matplotlib inline

#### IMAGE
img_gray =  0.2989 * img[:,:,0] + 0.5870 * img[:,:,1] + 0.1140 * img[:,:,2] # Apparently these are "good" coefficients to convert to grayscale
#########


To display an image from a matrix, you can use the matplotlib command imshow

In :
plt.imshow(img_gray, cmap = cm.Greys_r)

Out:
<matplotlib.image.AxesImage at 0x7ff3154f7850> Our goal is to investigate the significance of singular values as bearer of information for the represented image. To investigate this, we will zero 75% of the singular values of the matrix of the grayscale pixels.

Question a: How many singular values does img_gray have?

In :
img_gray.shape

Out:
(480, 640)
In :
U,s,Vh = np.linalg.svd(img_gray)

In :
len(s)

Out:
480
In :
np.linalg.matrix_rank(img_gray)

Out:
429
In :
s

Out:
array([1.62934189e+02, 2.41521511e+01, 2.00762005e+01, 1.70140228e+01,
1.42172527e+01, 1.27313280e+01, 1.22208471e+01, 1.02333879e+01,
9.48783112e+00, 8.03566456e+00, 7.44432831e+00, 6.45407772e+00,
6.42351913e+00, 6.05723715e+00, 5.40282917e+00, 5.20627785e+00,
5.08042526e+00, 4.71330214e+00, 4.40915823e+00, 4.33836842e+00,
4.05861187e+00, 3.89276600e+00, 3.57606959e+00, 3.48242426e+00,
3.47771430e+00, 3.20957446e+00, 3.11490202e+00, 2.92868638e+00,
2.82897282e+00, 2.75604391e+00, 2.65619540e+00, 2.58818793e+00,
2.33383203e+00, 2.29098654e+00, 2.24131513e+00, 2.16507411e+00,
2.05369735e+00, 1.99828827e+00, 1.92735314e+00, 1.88488162e+00,
1.82545531e+00, 1.76453578e+00, 1.73672128e+00, 1.66965055e+00,
1.61436272e+00, 1.58422875e+00, 1.54695439e+00, 1.53352308e+00,
1.47903979e+00, 1.38837266e+00, 1.35664225e+00, 1.32175910e+00,
1.31679225e+00, 1.28521657e+00, 1.22498906e+00, 1.21496940e+00,
1.18191719e+00, 1.15067828e+00, 1.11739492e+00, 1.07949066e+00,
1.04255116e+00, 1.01528823e+00, 1.00000238e+00, 9.72820163e-01,
9.37752783e-01, 9.27458167e-01, 9.06479239e-01, 8.85764718e-01,
8.77851844e-01, 8.47301185e-01, 8.26634347e-01, 8.15798283e-01,
7.82753706e-01, 7.73144782e-01, 7.61422753e-01, 7.36777663e-01,
7.24104345e-01, 7.03238368e-01, 6.96314156e-01, 6.76256657e-01,
6.56863511e-01, 6.49573624e-01, 6.43137336e-01, 6.36048138e-01,
6.25391722e-01, 6.07199073e-01, 5.95998108e-01, 5.81759036e-01,
5.67611933e-01, 5.57105184e-01, 5.46038151e-01, 5.40473700e-01,
5.28433919e-01, 5.25654972e-01, 5.05929351e-01, 4.96961564e-01,
4.87615794e-01, 4.79562432e-01, 4.72071588e-01, 4.65194076e-01,
4.64728773e-01, 4.46846306e-01, 4.41472232e-01, 4.31617320e-01,
4.22693551e-01, 4.15085047e-01, 4.07940954e-01, 4.00389940e-01,
3.95808905e-01, 3.82894695e-01, 3.70972365e-01, 3.62910867e-01,
3.61756831e-01, 3.51452261e-01, 3.46367419e-01, 3.42968345e-01,
3.38265330e-01, 3.32123965e-01, 3.24237347e-01, 3.22902143e-01,
3.17827374e-01, 3.14924479e-01, 3.04702103e-01, 3.00596565e-01,
2.94696838e-01, 2.90225744e-01, 2.85957009e-01, 2.80708998e-01,
2.73116589e-01, 2.69975424e-01, 2.67233133e-01, 2.61599988e-01,
2.60344654e-01, 2.57758707e-01, 2.53093034e-01, 2.48557597e-01,
2.42849186e-01, 2.40646496e-01, 2.38411665e-01, 2.33646780e-01,
2.31141374e-01, 2.26266190e-01, 2.24702597e-01, 2.17930466e-01,
2.15463787e-01, 2.10523918e-01, 2.07457215e-01, 2.04009429e-01,
2.01087728e-01, 1.95860803e-01, 1.92099631e-01, 1.90158457e-01,
1.85807139e-01, 1.83759421e-01, 1.82398587e-01, 1.81696206e-01,
1.80590749e-01, 1.75101772e-01, 1.72591433e-01, 1.69345707e-01,
1.67470470e-01, 1.66304797e-01, 1.64821163e-01, 1.62724197e-01,
1.60080537e-01, 1.55542344e-01, 1.55093744e-01, 1.52323246e-01,
1.51776880e-01, 1.49492905e-01, 1.47634536e-01, 1.44649953e-01,
1.41252443e-01, 1.38837919e-01, 1.37775823e-01, 1.36388049e-01,
1.34443909e-01, 1.32881641e-01, 1.30474225e-01, 1.27740353e-01,
1.25572428e-01, 1.24713637e-01, 1.22918196e-01, 1.22276500e-01,
1.20907024e-01, 1.18445821e-01, 1.17044196e-01, 1.16301805e-01,
1.12747163e-01, 1.12181745e-01, 1.10916935e-01, 1.09403200e-01,
1.08555175e-01, 1.07262336e-01, 1.06193833e-01, 1.04766846e-01,
1.03528798e-01, 1.00377910e-01, 9.90144163e-02, 9.80005264e-02,
9.68270600e-02, 9.68031436e-02, 9.56129506e-02, 9.31497216e-02,
9.22302157e-02, 9.09415334e-02, 8.92893448e-02, 8.82410258e-02,
8.66450146e-02, 8.63775536e-02, 8.49997699e-02, 8.45521018e-02,
8.32381472e-02, 8.23520795e-02, 8.09953362e-02, 7.99108669e-02,
7.66138062e-02, 7.60902315e-02, 7.56185204e-02, 7.33452141e-02,
7.27651492e-02, 7.24001154e-02, 7.14652091e-02, 7.10753500e-02,
6.94880560e-02, 6.88447356e-02, 6.84455708e-02, 6.77073300e-02,
6.59094602e-02, 6.54073805e-02, 6.44301102e-02, 6.37435466e-02,
6.27848804e-02, 6.11915700e-02, 6.05545677e-02, 5.95594570e-02,
5.92901632e-02, 5.85958995e-02, 5.74364923e-02, 5.68279140e-02,
5.62645234e-02, 5.58368713e-02, 5.55521324e-02, 5.46018519e-02,
5.38481586e-02, 5.29414564e-02, 5.25157116e-02, 5.12469187e-02,
5.10444306e-02, 5.06621860e-02, 4.95150462e-02, 4.87881489e-02,
4.82990704e-02, 4.73646559e-02, 4.71161418e-02, 4.63756807e-02,
4.60606031e-02, 4.55069579e-02, 4.46332544e-02, 4.38329652e-02,
4.34802696e-02, 4.33919206e-02, 4.26158682e-02, 4.25687023e-02,
4.19041589e-02, 4.18439060e-02, 4.12656181e-02, 4.02493440e-02,
3.98192964e-02, 3.95077951e-02, 3.93928103e-02, 3.87944244e-02,
3.85014936e-02, 3.83235998e-02, 3.79769132e-02, 3.75140607e-02,
3.71767767e-02, 3.67311165e-02, 3.66057940e-02, 3.61168832e-02,
3.56891863e-02, 3.54498141e-02, 3.53237092e-02, 3.50557901e-02,
3.48131172e-02, 3.42482552e-02, 3.41382362e-02, 3.40200849e-02,
3.38728279e-02, 3.37381028e-02, 3.35610695e-02, 3.32501791e-02,
3.31166834e-02, 3.26263458e-02, 3.23564596e-02, 3.21312249e-02,
3.20097208e-02, 3.17645408e-02, 3.16179991e-02, 3.14113759e-02,
3.11357770e-02, 3.10511384e-02, 3.08878124e-02, 3.06350086e-02,
3.05465348e-02, 3.02808732e-02, 2.98409332e-02, 2.96975449e-02,
2.96576582e-02, 2.95333378e-02, 2.91926544e-02, 2.88753230e-02,
2.87462994e-02, 2.85097994e-02, 2.83360761e-02, 2.82139871e-02,
2.81518921e-02, 2.77721565e-02, 2.76996791e-02, 2.74188817e-02,
2.73833070e-02, 2.73583997e-02, 2.72100363e-02, 2.69842185e-02,
2.66609062e-02, 2.66095772e-02, 2.64799334e-02, 2.61053108e-02,
2.58379821e-02, 2.57599931e-02, 2.57021710e-02, 2.55520754e-02,
2.52178833e-02, 2.49351393e-02, 2.49068588e-02, 2.48744898e-02,
2.45041605e-02, 2.43859310e-02, 2.43534576e-02, 2.42304970e-02,
2.40125451e-02, 2.38416083e-02, 2.36850474e-02, 2.35850178e-02,
2.34359857e-02, 2.33350378e-02, 2.32340507e-02, 2.30765529e-02,
2.29026396e-02, 2.27934457e-02, 2.26065740e-02, 2.24429648e-02,
2.23109704e-02, 2.22124960e-02, 2.19505429e-02, 2.19187364e-02,
2.17535552e-02, 2.16454733e-02, 2.15567090e-02, 2.13723555e-02,
2.12524273e-02, 2.11992450e-02, 2.10752152e-02, 2.08681636e-02,
2.05656290e-02, 2.04927083e-02, 2.03190148e-02, 2.02912204e-02,
2.01020073e-02, 1.98616926e-02, 1.98098980e-02, 1.97105259e-02,
1.95980668e-02, 1.94427371e-02, 1.93745904e-02, 1.92371048e-02,
1.89938489e-02, 1.89657453e-02, 1.86659936e-02, 1.85321625e-02,
1.84689816e-02, 1.83426291e-02, 1.83082428e-02, 1.81911848e-02,
1.80462413e-02, 1.79338437e-02, 1.77577455e-02, 1.75750628e-02,
1.73917823e-02, 1.73133928e-02, 1.72254462e-02, 1.70100834e-02,
1.69985890e-02, 1.69629287e-02, 1.65927205e-02, 1.65382214e-02,
1.64936874e-02, 1.63189527e-02, 1.62624270e-02, 1.60032213e-02,
1.59194637e-02, 1.57861561e-02, 1.55710457e-02, 1.55141838e-02,
1.54828038e-02, 1.54213849e-02, 1.53106637e-02, 1.50422752e-02,
1.49266897e-02, 1.47630218e-02, 1.46441162e-02, 1.45366406e-02,
1.44718569e-02, 1.43201165e-02, 1.42147681e-02, 1.40904626e-02,
1.39762927e-02, 1.39130028e-02, 1.37424413e-02, 1.37180863e-02,
1.34768728e-02, 1.33709963e-02, 1.32721262e-02, 1.30652962e-02,
1.29355080e-02, 1.28526129e-02, 1.25789884e-02, 1.25682391e-02,
1.24526694e-02, 1.23342182e-02, 1.21436026e-02, 1.20447287e-02,
1.19034564e-02, 1.17551573e-02, 1.16961366e-02, 1.16546061e-02,
1.15772812e-02, 1.13544371e-02, 1.11528672e-02, 1.10750981e-02,
1.10018887e-02, 1.07716704e-02, 1.06261997e-02, 1.05332723e-02,
1.03939790e-02, 1.03147393e-02, 1.01760728e-02, 1.00988848e-02,
9.90787707e-03, 9.89310816e-03, 9.76674259e-03, 9.59912594e-03,
9.32480115e-03, 9.24131926e-03, 9.04235244e-03, 9.01850220e-03,
8.88617150e-03, 8.81741196e-03, 8.70393682e-03, 8.42054654e-03,
8.34246073e-03, 8.07079766e-03, 7.94494804e-03, 7.80721381e-03,
7.67743681e-03, 7.59434653e-03, 7.49550899e-03, 7.43582239e-03,
7.26346998e-03, 7.01179588e-03, 6.90957485e-03, 6.73384173e-03,
6.63539488e-03, 6.54417882e-03, 6.36292202e-03, 6.19272655e-03,
6.05892390e-03, 5.98990824e-03, 5.80914877e-03, 5.32500772e-03],
dtype=float32)

Store in a variable n_zero the number of singular values that we will change, ie. 75% of the total number.

Question b: Compute the SVD of the grayscale image img_gray. Generate new images (matrices of grayscale pixels) by changing the singular values in the original as follows:

1. Put to zero the n_zero smallest singular values 2.Put to zero the n_zero greatest singular values
2. Put to zero n_zero singular values at random

Compare the resulting images. What can you conclude about the relative importance of the singular values?

In :
U,s,Vh = np.linalg.svd(img_gray,full_matrices=False)

In :
n_zero = int(0.75*len(s))
n_zero

Out:
360
In :
# 1 smallest
s_small = np.copy(s)
s_small[len(s)-n_zero:] = 0.0
s_small

Out:
array([162.93419   ,  24.152151  ,  20.0762    ,  17.014023  ,
14.217253  ,  12.731328  ,  12.220847  ,  10.233388  ,
9.487831  ,   8.035665  ,   7.4443283 ,   6.4540777 ,
6.423519  ,   6.057237  ,   5.402829  ,   5.206278  ,
5.0804253 ,   4.713302  ,   4.409158  ,   4.3383684 ,
4.058612  ,   3.892766  ,   3.5760696 ,   3.4824243 ,
3.4777143 ,   3.2095745 ,   3.114902  ,   2.9286864 ,
2.8289728 ,   2.756044  ,   2.6561954 ,   2.588188  ,
2.333832  ,   2.2909865 ,   2.2413151 ,   2.165074  ,
2.0536973 ,   1.9982883 ,   1.9273531 ,   1.8848816 ,
1.8254553 ,   1.7645358 ,   1.7367213 ,   1.6696506 ,
1.6143627 ,   1.5842288 ,   1.5469544 ,   1.5335231 ,
1.4790398 ,   1.3883727 ,   1.3566422 ,   1.3217591 ,
1.3167922 ,   1.2852166 ,   1.224989  ,   1.2149694 ,
1.1819172 ,   1.1506783 ,   1.1173949 ,   1.0794907 ,
1.0425512 ,   1.0152882 ,   1.0000024 ,   0.97282016,
0.9377528 ,   0.92745817,   0.90647924,   0.8857647 ,
0.87785184,   0.8473012 ,   0.82663435,   0.8157983 ,
0.7827537 ,   0.7731448 ,   0.76142275,   0.73677766,
0.72410434,   0.70323837,   0.69631416,   0.67625666,
0.6568635 ,   0.6495736 ,   0.64313734,   0.63604814,
0.6253917 ,   0.6071991 ,   0.5959981 ,   0.58175904,
0.56761193,   0.5571052 ,   0.54603815,   0.5404737 ,
0.5284339 ,   0.525655  ,   0.50592935,   0.49696156,
0.4876158 ,   0.47956243,   0.4720716 ,   0.46519408,
0.46472877,   0.4468463 ,   0.44147223,   0.43161732,
0.42269355,   0.41508505,   0.40794095,   0.40038994,
0.3958089 ,   0.3828947 ,   0.37097237,   0.36291087,
0.36175683,   0.35145226,   0.34636742,   0.34296834,
0.33826533,   0.33212397,   0.32423735,   0.32290214,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ,
0.        ,   0.        ,   0.        ,   0.        ],
dtype=float32)
In :
img_small = np.dot(U, np.dot(np.diag(s_small), Vh))

In :
# 2 greatest
s_great = np.copy(s)
s_great[:n_zero] = 0.0
s_great

Out:
array([0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.        , 0.        , 0.        , 0.        , 0.        ,
0.02125243, 0.02119925, 0.02107522, 0.02086816, 0.02056563,
0.02049271, 0.02031901, 0.02029122, 0.02010201, 0.01986169,
0.0198099 , 0.01971053, 0.01959807, 0.01944274, 0.01937459,
0.0192371 , 0.01899385, 0.01896575, 0.01866599, 0.01853216,
0.01846898, 0.01834263, 0.01830824, 0.01819118, 0.01804624,
0.01793384, 0.01775775, 0.01757506, 0.01739178, 0.01731339,
0.01722545, 0.01701008, 0.01699859, 0.01696293, 0.01659272,
0.01653822, 0.01649369, 0.01631895, 0.01626243, 0.01600322,
0.01591946, 0.01578616, 0.01557105, 0.01551418, 0.0154828 ,
0.01542138, 0.01531066, 0.01504228, 0.01492669, 0.01476302,
0.01464412, 0.01453664, 0.01447186, 0.01432012, 0.01421477,
0.01409046, 0.01397629, 0.013913  , 0.01374244, 0.01371809,
0.01347687, 0.013371  , 0.01327213, 0.0130653 , 0.01293551,
0.01285261, 0.01257899, 0.01256824, 0.01245267, 0.01233422,
0.0121436 , 0.01204473, 0.01190346, 0.01175516, 0.01169614,
0.01165461, 0.01157728, 0.01135444, 0.01115287, 0.0110751 ,
0.01100189, 0.01077167, 0.0106262 , 0.01053327, 0.01039398,
0.01031474, 0.01017607, 0.01009888, 0.00990788, 0.00989311,
0.00976674, 0.00959913, 0.0093248 , 0.00924132, 0.00904235,
0.0090185 , 0.00888617, 0.00881741, 0.00870394, 0.00842055,
0.00834246, 0.0080708 , 0.00794495, 0.00780721, 0.00767744,
0.00759435, 0.00749551, 0.00743582, 0.00726347, 0.0070118 ,
0.00690957, 0.00673384, 0.00663539, 0.00654418, 0.00636292,
0.00619273, 0.00605892, 0.00598991, 0.00580915, 0.00532501],
dtype=float32)
In :
img_great = np.dot(U, np.dot(np.diag(s_great), Vh))

In :
# 3 random
s_random = np.copy(s)
s_random[np.random.randint(0,len(s),n_zero)] = 0.0
s_random

Out:
array([0.00000000e+00, 2.41521511e+01, 2.00762005e+01, 1.70140228e+01,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 1.02333879e+01,
0.00000000e+00, 8.03566456e+00, 7.44432831e+00, 6.45407772e+00,
0.00000000e+00, 6.05723715e+00, 0.00000000e+00, 5.20627785e+00,
5.08042526e+00, 0.00000000e+00, 0.00000000e+00, 4.33836842e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 3.48242426e+00,
3.47771430e+00, 3.20957446e+00, 0.00000000e+00, 2.92868638e+00,
2.82897282e+00, 0.00000000e+00, 2.65619540e+00, 2.58818793e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 2.16507411e+00,
2.05369735e+00, 1.99828827e+00, 0.00000000e+00, 1.88488162e+00,
1.82545531e+00, 0.00000000e+00, 1.73672128e+00, 1.66965055e+00,
1.61436272e+00, 1.58422875e+00, 1.54695439e+00, 1.53352308e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 1.32175910e+00,
1.31679225e+00, 0.00000000e+00, 0.00000000e+00, 1.21496940e+00,
1.18191719e+00, 1.15067828e+00, 1.11739492e+00, 1.07949066e+00,
1.04255116e+00, 0.00000000e+00, 1.00000238e+00, 9.72820163e-01,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 8.85764718e-01,
0.00000000e+00, 8.47301185e-01, 0.00000000e+00, 8.15798283e-01,
7.82753706e-01, 7.73144782e-01, 7.61422753e-01, 0.00000000e+00,
7.24104345e-01, 0.00000000e+00, 0.00000000e+00, 6.76256657e-01,
0.00000000e+00, 0.00000000e+00, 6.43137336e-01, 0.00000000e+00,
6.25391722e-01, 0.00000000e+00, 5.95998108e-01, 0.00000000e+00,
5.67611933e-01, 0.00000000e+00, 5.46038151e-01, 0.00000000e+00,
0.00000000e+00, 5.25654972e-01, 0.00000000e+00, 4.96961564e-01,
0.00000000e+00, 4.79562432e-01, 0.00000000e+00, 0.00000000e+00,
4.64728773e-01, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 4.15085047e-01, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 3.82894695e-01, 3.70972365e-01, 3.62910867e-01,
0.00000000e+00, 0.00000000e+00, 3.46367419e-01, 0.00000000e+00,
3.38265330e-01, 3.32123965e-01, 0.00000000e+00, 0.00000000e+00,
3.17827374e-01, 0.00000000e+00, 3.04702103e-01, 0.00000000e+00,
0.00000000e+00, 2.90225744e-01, 2.85957009e-01, 0.00000000e+00,
2.73116589e-01, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
2.42849186e-01, 0.00000000e+00, 2.38411665e-01, 2.33646780e-01,
0.00000000e+00, 0.00000000e+00, 2.24702597e-01, 0.00000000e+00,
2.15463787e-01, 2.10523918e-01, 2.07457215e-01, 0.00000000e+00,
2.01087728e-01, 1.95860803e-01, 1.92099631e-01, 1.90158457e-01,
1.85807139e-01, 1.83759421e-01, 1.82398587e-01, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 1.69345707e-01,
0.00000000e+00, 0.00000000e+00, 1.64821163e-01, 1.62724197e-01,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
1.51776880e-01, 0.00000000e+00, 1.47634536e-01, 1.44649953e-01,
1.41252443e-01, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
1.34443909e-01, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
1.25572428e-01, 0.00000000e+00, 1.22918196e-01, 1.22276500e-01,
0.00000000e+00, 1.18445821e-01, 1.17044196e-01, 1.16301805e-01,
1.12747163e-01, 0.00000000e+00, 1.10916935e-01, 1.09403200e-01,
1.08555175e-01, 0.00000000e+00, 1.06193833e-01, 1.04766846e-01,
0.00000000e+00, 1.00377910e-01, 9.90144163e-02, 0.00000000e+00,
9.68270600e-02, 9.68031436e-02, 9.56129506e-02, 0.00000000e+00,
9.22302157e-02, 9.09415334e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 8.49997699e-02, 0.00000000e+00,
8.32381472e-02, 8.23520795e-02, 8.09953362e-02, 0.00000000e+00,
7.66138062e-02, 0.00000000e+00, 7.56185204e-02, 0.00000000e+00,
7.27651492e-02, 7.24001154e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 6.88447356e-02, 6.84455708e-02, 0.00000000e+00,
6.59094602e-02, 0.00000000e+00, 6.44301102e-02, 0.00000000e+00,
6.27848804e-02, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 5.85958995e-02, 0.00000000e+00, 5.68279140e-02,
5.62645234e-02, 0.00000000e+00, 5.55521324e-02, 0.00000000e+00,
0.00000000e+00, 5.29414564e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 5.06621860e-02, 4.95150462e-02, 4.87881489e-02,
4.82990704e-02, 4.73646559e-02, 4.71161418e-02, 4.63756807e-02,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 4.33919206e-02, 0.00000000e+00, 0.00000000e+00,
4.19041589e-02, 4.18439060e-02, 4.12656181e-02, 0.00000000e+00,
0.00000000e+00, 3.95077951e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 3.83235998e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 3.67311165e-02, 3.66057940e-02, 3.61168832e-02,
3.56891863e-02, 3.54498141e-02, 3.53237092e-02, 3.50557901e-02,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 3.40200849e-02,
0.00000000e+00, 3.37381028e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 3.26263458e-02, 0.00000000e+00, 3.21312249e-02,
0.00000000e+00, 3.17645408e-02, 0.00000000e+00, 3.14113759e-02,
3.11357770e-02, 3.10511384e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 3.02808732e-02, 0.00000000e+00, 0.00000000e+00,
2.96576582e-02, 0.00000000e+00, 0.00000000e+00, 2.88753230e-02,
0.00000000e+00, 0.00000000e+00, 2.83360761e-02, 0.00000000e+00,
2.81518921e-02, 2.77721565e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
2.66609062e-02, 2.66095772e-02, 2.64799334e-02, 0.00000000e+00,
0.00000000e+00, 2.57599931e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 2.49068588e-02, 2.48744898e-02,
0.00000000e+00, 2.43859310e-02, 0.00000000e+00, 2.42304970e-02,
2.40125451e-02, 2.38416083e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 2.32340507e-02, 0.00000000e+00,
2.29026396e-02, 0.00000000e+00, 2.26065740e-02, 0.00000000e+00,
0.00000000e+00, 2.22124960e-02, 2.19505429e-02, 2.19187364e-02,
2.17535552e-02, 0.00000000e+00, 2.15567090e-02, 2.13723555e-02,
2.12524273e-02, 0.00000000e+00, 2.10752152e-02, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 2.02912204e-02,
0.00000000e+00, 1.98616926e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 1.94427371e-02, 1.93745904e-02, 0.00000000e+00,
0.00000000e+00, 1.89657453e-02, 0.00000000e+00, 1.85321625e-02,
1.84689816e-02, 0.00000000e+00, 1.83082428e-02, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 1.69629287e-02, 0.00000000e+00, 1.65382214e-02,
1.64936874e-02, 1.63189527e-02, 1.62624270e-02, 0.00000000e+00,
0.00000000e+00, 1.57861561e-02, 1.55710457e-02, 1.55141838e-02,
1.54828038e-02, 1.54213849e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 1.47630218e-02, 1.46441162e-02, 1.45366406e-02,
0.00000000e+00, 1.43201165e-02, 0.00000000e+00, 0.00000000e+00,
1.39762927e-02, 0.00000000e+00, 0.00000000e+00, 1.37180863e-02,
1.34768728e-02, 0.00000000e+00, 1.32721262e-02, 0.00000000e+00,
1.29355080e-02, 1.28526129e-02, 0.00000000e+00, 0.00000000e+00,
1.24526694e-02, 1.23342182e-02, 0.00000000e+00, 0.00000000e+00,
0.00000000e+00, 1.17551573e-02, 1.16961366e-02, 0.00000000e+00,
0.00000000e+00, 1.13544371e-02, 0.00000000e+00, 1.10750981e-02,
1.10018887e-02, 0.00000000e+00, 0.00000000e+00, 1.05332723e-02,
0.00000000e+00, 1.03147393e-02, 0.00000000e+00, 0.00000000e+00,
9.90787707e-03, 9.89310816e-03, 9.76674259e-03, 9.59912594e-03,
0.00000000e+00, 9.24131926e-03, 0.00000000e+00, 9.01850220e-03,
8.88617150e-03, 8.81741196e-03, 0.00000000e+00, 8.42054654e-03,
0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 7.80721381e-03,
7.67743681e-03, 0.00000000e+00, 7.49550899e-03, 7.43582239e-03,
0.00000000e+00, 7.01179588e-03, 0.00000000e+00, 0.00000000e+00,
6.63539488e-03, 6.54417882e-03, 6.36292202e-03, 0.00000000e+00,
6.05892390e-03, 0.00000000e+00, 0.00000000e+00, 5.32500772e-03],
dtype=float32)
In :
img_random = np.dot(U, np.dot(np.diag(s_random), Vh))

In :
plt.figure()

plt.subplot(2,2,1)
plt.imshow(img_gray, cmap = cm.Greys_r)
plt.title("Original")
plt.xticks([]),plt.yticks([])

plt.subplot(2,2,2)
plt.imshow(img_small, cmap = cm.Greys_r)
plt.title("Smallest removed")
plt.xticks([]),plt.yticks([])

plt.subplot(2,2,3)
plt.imshow(img_great, cmap = cm.Greys_r)
plt.title("Greatest removed")
plt.xticks([]),plt.yticks([])

plt.subplot(2,2,4)
plt.imshow(img_random, cmap = cm.Greys_r)
plt.title("Random removed")
plt.xticks([]),plt.yticks([])

plt.show() Question c: Compute the sum of the singular values for the original and modified images. What can you conclude about the visual information provided by the singular values?

In :
print("\t\t\t Orig. \t Smallest removed \t Greatest removed \t Random")
print("Sing. val. sum: \t{:3.1f} \t {:3.1f} \t\t\t {:3.1f} \t\t\t {:3.1f}".format(sum(s),sum(s_small),sum(s_great),sum(s_random)))
print("Percentage: \t\t{:3.1f} \t {:3.1f} \t\t\t {:3.1f} \t\t\t {:3.1f}".format(sum(s)/sum(s)*100,sum(s_small)/sum(s)*100,sum(s_great)/sum(s)*100,sum(s_random)/sum(s)*100))

			 Orig. 	 Smallest removed 	 Greatest removed 	 Random
Sing. val. sum: 	489.5 	 466.2 			 1.6 			 191.4
Percentage: 		100.0 	 95.3 			 0.3 			 39.1


# 3- PageRank and the Power Method¶

In this part, we will compute the PageRank ordering of the following graph. In PageRank, the score $x_i$ of page $i$ is equal to the sum over the pages $j$ pointing toward $i$ of their scores $x_j$ divided by their number of outgoing links $n_j$. This leads to a ranking matrix $R$ defined from the scoring method as $$x = Rx.$$

In :
import numpy as np
import matplotlib.pyplot as plt

#### Graph matrix
A = np.array([[0,1,1,0,1],[0,0,0,1,1],[1,0,0,1,0],[0,0,1,0,1],[0,1,0,0,0]])
####


Question a: Explain how the ranking matrix $R$ is generated from adjacence matrix $A$ in the following code.

In :
R = np.dot( A  , np.diag(1.0/np.sum(A,0)) )

In :
R

Out:
array([[0.        , 0.5       , 0.5       , 0.        , 0.33333333],
[0.        , 0.        , 0.        , 0.5       , 0.33333333],
[1.        , 0.        , 0.        , 0.5       , 0.        ],
[0.        , 0.        , 0.5       , 0.        , 0.33333333],
[0.        , 0.5       , 0.        , 0.        , 0.        ]])

Question b: Check numerically that $\|R\| = 1$ for some matrix norm and that the spectral radius of $R$ is equal to $1$.

In :
np.linalg.norm(R)

Out:
1.6832508230603465
In :
np.linalg.norm(R,1)

Out:
1.0
In :
max(abs(np.linalg.eigvals(R)))

Out:
0.9999999999999997

Question c: Iterate the matrix $R$ a large number of times and check if the matrix is primitive. What do you notice on the eigenvalues and eigenvectors? How is defined the rank 1 matrix that you obtain? This manner of computing eigenvectors/values is called the power method.

In :
np.linalg.matrix_power(R,100)

Out:
array([[0.26002337, 0.25999364, 0.25997878, 0.26001519, 0.25998818],
[0.11998832, 0.12000318, 0.12001061, 0.11999241, 0.12000591],
[0.35996495, 0.36000954, 0.36003184, 0.35997722, 0.36001772],
[0.20001694, 0.19999539, 0.19998462, 0.20001101, 0.19999144],
[0.06000643, 0.05999825, 0.05999416, 0.06000418, 0.05999675]])
In :
np.all(np.linalg.matrix_power(R,100)>0.0)

Out:
True

Question d: Recover the Perron eigenvector of matrix $R$. The entries of this vector are the PageRank scores of the nodes/pages of the graph. Give the PageRank ordering of the pages of the graph.

In :
R1000 = np.linalg.matrix_power(R,1000)

In :
R1000

Out:
array([[0.26, 0.26, 0.26, 0.26, 0.26],
[0.12, 0.12, 0.12, 0.12, 0.12],
[0.36, 0.36, 0.36, 0.36, 0.36],
[0.2 , 0.2 , 0.2 , 0.2 , 0.2 ],
[0.06, 0.06, 0.06, 0.06, 0.06]])
In :
v = R1000[:,0]
v

Out:
array([0.26, 0.12, 0.36, 0.2 , 0.06]) In this exercise, the graph we took led to a primitive matrix as seen above; this is necessary for the power method to work as the eigenvalue $1$ has to be the only one of modulus $1$. This is actually the case when the graph is strongly connected, that is when you can go from any node to any other node by following the edges. When this is not the case, our problem becomes ill posed. To overcome this problem, the ranking matrix $R$ is replaced by $$M = (1-\alpha) R + \alpha J, ~~~~~~~~ \alpha\in]0,1[$$ where is $J$ is the $5\times 5$ matrix whose entries are all $1/5$. The value of $\alpha$ originally used by Google is $0.15$.

Question e: Suppress the link from $2$ to $5$.

• Show that $M$ is column-stochastic provided that $R$ is.
• Show that the problem with $M$ is now well-posed.
• Compute the ranking for this graph.
In :
A_new = A
A_new[4,1]=0

In :
A_new

Out:
array([[0, 1, 1, 0, 1],
[0, 0, 0, 1, 1],
[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 0, 0]])
In :
R_new = np.dot( A_new , np.diag(1.0/np.sum(A_new,0)) )
R_new

Out:
array([[0.        , 1.        , 0.5       , 0.        , 0.33333333],
[0.        , 0.        , 0.        , 0.5       , 0.33333333],
[1.        , 0.        , 0.        , 0.5       , 0.        ],
[0.        , 0.        , 0.5       , 0.        , 0.33333333],
[0.        , 0.        , 0.        , 0.        , 0.        ]])
In :
M = (1-0.15)*R_new + 0.15/5
M

Out:
array([[0.03      , 0.88      , 0.455     , 0.03      , 0.31333333],
[0.03      , 0.03      , 0.03      , 0.455     , 0.31333333],
[0.88      , 0.03      , 0.03      , 0.455     , 0.03      ],
[0.03      , 0.03      , 0.455     , 0.03      , 0.31333333],
[0.03      , 0.03      , 0.03      , 0.03      , 0.03      ]])
In :
v_new = np.linalg.matrix_power(M,1000)[:,0]
v_new

Out:
array([0.29478388, 0.1203182 , 0.3623845 , 0.19251341, 0.03      ])
In :
v

Out:
array([0.26, 0.12, 0.36, 0.2 , 0.06])