{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"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": null,
"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": "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": "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": "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": null,
"id": "f58a90c7-d4e3-48d9-a21b-42a4d79e2344",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"def get_fourier_matrix(N):\n",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2283adf4",
"metadata": {
"deletable": false,
"editable": false
},
"outputs": [],
"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_answer_cell"
]
},
"outputs": [],
"source": [
"# plot x1\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7a504349-03a3-4efd-bc3b-8249c09453fb",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# plot x2\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7bf1bf4a-04b8-43f6-8128-29647e1f964a",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# Compute the Fourier transform of x1 and x2\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "159e693c-4427-4a8b-9f53-42dc63bafbc9",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# Plot the spectrum of x1\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f2c3061b-900e-44d9-bb73-02c98334a818",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# Plot the spectrum of x2\n",
"..."
]
},
{
"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_answer_cell"
]
},
"outputs": [],
"source": [
"def get_block_dft_matrix(N, p):\n",
" ..."
]
},
{
"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_answer_cell"
]
},
"outputs": [],
"source": [
"# Compute the block DFT matrix Wb\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e1eb36fe-3079-4feb-86df-10596293e550",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# Plot the block DFT of x1\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4de97281-75ba-49d0-bc02-2573cf9791ec",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# Plot the block DFT of x2\n",
"..."
]
},
{
"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": "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": "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_answer_cell"
]
},
"outputs": [],
"source": [
"def get_sl_haar_matrix(N):\n",
" ..."
]
},
{
"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_answer_cell"
]
},
"outputs": [],
"source": [
"def get_haar_matrix(N, level):\n",
" ..."
]
},
{
"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": "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_answer_cell"
]
},
"outputs": [],
"source": [
"# display the decomposition of x1\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b01b9267-9609-474e-b5e0-8b7adb687164",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# display the decomposition of x2\n",
"..."
]
},
{
"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_answer_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",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c029ab19-11a5-4bc9-b348-31bf8ca07bca",
"metadata": {
"tags": [
"otter_answer_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",
" ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1b47fbc5-070b-49c4-a616-d8e753adede1",
"metadata": {
"tags": [
"otter_answer_cell"
]
},
"outputs": [],
"source": [
"# Perform denoising with the full Fourier transform and display the result. \n",
"# Make sure you choose a good threshold\n",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d06fa927-ca94-4387-b987-a4e3ffeabeb2",
"metadata": {
"tags": [
"otter_answer_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",
"..."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "98e6e4a6-a289-4552-b5a9-27f40c40cb40",
"metadata": {
"tags": [
"otter_answer_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",
"..."
]
},
{
"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": "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
}