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.
  • Bonus tasks are challenging and non-obligatory. However, they may help you with your final grade.

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