Linear transforms.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e039b976",
   "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",
    "## Important\n",
    "You need to submit *individually* your answers on moodle before the next exercise session. For the theoretical questions you can either fill the notebook or write it on a separate sheet (if you are not comfortable with Markdown/TeX) and upload a scanned version. \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": "c6cd60d1",
   "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": "aed5c02d",
   "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": "db9f3b40",
   "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": "a6772e5f",
   "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": "8389b07e",
   "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": "eae601f6",
   "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": "655fc363",
   "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": "1ad05860",
   "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": "7a80f125",
   "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": "7fdfd203",
   "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": "e6d9e517",
   "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": "ee4201b9",
   "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": "4ab6578e",
   "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": "9a63dd83",
   "metadata": {
    "tags": [
     "otter_answer_cell"
    ]
   },
   "source": [
    "_Type your answer here, replacing this text._"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43d32956",
   "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": [