{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6b19e795-908a-481b-8a9f-5241ca8e8fb4",
   "metadata": {},
   "source": [
    "# SVD et compression d'image"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a1fa341-b872-438b-825a-c4d50f939995",
   "metadata": {},
   "source": [
    "L'objectif de ce TP est d'explorer la SVD. Vous commencerez par implémenter un algorithme pour calculer la SVD, puis vous étudierez comment elle est liée à la méthode des moindres carrés. Enfin, vous découvrirez une application moins conventionnelle de la SVD. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5737102e-ca30-40dc-98e9-5f485b02f4f0",
   "metadata": {},
   "source": [
    "## Algorithme de SVD"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64f96a57-6054-4abc-8676-f66516ab8437",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Soit $M$ une matrice de $\\mathcal {R}^{n,m}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21bd6598-7342-43e7-ad66-4f9db15a547c",
   "metadata": {},
   "source": [
    "Dans cette partie, posons $n = 200$ et $m = 2$. On fabriquera la matrice M comme suit :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e99eabb-acac-42a3-b8a5-ecd9a7ca57ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def generate_points(n, P):\n",
    "  \"\"\"Génère n points aléatoires dans le cercle unitaire, multipliés par la matrice P.\n",
    "\n",
    "  Args:\n",
    "    n: Nombre de points à générer.\n",
    "    P: Matrice à multiplier avec les points générés.\n",
    "\n",
    "  Returns:\n",
    "    Un tableau numpy de forme (n, 2) contenant les points générés.\n",
    "  \"\"\"\n",
    "\n",
    "  M = np.zeros((n, 2))\n",
    "  ind = 0\n",
    "\n",
    "  while ind < n:\n",
    "    point = 2 * (0.5 - np.random.rand(1, 2))\n",
    "    if np.linalg.norm(point) < 1:\n",
    "      M[ind, :] = point\n",
    "      ind += 1\n",
    "\n",
    "  return M * P"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1cbb70cc-81ee-4d11-9937-b18cdf2e8c93",
   "metadata": {},
   "source": [
    "Dans la suite, on choisra $P$ :\n",
    "$$P=\\left(\\begin{matrix} −1.5 & 3.2 \\\\ 1.2 & −0.4 \\end{matrix}\\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2647c0c4-263b-467e-9268-349b4708cdfd",
   "metadata": {},
   "source": [
    "Calculer les valeurs propres $\\lambda_i$ et vecteurs propres vi de la matrice $M^T × M$ – avec la fonction dédiée de python\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12a008aa-a34b-4c5a-b723-42a62ef69588",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Ecrire le code du calcul\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2716aff3-8933-4843-aa44-6f822ea231c8",
   "metadata": {},
   "source": [
    "On pose $S = diag(\\sqrt{\\lambda_i})$ et $V$ la matrice des vecteurs propres.\n",
    "Calculer $U = M × V^T \\times S^{-1}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbbd3398-455d-4893-abc8-6530b76c346d",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Ecrire le code du calcul"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f693ef1-829f-408d-9106-027378897543",
   "metadata": {},
   "source": [
    "Vérifier que $U$, $S$ et $V$ correspondent bien au retour de la fonction _svd_ de python !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "74af6f83-819b-4e44-b09b-4e5e358cde47",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Ecire le code de vérification"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e78b3359-01cd-480d-bd20-689a1f2b607b",
   "metadata": {},
   "source": [
    "Tracer ensuite tous les points de M, et superposer les droites définies par les collones de $V$ et le point $0$.\n",
    "On pourra utiliser _.axis('equal')_ pour afficher le graph dans un repère orthonormale."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a16d3de5-50c2-45a3-ba70-4a948049a9da",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Ecrire le code pour faire le graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "811a1be4-0775-4410-ade8-82e44b1ddc5a",
   "metadata": {},
   "source": [
    "Pouvez vous en conclure quelque chose ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bf940d3-a4c2-4c0a-948c-90e6732b6238",
   "metadata": {},
   "source": [
    "## Résolution de système hyperstatique et SVD"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bc891bd-fd79-4f8d-becd-cb2a90d06ed8",
   "metadata": {},
   "source": [
    "La SVD (Décomposition en Valeurs Singulières) est une méthode puissante et robuste pour résoudre des systèmes linéaires surdéterminés, c'est-à-dire lorsque nous avons plus d'équations que d'inconnues. En d'autres termes, nous cherchons à résoudre le système linéaire :\n",
    "\n",
    "$$Mx = b$$\n",
    "\n",
    "où :\n",
    "\n",
    "- $M$ est une matrice de taille $m \\times n$ (avec $m >> n$), représentant les coefficients du système.\n",
    "- $x$ est un vecteur de taille $n \\times 1$, contenant les inconnues.\n",
    "- $b$ est un vecteur de taille $m \\times 1$, représentant les termes connus.\n",
    "\n",
    "En se basant sur la décomposition SVD,$M = U\\Sigma V*$, où $U$ et $V$ sont des matrices unitaires et $\\Sigma$ est une matrice diagonale contenant les valeurs singulières de $M$, la solution des moindres carrés est donnée par :\n",
    "\n",
    "$$x = V\\Sigma^+ U \\times b$$\n",
    "\n",
    "où $\\Sigma^+$ est la pseudo-inverse de $Σ$, obtenue en inversant les valeurs singulières non nulles."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f421102-dbe8-4e10-82a4-1cee4b69f85b",
   "metadata": {},
   "source": [
    "### Application"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3db19bd3-0faf-40ca-a68e-71c754ff93a5",
   "metadata": {},
   "source": [
    "Étant donné un ensemble de m points de données $(t_i, b_i)$, nous cherchons à déterminer les coefficients d'un polynôme de degré $n-1$ de sorte que la somme des carrés des écarts entre les valeurs du polynôme aux abscisses $t_i$ et les valeurs observées $b_i$ soit minimale.\n",
    "\n",
    "L'objectif est de trouver le polynôme \n",
    "$$p(t) = x_0 +x_1t +x_2 t^2 +\\ldots + x_{n-1}t^{n-1}$$\n",
    "\n",
    "qui approche au mieux les points $(t_i, b_i)$ au sens des moindres carrés."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "623dd9dc-63f2-4a15-b204-abdde6f3b00d",
   "metadata": {},
   "source": [
    "On considère les données suivantes\n",
    "\n",
    "| t | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |\n",
    "|---|----|----|----|----|----|----|----|----|----|----|----|\n",
    "| b | 2  | 7  | 9  | 12 | 13 | 14 | 14 | 13 | 10 | 8  | 4  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91844fc0-f393-4530-9d43-6bbd3662b59f",
   "metadata": {},
   "source": [
    "Calculer, par SVD, les coefficients du polynôme de degré $2$ approximant les données."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a345691c-865a-4659-939b-40231513bca9",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Code de calcul de"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61f569ff-7f67-420f-95fa-00fabeed8daa",
   "metadata": {},
   "source": [
    "## Compression d’image et SVD"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22845aca-3c28-4ab9-b7d9-b2d7f64075f7",
   "metadata": {},
   "source": [
    "\n",
    "1. Télécharger l’image en noir et blanc [ici](https://negativespace.co/wp-content/uploads/2017/04/negative-space-black-white-london-street-Custom.jpg)\n",
    "2. \n",
    "Importer l'image – par exemple sous le nom M.\n",
    "3. \n",
    "Réenregistrer la matrice résultante en double.\n",
    "4. \n",
    "Faire une SVD de $M$, récupérant les matrices $U$, $S$ et $V$ .\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e573e84d-5787-4f74-89a9-6a447b125f58",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Code de pour la SVD d'une image"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51e1ba5a-5d4b-4b71-a1b0-0f5dfc12befa",
   "metadata": {},
   "source": [
    "5. Faire une boucle affichant le résultat du produit $U (:, i) × S (1 : i, 1 : i) × V (:, 1 : i)^T$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f76769e-ed9f-4eed-bd8c-f6913753f700",
   "metadata": {},
   "outputs": [],
   "source": [
    "### Code de l'affichage"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56ceae7e-675d-41c4-a7d1-ce668c4699a1",
   "metadata": {},
   "source": [
    "6. Conclusions sur la compression d’image à l'aide de la SVD ?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47099f14-ddef-47be-92a2-65cc842872bf",
   "metadata": {},
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}