### Note¶

• All items of problems in problem sets should be done in seperate cells.
• Do not forget to include title, labels of each line and set axis names for every figure you plot.
• If most part of your plot is very close to $0$, it might be a good idea to use logarithmic scale.
• You can submit incomplete problems. They will be graded as well.

# Problem 1 (Fast Fourier transform)¶

## 25 pts¶

• Implement matrix version of the Cooley-Tukey FFT algorithm (see lecture 4). This means that your goal is to write a function that has vector as an input and its discrete Fourier transform as an output. Make sure that your algorithm does not utilize full matrices and your complexity is $\mathcal{O}(n \log n)$. For simplicity consider that $n$ is a power of $2$

• Compare timings of your algorithm with those of np.dot and np.fft.fft by plotting timings as a function of $n$. Was it a good idea to implement your own version of the FFT? :)

• The overall complexity of FFT algorithm is $\mathcal{O}(n \log n)$. Find analytically constant hidden in $\mathcal{O}(\cdot)$ for the Cooley-Tukey version.

In [ ]:



# Problem 2 (Strassen algorithm)¶

## 25 pts¶

• Implement Strassen algorithm. For simplicity consider that n is a power of 2
• Compare your implementation the Strassen algorithm with direct matrix-matrix multiplication using loops and 𝚗p.𝚍𝚘𝚝 function by ploting timings as a function of $n$.

It might be a good idea not to do recursion in the Strassen algorithm to the bottom level. Sometimes only several levels of the recursion are used. This helps to reduce a constant outside $n^3$.

• Find analytically constant outside $n^3$ after $2$ levels of the Strassen algorithm. Compare it with $2n^3$ in the naive version.
In [ ]:



# Problem 3 (Fast convolution)¶

## 30 pts¶

#### 1D¶

• Implement fast multiplication of a Toeplitz matrix by a given vector with $\mathcal{O}(n \log n)$ complexity. Make sure that you do not form the Toeplitz matrix itself!

• Now you are able to implement Problem 1 from the Problem Set 1 without truncating the signal. Convolve your signal with the filter $T$ using your fast multiplication algorithm (set $\alpha=\frac{1}{20}$). Play the signal.

#### 2D¶

• Find convolution of the Lena $n\times n$ image and the following filter $$T_{i_1j_1i_2j_2} \equiv T_{i_1-j_1,i_2-j_2} = \frac{\alpha}{\pi} e^{-\alpha \left[(i_1 - j_1)^2 + (i_2 - j_2)^2 \right]}, \quad i_1,j_1, i_2, j_2 = 1,\dots, n, \quad \alpha = \frac{1}{50}$$ with $\mathcal{O}(n^2 \log n^2)$ complexity. Plot the resulting image (plt.imshow might be helpful for this task). What is the complexity of naive summation?
In [ ]:



# Problem 4 (SVD intro)¶

## 20 pts¶

• Find SVD decomposition of the Lena image and plot its singular values.
• Compress the image using trunction of singular values. Plot compressed images for several $r$ ($r$ is a number of remaining singular values). Specify in titles of images compression rate. Note: do not forget to use plt.subplots.
In [ ]:



# Bonus Problem (HOSVD)¶

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 = 0,\dots, 199$$ with $10^{-5}$ accuracy. Details can be found here on Figure 4.3.

In [ ]: