{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"id": "60552e92",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [],
"source": [
"# Initialize Otter\n",
"import otter\n",
"grader = otter.Notebook(\"Linear transforms.ipynb\")"
]
},
{
"cell_type": "markdown",
"id": "73bbe3f2-6e0a-463e-abc6-01213d4e5811",
"metadata": {
"tags": []
},
"source": [
"# Matrix Analysis 2025 - EE312\n",
"## Week 2 - Linear transforms\n",
"[N. Aspert](https://people.epfl.ch/nicolas.aspert) - [LTS2](https://lts2.epfl.ch)\n",
"\n",
"The first week notebook (introduction to Python, Numpy and Matplotlib) can be used as a help.\n",
"\n",
"## Objective\n",
"\n",
"The end goal is to understand purely algebraic, matrix based, view of a few linear transforms. You will use those linear transform to perform some basic time-frequency analysis of signals."
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "9e522683-69ce-458f-a78c-9780e07a865e",
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "markdown",
"id": "5901baaa-4eb1-446a-8c0b-88369a9e213e",
"metadata": {},
"source": [
"## Part I - Fourier"
]
},
{
"cell_type": "markdown",
"id": "7e81811f-e9c9-4d57-bbb9-bee71b7df722",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"1. Prove that any set of orthogonal vectors $v_i \\in \\mathbb{C}^N, \\, i=1, \\ldots , M \\leq N$ such that $v_i^H v_j = C \\delta_{i,j}$ is linearly independent (where $C$ is some constant)."
]
},
{
"cell_type": "markdown",
"id": "b6087a12",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "5d9c0799-a145-4b31-b8a7-3dc6d9fcf6da",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"We have a set of orthogonal vectors $v_i \\in \\mathbb{C}^N,$ with $i=1, \\ldots , M \\leq N$.\\\n",
"Therefore, $v_i^H v_j = C \\delta_{i,j} =\\left\\{\\begin{matrix}\n",
" C,& if & i=j\\\\ \n",
" 0,& if & i\\neq j\n",
"\\end{matrix}\\right.$.<br/>\n",
"\n",
"We want to prove that the set is linearly independent, in other words that we have, with $c_{i}$ some scalar, \\\n",
"$\\sum_{j = 1}^{N} c_{j}.v_{j} = 0 \\Leftrightarrow c_{j} = 0$.<br/><br/><br/>\n",
"Let's start, we can write:\\\n",
"$v_{i}^H. (\\sum_{j = 1}^{N}c_{j}.v_{j}) = v_{i}.0 = 0$<br/><br/>\n",
"Therefore,\\\n",
"$0 = v_{i}^H. (\\sum_{j = 1}^{N}c_{j}.v_{j}) =\\sum_{j = 1}^{N}c_{j}.v_{j}.v_{i}^H$<br/><br/>\n",
"Yet, the set of vectors $v_i$ is orthogonal, $v_i^H v_j = C \\delta_{i,j}$. So, all the terms of the sum are equal to zero except for the one where $i=j$:<br/>\n",
"$0 =\\sum_{j = 1}^{N}c_{j}.v_{j}.v_{i}^H = 0 + c_{i}.v_{i}.v_{i}^H = c_{i}.v_{i}.v_{i}^H$.\\\n",
"$0 = c_{i}.v_{i}.v_{i}^H$.<br/><br/>\n",
"Nonetheless, we know that $v_{i}$ is a non-zero vector, $v_{i}.v_{i}^H =C$. Hence, we can deduce:\\\n",
"$0 = c_{i}.v_{i}.v_{i}^H$ *if and only if* $c_{i} = 0$<br/><br/>\n",
"This reasonning works for all $i=1, \\ldots , M \\leq N$.<br/><br/>\n",
"\n",
"We can conclude that:\\\n",
"$\\sum_{j = 1}^{N} c_{j}.v_{j} = 0 \\Leftrightarrow c_{j} = 0$.<br/>\n",
"**The set of orthogonal vectors is linearly independent.**"
]
},
{
"cell_type": "markdown",
"id": "accea561-acef-429f-aa68-cc002cba19b8",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"<!-- BEGIN QUESTION -->\n",
"\n",
"2. Compute $a_r = \\sum_{n=0}^{N-1}e^{j2\\pi r\\frac{n}{N}}$, where $r$ is an integer (discuss the result depending on the value of $r$)."
]
},
{
"cell_type": "markdown",
"id": "3f0ff7a0",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "6da31060-083f-4873-9ad3-bf33c4a62b84",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"If $r\\equiv 0 \\mod N$, then $e^{j2\\pi r\\frac{n}{N}}=1$, and $a_r = \\sum_{n = 0}^{N-1} 1 = N$.\n",
"\n",
"\n",
"If $r\\not\\equiv 0 \\mod N$, this is the sum of a geometric series $a_r = \\sum_{n = 0}^{N-1} b^{n} = \\frac{1 - b^N}{1 - b}$, with $b=e^{\\frac{2jr\\pi}{N}}$.\n",
"Since $b^N = e^{2jr\\pi} = 1$, we then have $a_r = 0$.\n"
]
},
{
"cell_type": "markdown",
"id": "b591574c-ba6d-4a15-8b42-0cb62508da73",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"<!-- BEGIN QUESTION -->\n",
"\n",
"3. Let $v_k \\in \\mathbb{C}^N$ be such that $v_k[n] = e^{-j 2 \\pi \\frac{kn}{N}}$, for $k,n = 0, \\ldots , N-1$. \n",
"- Prove that these vectors are mutually orthogonal, hence linearly independent. \n",
"- Compute the norm of $v_k$."
]
},
{
"cell_type": "markdown",
"id": "d8031ee7",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "1cd4d461-705e-405d-a433-ee0d4caeb522",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"$v_{k}$ has the form $\\begin{pmatrix}\n",
"e^{0}\\\\ \n",
"e^{-j 2 \\pi \\frac{k}{N}}\\\\ \n",
"...\\\\ \n",
"e^{-j 2 \\pi \\frac{kN-1}{N}}\n",
"\\end{pmatrix}$, for $k,n = 0, \\ldots , N-1$.<br/><br/>\n",
"\n",
"As we mentioned in the previous question, to prove that vectors are mutually orthogonal, we need to demonstrate that $v_k^H v_l = C \\delta_{k,l}$, with $C$ some constant.<br/><br/>\n",
"\n",
"$v_k^H v_l = \\sum_{n = 0}^{N-1} v_{k}[n]^H .v_l[n]$, with $k,l,n = 0, \\ldots , N-1$. (simple rule of matrix multiplication)<br/><br/>\n",
" $= \\sum_{n = 0}^{N-1} e^{j2\\pi k\\frac{n}{N}}.e^{-j2\\pi l\\frac{n}{N}} $<br/>\n",
"\n",
" $= \\sum_{n = 0}^{N-1} e^{j2\\pi \\frac{n}{N}(k-l)}$<br/>\n",
"\n",
" $= \\sum_{n = 0}^{N-1} e^{j2\\pi \\frac{n}{N}r}$, if we define $r=k-l$.<br/><br/>\n",
"\n",
"Using the result of question 2, $v_k^H v_l = 0$ for $k\\neq l$. \n",
"\n",
"For $r = 0$, question2 shows that $v_k^H v_l = N$ for $k = l$.<br/><br/>\n",
"\n",
"\n",
"We can conclude with:<br/>\n",
"$v_k \\in \\mathbb{C}^N$ such as $v_k[n] = e^{-j 2 \\pi \\frac{kn}{N}}$, for $k,n = 0, \\ldots , N-1$ give us:<br/>\n",
"$v_k^H v_l = N \\delta_{k,l}$.\n",
"\n",
"\n",
"**The vectors are mutually orthogonal, hence linear independent.**\n",
"\n",
"From the above result we have $v_k^Hv_k = N = \\|v_k\\|^2$, and therefore $\\|v_k\\| = \\sqrt{N}$."
]
},
{
"cell_type": "markdown",
"id": "efc7a6a3-1602-4100-8ec8-d82f9e01ad86",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"4. Implement the function `get_fourier_matrix` that returns a normalized Fourier matrix of size $N\\times N$. Do not make use of the builtin DFT/FFT functions in `numpy` or `scipy`. Raise a `ValueError` exception if a ngetive or zero $N$ value is supplied."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "f58a90c7-d4e3-48d9-a21b-42a4d79e2344",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"def get_fourier_matrix(N):\n",
" # BEGIN SOLUTION\n",
" if N <= 0:\n",
" raise ValueError(\"Invalid size\")\n",
" k = np.arange(0, N)\n",
" Ws = np.exp(-2j*np.pi*np.outer(k, k)/N)\n",
" return Ws/np.sqrt(N)\n",
" # END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "2283adf4",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [
{
"data": {
"text/html": [
"<p><strong><pre style='display: inline;'>q4</pre></strong> passed! 🎉</p><p><strong><pre style='display: inline;'>q4 - 1</pre> message:</strong> Good, your implementation returns correct results</p><p><strong><pre style='display: inline;'>q4 - 2</pre> message:</strong> Good, you did not use the scipy.linalg.dft function</p><p><strong><pre style='display: inline;'>q4 - 3</pre> message:</strong> Good, you did not use the scipy.fft.fft function</p><p><strong><pre style='display: inline;'>q4 - 4</pre> message:</strong> Good, you did not use the numpy.fft.fft function</p><p><strong><pre style='display: inline;'>q4 - 5</pre> message:</strong> Good, your implementation returns an orthogonal matrix</p><p><strong><pre style='display: inline;'>q4 - 6</pre> message:</strong> Good, you properly validated size before computing the result</p>"
],
"text/plain": [
"q4 results: All test cases passed!\n",
"q4 - 1 message: Good, your implementation returns correct results\n",
"q4 - 2 message: Good, you did not use the scipy.linalg.dft function\n",
"q4 - 3 message: Good, you did not use the scipy.fft.fft function\n",
"q4 - 4 message: Good, you did not use the numpy.fft.fft function\n",
"q4 - 5 message: Good, your implementation returns an orthogonal matrix\n",
"q4 - 6 message: Good, you properly validated size before computing the result"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grader.check(\"q4\")"
]
},
{
"cell_type": "markdown",
"id": "a5f6b819-1e53-456a-bf67-b76258922d6e",
"metadata": {},
"source": [
"Let us now generate two test signals. \n",
"\n",
"The first one $x_1(t)$ is made of four piecewise sinusoids, of different frequencies:\n",
"\n",
"$$\n",
"x_1(t) = \\cos(2\\pi 5t), 0\\le t < 2\\\\\n",
"x_1(t) = \\cos(2\\pi 10t), 2\\le t < 4\\\\\n",
"x_1(t) = \\cos(2\\pi 25t), 4\\le t < 6\\\\\n",
"x_1(t) = \\cos(2\\pi 50t), 6\\le t < 8\\\\\n",
"$$\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "081e39c8-1874-4274-a7dc-59c8bdab84e4",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"Fs = 256 # sampling frequency\n",
"t = np.arange(0, Fs*8)/Fs\n",
"x1 = np.zeros(Fs*8)\n",
"x1[0:Fs*2] = np.cos(2*np.pi*5*t[0:Fs*2])\n",
"x1[Fs*2:Fs*4] = np.cos(2*np.pi*10*t[Fs*2:Fs*4])\n",
"x1[Fs*4:Fs*6] = np.cos(2*np.pi*25*t[Fs*4:Fs*6])\n",
"x1[Fs*6:Fs*8] = np.cos(2*np.pi*50*t[Fs*6:Fs*8])"
]
},
{
"cell_type": "markdown",
"id": "b7f7475c-bfb0-4e9f-9dd6-ac9eeb5abef1",
"metadata": {},
"source": [
"The second signal $x_2(t)$ is the sum of the same sinusoids over the complete time interval, with a scaling term s.t. the amplitude of both signals is identical."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8e0199b4-baf4-4376-a61c-b778aabe59f7",
"metadata": {},
"outputs": [],
"source": [
"x2 = 0.25*(np.cos(2*np.pi*5*t) + np.cos(2*np.pi*10*t) + np.cos(2*np.pi*25*t) + np.cos(2*np.pi*50*t))"
]
},
{
"cell_type": "markdown",
"id": "c52f3daf-0017-4252-b297-b5d6bb6c8151",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"5. \n",
"- Display the generated signals using `plt.plot`. \n",
"- Compute their Fourier transforms using the Fourier matrix generate at the previous question.\n",
"- Display the amplitude of their Fourier spectrum. What do you observe ? "
]
},
{
"cell_type": "markdown",
"id": "cbde7de1",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7d4aee96-f61e-4e51-84e8-56b4e357aa0f",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# plot x1\n",
"# BEGIN SOLUTION\n",
"plt.plot(x1)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7a504349-03a3-4efd-bc3b-8249c09453fb",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# plot x2\n",
"# BEGIN SOLUTION\n",
"plt.plot(x2)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7bf1bf4a-04b8-43f6-8128-29647e1f964a",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Compute the Fourier transform of x1 and x2\n",
"# BEGIN SOLUTION\n",
"W = get_fourier_matrix(len(x1))\n",
"xf1 = W@x1\n",
"xf2 = W@x2\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "159e693c-4427-4a8b-9f53-42dc63bafbc9",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Plot the spectrum of x1\n",
"# BEGIN SOLUTION\n",
"plt.plot(np.abs(xf1))\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f2c3061b-900e-44d9-bb73-02c98334a818",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Plot the spectrum of x2\n",
"# BEGIN SOLUTION\n",
"plt.plot(np.abs(xf2))\n",
"# END SOLUTION"
]
},
{
"cell_type": "markdown",
"id": "61c226cc-df74-4a71-9e18-8b2071e65a91",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"Despite having $x_1$ and $x_2$ being quite different signals, we notice that the amplitude of their Fourier transform is very similar. The Fourier transform of $x_1$ exhibit more ripples around the peaks due to discontinuites, but both show four symmetrical peaks at the frequencies of the 4 sinusoids composing the signals. While the input signals can be reconstructed from their Fourier transform, these representations are not very well suited, as they give precise informations about the frequencies present in both signals, but no information about their location in time."
]
},
{
"cell_type": "markdown",
"id": "19060be9-6494-4b4e-9803-1a4cb6fc36ac",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"In order to have a better compromise between time and frequency, the input signal will be split in smaller non-overlapping blocks of length $p$, and we will perform the DFT of each block.\n",
"\n",
"6. Using the `get_fourier_matrix` implemented previously, fill the `get_block_dft_matrix` function below s.t. it returns a $N\\times N$ matrix that will perform the block Fourier transform when applied to an input vector. Raise a `ValueError` if $p$ does not divide $N$.\n",
"\n",
"Hint: [numpy.pad](https://numpy.org/doc/stable/reference/generated/numpy.pad.html#numpy.pad) and/or [numpy.kron](https://numpy.org/doc/stable/reference/generated/numpy.kron.html) might prove useful."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "903005b2-e249-48a0-b28b-24daef16cdb7",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"def get_block_dft_matrix(N, p):\n",
" # BEGIN SOLUTION\n",
" if N % p != 0:\n",
" raise ValueError(\"Incorrect size\")\n",
" return np.kron(np.eye(N//p), get_fourier_matrix(p))\n",
" # END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "58978e43",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [],
"source": [
"grader.check(\"q6\")"
]
},
{
"cell_type": "markdown",
"id": "4e894db3-b5e6-4b44-a7d1-988c59542b74",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"We will now use this block Fourier transform to how the frequencies of the signal evolve through time.\n",
"\n",
"7. \n",
"- Using the `reshape` and `plt.imshow` functions, display the amplitude of the result of the block Fourier transform of $x_1$ and $x_2$. Is the result improved when compared to the one observed in question 5 ?\n",
"- What is the influence of parameter $p$ ? \n"
]
},
{
"cell_type": "markdown",
"id": "6239185e",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6da33694-7bd6-4257-9a5f-9bb300cd5c69",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Compute the block DFT matrix Wb\n",
"# BEGIN SOLUTION\n",
"p = 64\n",
"Wb = get_block_dft_matrix(len(x1), p)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e1eb36fe-3079-4feb-86df-10596293e550",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Plot the block DFT of x1\n",
"# BEGIN SOLUTION\n",
"plt.imshow(np.rot90(np.abs(Wb@x1).reshape(len(x1)//p, p)))\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4de97281-75ba-49d0-bc02-2573cf9791ec",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Plot the block DFT of x2\n",
"# BEGIN SOLUTION\n",
"plt.imshow(np.rot90(np.abs(Wb@x2).reshape(len(x2)//p, p)))\n",
"# END SOLUTION"
]
},
{
"cell_type": "markdown",
"id": "34644739-72f3-4570-b27f-579baeb2f33d",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"We now have a better idea of how the frequencies present in the signals evolve through time. It is more obvious that $x_1$ contains a sequence of sinusoids and $x_2$ a superposition of sinusoids. \n",
"\n",
"However, the limitation is that parameter $p$ controls the frequency resolution. If we chose a value of $p$ too small, the frequency resolution is poor, and if we chose a $p$ too big, the time resolution will be in turn bad. So while we improve the time-frequency display, there is a tradeoff to be made between time and frequency resolutions, as both cannot be simultaneously high."
]
},
{
"cell_type": "markdown",
"id": "76cc3589-b7d9-44ec-98ea-07fc6550a53a",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"<!-- BEGIN QUESTION -->\n",
"\n",
"8. In a real-world application, would generating a $N\\times N$ matrix to perform the block Fourier transform be a good way to implement it ? (Justify)"
]
},
{
"cell_type": "markdown",
"id": "ff1a761a",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "21f8ce3e-1548-45fe-aa05-7b59aa052eca",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"In a real-world application, the matrix as we implemented it is a poor choice. As the blocks that compose it are identical, it would be much more efficient to apply the smaller block Fourier matrix directly to the chunks of the input signals."
]
},
{
"cell_type": "markdown",
"id": "87372bd1-4055-4742-ab6a-f7b6ba8750af",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"## Part II - Haar transform\n",
"\n",
"In this part we will study another approach to study the time/frequency properties of signals. \n",
"\n",
"Let us consider a vector $x\\in\\mathbb{R}^N$, with $N$ being even. The single-level Haar transform decomposes $x$ into two vectors $a^1$ and $d^1$ belonging to $\\mathbb{R}^{\\frac{N}{2}}$. \n",
"\n",
"The coefficients of $a^1$ are defined as follows: $a^1_n = \\frac{1}{\\sqrt{2}}(x_{2n-1} + x_{2n}), n=1, ..., \\frac{N}{2}$. $a^1$ is referred to as the *average coefficients vector*.\n",
"\n",
"The coefficients of $d^1$ are defined as follows: $d^1_n = \\frac{1}{\\sqrt{2}}(x_{2n-1} - x_{2n}), n=1, ..., \\frac{N}{2}$. $d^1$ is referred to as the *detail coefficients vector*.\n"
]
},
{
"cell_type": "markdown",
"id": "170a3e62-8b25-482c-a8dd-91988b1d08ed",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"9. Let us represent the single-level Haar transform by a matrix $H_1$ s.t. \n",
"$$\n",
"H_1 x = \\begin{pmatrix}a^1 \\\\ d^1\\end{pmatrix}\n",
"$$\n",
"Prove that $H_1$ is orthonormal."
]
},
{
"cell_type": "markdown",
"id": "56fd9eda",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "e5906e37-9a3f-469c-9904-ba4fe551612c",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"In order to check that $H_1H_1^T=H_1^TH_1 = I$ we need to distinguish different cases.\n",
"\n",
"First, we see that $H_1$ has two types of rows: the upper-half is made of shifted copies of $\\frac{1}{\\sqrt{2}}(1, 1, 0, ...., 0)$, the lower-half is made of shifted copies of \n",
"$\\frac{1}{\\sqrt{2}}(1, -1, 0, ...., 0)$. Both are shifted by multiple of 2 elements, and the only case where those vectors have a common support is when they are shifted by the same amount of elements. Otherwise they have disjoint supports, and their scalar product is 0, which makes them orthogonal.\n",
"\n",
"When they have a common support, there are two cases:\n",
"- we compute the scalar product of a row of $H_1$ with itself, which in this case is clearly equal to 1\n",
"- we compute the scalar product of a row of $H_1$ with its counterpart having the same support in the other half of the matrix, i.e. we compute the scalar product of $(..., 1, 1, 0, ... )$ with $(..., 1, -1, ...)$, which is clearly equal to 0.\n",
"\n",
"This shows that $H_1$ is an orthonormal matrix."
]
},
{
"cell_type": "markdown",
"id": "92f1b78b-3017-4129-bc95-f132717bc7b9",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"10. Write a function that returns the single-level Haar transform matrix $H_1$ for a given $N$. Raise a `ValueError` if $N$ is invalid."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5d123a1c-7f98-4edf-b896-7d773bf48e76",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"def get_sl_haar_matrix(N):\n",
" # BEGIN SOLUTION\n",
" if N <= 0 or N%2 != 0:\n",
" raise ValueError(\"Invalid size\")\n",
" Hu = np.kron(np.eye(N//2), [1, 1])\n",
" Hl = np.kron(np.eye(N//2), [1, -1])\n",
" return np.vstack([Hu, Hl])/np.sqrt(2)\n",
" # END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "86b9b019",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [],
"source": [
"grader.check(\"q10\")"
]
},
{
"cell_type": "markdown",
"id": "e2e7a4af-0f4e-4972-a051-468a12967e79",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"The multi-level Haar transform is defined by recursively applying the single-level transform **to the average coefficient parts**. \n",
"\n",
"For instance constructing 2-level Haar transform over $N$ points start with the previously defined $H_{1,N}$ matrix of size $N\\times N$ and the corresponding $\\frac{N}{2}\\times\\frac{N}{2}$ version denoted by $H_{1,\\frac{N}{2}}$. \n",
"\n",
"$H_{1,N}$ can be written as\n",
"$$\n",
"\\begin{pmatrix} H_{1, N}^a \\\\ H_{1,N}^d \\end{pmatrix},\n",
"$$\n",
"where $H_{1, N}^a$ and $H_{1,N}^d$ are respectively the average and detail coefficient matrices, both of size $\\frac{N}{2}\\times N$.\n",
"\n",
"Following these notations, the 2-level Haar transform matrix $H_{2,N}$ can be written as:\n",
"$$\n",
"\\begin{pmatrix} H_{1,\\frac{N}{2}}H_{1, N}^a \\\\ H_{1,N}^d \\end{pmatrix},\n",
"$$\n",
"\n",
"11. Implement a function that returns the $H_{p,N}$ matrix of size $N\\times N$ that performs a $p$-level haar transform. Raise a `ValueError` if the size and the level are incompatible, or if the level is smaller than 1."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d73eb83b-8d4b-4bf9-9c19-b3d15ee927c1",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"def get_haar_matrix(N, level):\n",
" # BEGIN SOLUTION\n",
" if level < 1:\n",
" raise ValueError(\"Invalid level\")\n",
" H = get_sl_haar_matrix(N)\n",
" cur_N = N\n",
" for k in range(level - 1):\n",
" cur_N = cur_N//2\n",
" if cur_N % 2 != 0:\n",
" raise ValueError(\"Incompatible size\")\n",
" Hs = get_sl_haar_matrix(cur_N)\n",
" H[:cur_N, :] = Hs@H[:cur_N, :]\n",
" return H\n",
" # END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c3138843",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [],
"source": [
"grader.check(\"q11\")"
]
},
{
"cell_type": "markdown",
"id": "918653e3-22c1-4b25-abbc-2461a6736557",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"12. Prove that $H_{p,N}$ is orthonormal."
]
},
{
"cell_type": "markdown",
"id": "02e21ab7",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "136913af-42f3-417a-a94d-2ae7fa7411c7",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"We have shown that $H_{1,N}$ is orthonormal. Using the definition of $H_{2,N}$, we have\n",
"$$\n",
"H_{2,N}H_{2,N}^T=\\begin{pmatrix} H_{1,\\frac{N}{2}}H_{1, N}^a \\\\ H_{1,N}^d \\end{pmatrix}\\begin{pmatrix} {H_{1, N}^a}^T H_{1,\\frac{N}{2}}^T & {H_{1,N}^d}^T \\end{pmatrix},\\\\\n",
"= \\begin{pmatrix} H_{1,\\frac{N}{2}}(H_{1, N}^a{H_{1, N}^a}^T) H_{1,\\frac{N}{2}}^T & H_{1,\\frac{N}{2}}H_{1, N}^a {H_{1,N}^d}^T \\\\ H_{1,N}^d{H_{1, N}^a}^T H_{1,\\frac{N}{2}}^T & H_{1,N}^d{_{1,N}^d}^T\\end{pmatrix}.\n",
"$$\n",
"\n",
"Since the vectors from $H^a$ and $H^d$ are orthogonal, we can simplify the expression to \n",
"$$\n",
"H_{2,N}H_{2,N}^T=\\begin{pmatrix} I & 0 \\\\ 0 & I\\end{pmatrix}.\n",
"$$\n",
"By induction, this is true for all levels."
]
},
{
"cell_type": "markdown",
"id": "8224d668-7cdc-4175-a587-0647df59b2b4",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"### Haar transform visualization\n",
"\n",
"In order to make the visualization of the Haar decomposition easy, we provide you the `plot_haar_coeffs` function that will display the average and detail coefficients of the different levels. \n",
"\n",
"The function takes 2 arguments:\n",
"- the input signal\n",
"- the number of levels\n"
]
},
{
"cell_type": "markdown",
"id": "b6cac5b0-a173-499c-ad89-9e4b82166c7a",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"13. Display the Haar transform of $x1$ and $x2$."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5ca2ec21-222e-430c-a7bd-d2af54e2de47",
"metadata": {
"deletable": false,
"editable": false,
"tags": []
},
"outputs": [],
"source": [
"from display_helper import plot_haar_coeffs"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6a946638-18dc-44fa-8ffc-0b44a3f653e1",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# display the decomposition of x1\n",
"# BEGIN SOLUTION\n",
"plot_haar_coeffs(x1, 5)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b01b9267-9609-474e-b5e0-8b7adb687164",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# display the decomposition of x2\n",
"# BEGIN SOLUTION\n",
"plot_haar_coeffs(x2, 5)\n",
"# END SOLUTION"
]
},
{
"cell_type": "markdown",
"id": "81e23ac6-de1a-4cb4-98f2-89545052f9f3",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"## Part III - Denoising\n",
"\n",
"We will now use the different transforms defined in part I and II to perform denoising.\n",
"Let us create a noisy signal for this purpose."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e5583ca2-13ea-49f8-baf6-4d6a223f3b2e",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"angle1 = np.linspace(0, 5*np.pi/2, 300)\n",
"wave1 = np.sin(angle1)\n",
"angle2 = np.linspace(0, 3*np.pi/2, 300)\n",
"wave2 = np.sin(angle2)\n",
"angle3 = np.linspace(np.pi/2, 2*np.pi, 424)\n",
"wave3 = np.sin(angle3)\n",
"wave = np.append(wave1, wave2)\n",
"wave = np.append(wave, wave3)\n",
"wave_noisy = wave + 0.2*np.random.normal(0, 1, 1024)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d3278fc1-e814-47b9-83f0-61f4fad8d4d7",
"metadata": {},
"outputs": [],
"source": [
"plt.plot(wave_noisy, 'r')\n",
"plt.plot(wave)"
]
},
{
"cell_type": "markdown",
"id": "33489d2d-b038-4896-87e7-0af6568ad702",
"metadata": {},
"source": [
"The noise is usually located in the higher frequencies. However, the signal we created is a bit special as it has two discontinuities which also generate high frequencies components (remember the Fourier transform of a rectangle function is a sinc). "
]
},
{
"cell_type": "markdown",
"id": "fbd9ce45-7214-4ca7-a5e3-cf0c340458a3",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- BEGIN QUESTION -->\n",
"\n",
"14. Implement a function `denoise_signal` that perform denoising of the input signal by using a supplied orthonormal transform matrix, and by setting the transformed coefficients having an amplitude smaller than a given threshold to 0. You might want to use the [numpy.where](https://numpy.org/doc/stable/reference/generated/numpy.where.html) function for this. When denoising using the Haar transform, you can preform the thresholding only on the detail coefficients. Implement the function `denoise_signal_haar` that performs this operation.\n",
"\n",
"NB: The result returned should be real, in order to be displayed. "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "cf7270a7-de1d-4c24-913c-916479ee8ab5",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"def denoise_signal(W, x, threshold=0.1):\n",
" \"\"\"\n",
" W: NxN input orthonormal matrix (Fourier, block-Fourier or Haar)\n",
" x: input signal (of length N)\n",
" \"\"\"\n",
" # BEGIN SOLUTION\n",
" x_tf = W@x\n",
" Winv = np.conj(W.T)\n",
" return np.real(Winv@np.where(np.abs(x_tf)<threshold, 0, x_tf))\n",
" # END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c029ab19-11a5-4bc9-b348-31bf8ca07bca",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"def denoise_signal_haar(W, x, threshold=0.1, detail_start_index=256):\n",
" \"\"\"\n",
" W: NxN input orthonormal matrix (Fourier, block-Fourier or Haar)\n",
" x: input signal (of length N)\n",
" detail_start_index: thresholding is performed on x[detail_start_index:]\n",
" \"\"\"\n",
" # BEGIN SOLUTION\n",
" x_tf = W@x\n",
" Winv = W.T\n",
" x_dn = x_tf\n",
" x_dn[detail_start_index:] = np.where(np.abs(x_tf[detail_start_index:])<threshold, 0, x_tf[detail_start_index:])\n",
" return Winv@x_dn\n",
" # END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1b47fbc5-070b-49c4-a616-d8e753adede1",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Perform denoising with the full Fourier transform and display the result. \n",
"# Make sure you choose a good threshold\n",
"# BEGIN SOLUTION\n",
"waverec_fourier = denoise_signal(get_fourier_matrix(len(wave_noisy)), wave_noisy, 0.55)\n",
"plt.plot(wave_noisy, 'r')\n",
"plt.plot(waverec_fourier)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d06fa927-ca94-4387-b987-a4e3ffeabeb2",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Perform denoising with the block Fourier transform and display the result\n",
"# Make sure you choose a good threshold and block size\n",
"# BEGIN SOLUTION\n",
"waverec_block_fourier = denoise_signal(get_block_dft_matrix(len(wave_noisy), 16), wave_noisy, 0.4)\n",
"plt.plot(wave_noisy, 'r')\n",
"plt.plot(waverec_block_fourier)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "98e6e4a6-a289-4552-b5a9-27f40c40cb40",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"outputs": [],
"source": [
"# Perform denoising with the Haar transform and display the result\n",
"# Make sure you choose a good threshold and an appropriate number of levels\n",
"# BEGIN SOLUTION\n",
"waverec_haar = denoise_signal_haar(get_haar_matrix(len(wave_noisy), 5), wave_noisy, 0.9, 256)\n",
"plt.plot(wave_noisy, 'r')\n",
"plt.plot(waverec_haar)\n",
"# END SOLUTION"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d5cb5707",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [],
"source": [
"grader.check(\"q14\")"
]
},
{
"cell_type": "markdown",
"id": "e6b05f2f-34a1-4689-82ef-c3be92c842ba",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n",
"<!-- BEGIN QUESTION -->\n",
"\n",
"15. Compare the three denoising methods (Fourier, block Fourier and Haar). Which one performs better (in terms of noise removal but also in terms of discontinuity preservation) ? Was that expected (justify) ?"
]
},
{
"cell_type": "markdown",
"id": "a999fadd",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"source": [
"_Type your answer here, replacing this text._"
]
},
{
"cell_type": "markdown",
"id": "eb6b1561-b5cb-4db0-87a0-ca9a4245b7f3",
"metadata": {
"tags": [
"otter_assign_solution_cell"
]
},
"source": [
"We see quite different results in terms of output. The full Fourier transform generates a cleaner denoised signal, however it also smoothes out the discontinuties, which might not be desireable (if you think of the 2D version applied to an image with sharp contours, they would be blurred out). Block DFT and Haar preserve discontinuities better but our very simple denoising method introduces also undesirable artifacts in the block DFT version, while Haar yields better results (good noise removal and discontinuity preservation). The Haar details coefficients are computed using only few neighboring samples, unlike high frequency Fourier coefficients. This helps in preserving the discontinuities when denoising. "
]
},
{
"cell_type": "markdown",
"id": "e705a9ec",
"metadata": {
"deletable": false,
"editable": false
},
"source": [
"<!-- END QUESTION -->\n",
"\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.10"
},
"otter": {
"OK_FORMAT": true,
"tests": {
"q10": {
"name": "q10",
"points": 4,
"suites": [
{
"cases": [
{
"code": ">>> with np.testing.assert_raises(ValueError):\n... get_sl_haar_matrix(-1)\n>>> with np.testing.assert_raises(ValueError):\n... get_sl_haar_matrix(0)\n>>> with np.testing.assert_raises(ValueError):\n... get_sl_haar_matrix(3)\n",
"failure_message": "Did you forget to validate the input size before performing the computation ?",
"hidden": false,
"locked": false,
"points": 1,
"success_message": "Good, you properly validated size before computing the result"
},
{
"code": ">>> np.testing.assert_array_almost_equal(get_sl_haar_matrix(2), np.array([[1, 1], [1, -1]]) / np.sqrt(2))\n>>> np.testing.assert_array_almost_equal(get_sl_haar_matrix(4), np.array([[1, 1, 0, 0], [0, 0, 1, 1], [1, -1, 0, 0], [0, 0, 1, -1]]) / np.sqrt(2))\n",
"failure_message": "Results seem incorrect, check your implementation",
"hidden": false,
"locked": false,
"points": 2,
"success_message": "Good, results look correct"
},
{
"code": ">>> H = get_sl_haar_matrix(16)\n>>> np.testing.assert_array_almost_equal(H @ H.T, np.eye(16))\n>>> np.testing.assert_array_almost_equal(H.T @ H, np.eye(16))\n",
"failure_message": "Results seem incorrect, check your implementation",
"hidden": false,
"locked": false,
"points": 1,
"success_message": "Good, computed matrix is orthogonal"
}
],
"scored": true,
"setup": "",
"teardown": "",
"type": "doctest"
}
]
},
"q11": {
"name": "q11",
"points": 4,
"suites": [
{
"cases": [
{
"code": ">>> with np.testing.assert_raises(ValueError):\n... get_haar_matrix(-1, 0)\n>>> with np.testing.assert_raises(ValueError):\n... get_haar_matrix(16, 0)\n>>> with np.testing.assert_raises(ValueError):\n... get_haar_matrix(4, 3)\n",
"failure_message": "Did you forget to validate the input size before performing the computation ?",
"hidden": false,
"locked": false,
"points": 1,
"success_message": "Good, you properly validated size/level before computing the result"
},
{
"code": ">>> H = get_haar_matrix(4, 2)\n>>> a = 1 / np.sqrt(2)\n>>> np.testing.assert_array_almost_equal(H, [[0.5, 0.5, 0.5, 0.5], [0.5, 0.5, -0.5, -0.5], [a, -a, 0.0, -0.0], [0.0, -0.0, a, -a]])\n",
"failure_message": "Results seem incorrect, check your implementation",
"hidden": false,
"locked": false,
"points": 2,
"success_message": "Good, results look correct"
},
{
"code": ">>> H = get_haar_matrix(64, 4)\n>>> np.testing.assert_array_almost_equal(H @ H.T, np.eye(64))\n>>> np.testing.assert_array_almost_equal(H.T @ H, np.eye(64))\n",
"failure_message": "Results seem incorrect, check your implementation",
"hidden": false,
"locked": false,
"points": 1,
"success_message": "Good, matrix is orthogonal"
}
],
"scored": true,
"setup": "",
"teardown": "",
"type": "doctest"
}
]
},
"q14": {
"name": "q14",
"points": 6,
"suites": [
{
"cases": [
{
"code": ">>> waverec = denoise_signal(get_fourier_matrix(len(wave_noisy)), wave_noisy, 0.0)\n>>> np.testing.assert_array_almost_equal(waverec, wave_noisy)\n",
"failure_message": "Results seem incorrect, check your implementation",
"hidden": false,
"locked": false,
"success_message": "Good, not denoising the noisy signal does not modify it."
}
],
"scored": true,
"setup": "",
"teardown": "",
"type": "doctest"
}
]
},
"q4": {
"name": "q4",
"points": 1,
"suites": [
{
"cases": [
{
"code": ">>> from scipy.linalg import dft\n>>> np.testing.assert_array_almost_equal(get_fourier_matrix(16), dft(16, scale='sqrtn'))\n",
"failure_message": "Check your implementation",
"hidden": false,
"locked": false,
"success_message": "Good, your implementation returns correct results"
},
{
"code": ">>> from unittest.mock import patch\n>>> def check_fourier_dft(N):\n... with patch('scipy.linalg.dft') as mock_dft:\n... get_fourier_matrix(N)\n... mock_dft.assert_not_called()\n>>> check_fourier_dft(32)\n",
"failure_message": "Do not use scipy.linalg.dft in your implementation",
"hidden": false,
"locked": false,
"success_message": "Good, you did not use the scipy.linalg.dft function"
},
{
"code": ">>> from unittest.mock import patch\n>>> def check_fourier_fft(N):\n... with patch('scipy.fft.fft') as mock_fft:\n... get_fourier_matrix(N)\n... mock_fft.assert_not_called()\n>>> check_fourier_fft(24)\n",
"failure_message": "Do not use scipy.fft.fft in your implementation",
"hidden": false,
"locked": false,
"success_message": "Good, you did not use the scipy.fft.fft function"
},
{
"code": ">>> from unittest.mock import patch\n>>> def check_fourier_npfft(N):\n... with patch('numpy.fft.fft') as mock_fft:\n... get_fourier_matrix(N)\n... mock_fft.assert_not_called()\n>>> check_fourier_npfft(48)\n",
"failure_message": "Do not use numpy.fft.fft in your implementation",
"hidden": false,
"locked": false,
"success_message": "Good, you did not use the numpy.fft.fft function"
},
{
"code": ">>> W = get_fourier_matrix(8)\n>>> np.testing.assert_array_almost_equal(np.conj(W.T) @ W, np.eye(8))\n",
"failure_message": "Check your implementation, resulting matrix should be orthogonal.",
"hidden": false,
"locked": false,
"success_message": "Good, your implementation returns an orthogonal matrix"
},
{
"code": ">>> with np.testing.assert_raises(ValueError):\n... get_fourier_matrix(0)\n>>> with np.testing.assert_raises(ValueError):\n... get_fourier_matrix(-5)\n",
"failure_message": "Did you forget to validate the input size before performing the computation ?",
"hidden": false,
"locked": false,
"success_message": "Good, you properly validated size before computing the result"
}
],
"scored": true,
"setup": "",
"teardown": "",
"type": "doctest"
}
]
},
"q6": {
"name": "q6",
"points": 4,
"suites": [
{
"cases": [
{
"code": ">>> W = get_block_dft_matrix(32, 8)\n>>> np.testing.assert_array_almost_equal(np.conj(W.T) @ W, np.eye(32))\n",
"failure_message": "Check your implementation, resulting matrix should be orthogonal.",
"hidden": false,
"locked": false,
"points": 1,
"success_message": "Good, your implementation returns an orthogonal matrix"
},
{
"code": ">>> with np.testing.assert_raises(ValueError):\n... get_block_dft_matrix(64, 7)\n",
"failure_message": "Did you forget to validate the input size before performing the computation ?",
"hidden": false,
"locked": false,
"points": 1,
"success_message": "Good, you properly validated size before computing the result"
},
{
"code": ">>> W = get_block_dft_matrix(4, 2)\n>>> np.testing.assert_array_almost_equal(W[0:2, 0:2], get_fourier_matrix(2))\n>>> np.testing.assert_array_almost_equal(W[2:4, 2:4], get_fourier_matrix(2))\n>>> np.testing.assert_array_almost_equal(W[2:4, 0:2], np.zeros((2, 2)) * 1j)\n>>> np.testing.assert_array_almost_equal(W[0:2, 2:4], np.zeros((2, 2)) * 1j)\n",
"failure_message": "Check your implementation !",
"hidden": false,
"locked": false,
"points": 2,
"success_message": "Good, your implementation returns the correct result"
}
],
"scored": true,
"setup": "",
"teardown": "",
"type": "doctest"
}
]
}
}
}
},
"nbformat": 4,
"nbformat_minor": 5
}