**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 [ ]:
```

**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 [ ]:
```

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 [ ]:
```

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)

```
```

```
In [14]:
```2./100**3*14000**3/1000/60

```
Out[14]:
```

```
In [ ]:
```