Problem 1 (Theoretical tasks)

LU decomposition 4 pts

Calculate number of operations to get the LU decomposition
How many operations are required to solve a linear system with a matrix given by its LU decomposition?
Is it possible to solve $1\ 000\ 000 \times 1\ 000\ 000$ dense linear system on your laptop within 1 month via LU decomposition?

Eigenvalues 4 pts

Squared matrix $A$ is called diagonalizable if there exists matrix $S$ such that $\Lambda = S^{-1} A S$ is a diagonal matrix. Prove that if matrix is diagonalizable, then $\Lambda$ has eigenvalues on a diagonal and $S$ consists of eigenvectors of $A$
Give example of a matrix which can not be diagonalized. What classes of diagonalizable matrices do you know?
Prove that $\lambda(A) \in \mathbb{R}^1$ if $A$ is Hermitian, $\lambda(A)$ has only imaginary part if $A$ is skew-Hermitian and $\vert \lambda(A) \vert = 1$ if $A$ is unitary

Neumann series 4 pts

Prove that for every $A$: $\|A\| < 1$ holds $$\|(I - A)^{-1}\| \leqslant \frac{\|I\|}{1 - \|A\|}$$
Prove that for small perturbation $\Delta A$ and $\Delta f$ of $A$ and $f$ in the linear system $Ax = f$ holds $$\frac{\Vert \Delta x \Vert}{\Vert x \Vert} \leqslant \frac{\Vert A \Vert \Vert A^{-1} \Vert}{1 - \Vert A\Vert \Vert A^{-1}\Vert \frac{\Vert\Delta A\Vert}{\Vert A\Vert}}\left(\frac{\Vert\Delta A\Vert}{\Vert A \Vert} + \frac{\Vert \Delta f \Vert}{ \Vert f \Vert}\right)$$ What role does $\|A\|\|A^{-1}\|$ play here?

SVD tool 4 pts

Prove that $\|A\|_2 = \sigma_1(A) \equiv \sqrt{\lambda_\text{max} (A^*A)}$ and $ \|A\|_F = (\sigma_1^2 + \dots + \sigma_r^2)^{1/2} $
Find optimal constants $c_1$ and $c_2$ such that $c_1 \|A\|_2 \leqslant \|A\|_F \leqslant c_2 \|A\|_2$ (matrix norm equivalence)
What is the distance between nonsingular matrix A and the nearest (in terms of the second norm) singular?



In [ ]:

Problem 2 (PageRank)

Connected graph 5 pts

Create an $n\times n$ (n = 100) matrix which corresponds to a random connected. The graph should correspond to the PageRank model
Implement power method and find PageRank of the resulting graph. Plot convergence rate of the method

Disconnected graph 6 pts

Create an $n\times n$ (n = 200) matrix which corresponds to a random disconnected graph that consists of two connected graphs for PageRank. What is the multiplicity of the eigenvalue $\lambda = 1$?
To avoid $\lambda = 1$ degeneration regularize the obtained matrix by multipling it by $1-d$ and by adding $\verb|d/n * ones((n,n))|$, where $d$ is a small parameter ($\sim 0.15$) and $n\times n$ is a size of the graph matrix
Find PageRank via power method. Plot convergence rate of the method for different $d$. Give comments on the convergence



In [ ]:

Problem 3 (Eigenfaces) 12 pts

The aim of this task is to build a face classifier. There are 40 persons in the database. Every person is represented by 10 photos with slightly different facial expression.

Download the database of faces from here
Create training sample.

Import first 9 images for each face ($9\times 40$ images). Represent these pictures as a matrix $F$ with $9\times 40$ columns, where each column is a reshaped 2D picture. Note: use $\verb|np.reshape|$ to reshape matrix into column

Calculate and plot mean face. Subtract it from each column of the matrix $F$
Calculate SVD decomposition of the shifted matrix F and truncate the obtained representaition with first $r$ columns: $U_r S_r V_r^T$.

Here $U_r$ is a matrix with $r$ columns - basis set in a space of faces. $W_r = S_r V_r^T$ is a matrix of coefficients in the basis $U_r$. Note that rank $r$ is a parameter which controls quality of classification. Note: parameter $\verb|full_matrices|$ in $\verb|np.linalg.svd|$ might be helpful

Plot $U_r$ vectors. Make sure to get face-like images. Remark: now you know what eigenfaces are =)
Import testing set which is the rest of photos. Find their coefficients in the basis $U_r$
Compare the calculated vectors of coefficients to vectors in $W_r$ and classify testing faces. As an output give indices of faces that were misclassified.

Similarity of faces is defined by their coefficients similarity which in turn is measured by angle.



In [ ]:

Problem 4 (HOSVD) bonus task

Implement High-Order SVD (HOSVD) algorithm in 3D. As an output give ranks of the 3D Hilbert tensor $$a_{ijk} = \frac{1}{i+j+k + 1}, \quad i,j,k = \overline{0,199}$$ with $10^{-5}$ accuracy. Details can be found here (Fig. 4.3)



In [10]:

    
import numpy as np
a = np.random.random((200,200))
%timeit np.linalg.svd(a)









    



100 loops, best of 3: 10.7 ms per loop



In [14]:

    
2./100**3*14000**3/1000/60









    Out[14]:





91.46666666666667



In [ ]: