{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b11b0cab",
   "metadata": {},
   "source": [
    "# TP2- Linear Algebra for Machine Learning\n",
    "\n",
    "Real Data Applications in Python: Performance & Accuracy\n",
    "\n",
    "## Objectives\n",
    "\n",
    "- Manipulate vectors and matrices and connect these operations to ML tasks (similarities, PCA, SVD).\n",
    "- Compare accuracy and execution time between homemade implementations and optimized library functions.\n",
    "- Develop skills in profiling (time measurement) and numerical validation (errors, stability).\n",
    "\n",
    "## Instructions\n",
    "\n",
    "For each question:\n",
    "\n",
    "1. Read the Reminder of the method or algorithm.\n",
    "2. Implement a naive Python version (loops, direct formulas).\n",
    "3. Compare with the optimized version using NumPy or scikit-learn.\n",
    "4. Measure and discuss execution times.\n",
    "\n",
    "## Exercises\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1490674e",
   "metadata": {},
   "source": [
    "### Question 1: Determinant of a Matrix\n",
    "\n",
    "**Reminder**: The determinant of an $n × n$ matrix can be computed recursively using\n",
    "**Laplace** expansion:\n",
    "\n",
    "$$\n",
    "\\text{det}(A) = \\sum_{j=1}^{n} (-1)^{i+j} a_{ij} \\text{det}(M_{ij})\n",
    "$$\n",
    "\n",
    "where $M_{1j}$ is the minor of $A$ obtained by removing row $1$ and column $j$. Complexity grows as $O(n!)$.\n",
    "\n",
    "#### Task\n",
    "\n",
    "Implement this recursive method in Python and compare with `numpy.linalg.det`.\n",
    "\n",
    "```python\n",
    "def my_determinant(M):\n",
    "    # TODO: implement recursicec Laplace expansion\n",
    "    return det\n",
    "```\n",
    "\n",
    "Measuer execution time for matrices of size $n = 3, 5, 7, 10$ and discuss complexity.\n",
    "\n",
    "#### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a19d103",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np, time\n",
    "\n",
    "np.random.seed(0)\n",
    "\n",
    "\n",
    "def minor_matrix(A, i, j):\n",
    "    # remove row i and column j\n",
    "    return np.delete(np.delete(A, i, axis=0), j, axis=1)\n",
    "\n",
    "\n",
    "def det_laplace(A):\n",
    "    A = np.asarray(A, dtype=float)\n",
    "    n, m = A.shape\n",
    "    assert n == m, \"Matrix must be square.\"\n",
    "    if n == 0:\n",
    "        return 1.0\n",
    "    if n == 1:\n",
    "        return A[0, 0]\n",
    "    if n == 2:\n",
    "        return A[0, 0] * A[1, 1] - A[0, 1] * A[1, 0]\n",
    "    # Expand along first row\n",
    "    s = 0.0\n",
    "    for j in range(n):\n",
    "        cofactor = ((-1) ** (0 + j)) * A[0, j] * det_laplace(minor_matrix(A, 0, j))\n",
    "        s += cofactor\n",
    "    return s\n",
    "\n",
    "\n",
    "def time_det(n, trials=3):\n",
    "    t_lap = t_np = 0.0\n",
    "    max_err = 0.0\n",
    "    for _ in range(trials):\n",
    "        A = np.random.randn(n, n)\n",
    "        t0 = time.time()\n",
    "        d1 = det_laplace(A)\n",
    "        t_lap += time.time() - t0\n",
    "        t0 = time.time()\n",
    "        d2 = np.linalg.det(A)\n",
    "        t_np += time.time() - t0\n",
    "        max_err = max(max_err, abs(d1 - d2))\n",
    "    t_lap /= trials\n",
    "    t_np /= trials\n",
    "    speedup = (t_lap / t_np) if t_np > 0 else float(\"inf\")\n",
    "    return t_lap, t_np, max_err, speedup\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    for n in [3, 5, 7]:\n",
    "        t1, t2, err, ratio = time_det(n, trials=3)\n",
    "        print(\n",
    "            f\"n={n} | Laplace {t1:.4f}s | NumPy {t2:.6f}s | max|Delta|={err:.3e} | speedup={ratio:.1f}x\"\n",
    "        )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18060c5b",
   "metadata": {},
   "source": [
    "### Question 2: Eigenvalues and Eigenvectors\n",
    "\n",
    "**Reminder**: The Power Iteration algorithm finds the dominant eigenvalue $\\lambda$ of a matrix $A$:\n",
    "\n",
    "1. Choose random vector $b_0$.\n",
    "2. Iterate $b_{k+1} = \\frac{Ab_k}{||Ab_k||}$ until convergence.\n",
    "3. Approximate **eigenvalue**: $\\lambda_k = \\frac{b_k^T A b_k}{b_k^T b_k}$.\n",
    "\n",
    "#### Task\n",
    "\n",
    "Implement Power Iteration to approximate the largest eigenvalue of a symmetric matrix. Compare results and execution times with `numpy.linalg.eig`.\n",
    "\n",
    "#### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27de4b08",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np, time\n",
    "\n",
    "np.random.seed(1)\n",
    "\n",
    "\n",
    "def power_iteration(A, max_iter=1000, tol=1e-8):\n",
    "    A = np.asarray(A, dtype=float)\n",
    "    n = A.shape[0]\n",
    "    b = np.random.randn(n)\n",
    "    b /= np.linalg.norm(b)\n",
    "    lam_old = 0.0\n",
    "    for _ in range(max_iter):\n",
    "        Ab = A @ b\n",
    "        norm = np.linalg.norm(Ab)\n",
    "        if norm == 0:\n",
    "            return 0.0, b\n",
    "        b = Ab / norm\n",
    "        lam = b @ (A @ b)  # Rayleigh quotient\n",
    "        if abs(lam - lam_old) < tol:\n",
    "            break\n",
    "        lam_old = lam\n",
    "    return lam, b\n",
    "\n",
    "\n",
    "def time_power(n, trials=3):\n",
    "    t_pi = t_np = 0.0\n",
    "    max_err = 0.0\n",
    "    for _ in range(trials):\n",
    "        X = np.random.randn(n, n)\n",
    "        A = (X + X.T) / 2  # make symmetric\n",
    "        t0 = time.time()\n",
    "        lam, v = power_iteration(A)\n",
    "        t_pi += time.time() - t0\n",
    "        t0 = time.time()\n",
    "        w, V = np.linalg.eig(A)\n",
    "        t_np += time.time() - t0\n",
    "        lam_np = np.max(np.real(w))\n",
    "        max_err = max(max_err, abs(lam - lam_np))\n",
    "    return t_pi / trials, t_np / trials, max_err\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    for n in [50, 100, 200]:\n",
    "        t1, t2, err = time_power(n)\n",
    "        print(\n",
    "            f\"n={n} | PowerIter {t1:.4f}s | NumPy eig {t2:.4f}s | max|Delta_lambda|={err:.3e}\"\n",
    "        )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d99b1038",
   "metadata": {},
   "source": [
    "### Question 3: Singular Value Decomposition (SVD)\n",
    "\n",
    "**Reminder**: The first singular vector $u_1$ of a matrix $A$ can be obtained by computing the dominant eigenvector of $A A^T$ . Then $v_1 = A^T u_1 / ||A^T u_1||$ . Iterating gives an SVD-like decomposition.\n",
    "\n",
    "#### Task\n",
    "\n",
    "Implement a naive SVD approach (first singular vector via power iteration). Compare with `numpy.linalg.svd`. Apply both methods to a grayscale image (100 × 100) and compare reconstruction quality and execution time.\n",
    "\n",
    "#### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56b5797e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np, time\n",
    "\n",
    "np.random.seed(2)\n",
    "\n",
    "\n",
    "def top_singular_vector(A, max_iter=1000, tol=1e-8):\n",
    "    # Power iteration on A A^T to get u1, then v1 = A^T u1 / ||A^T u1||, sigma1 = ||A^T u1||\n",
    "    A = np.asarray(A, dtype=float)\n",
    "    m, n = A.shape\n",
    "    u = np.random.randn(m)\n",
    "    u /= np.linalg.norm(u)\n",
    "    lam_old = 0.0\n",
    "    for _ in range(max_iter):\n",
    "        u_new = A @ (A.T @ u)\n",
    "        norm = np.linalg.norm(u_new)\n",
    "        if norm == 0:\n",
    "            break\n",
    "        u = u_new / norm\n",
    "        lam = u @ (A @ (A.T @ u))\n",
    "        if abs(lam - lam_old) < tol:\n",
    "            break\n",
    "        lam_old = lam\n",
    "    v = A.T @ u\n",
    "    sigma1 = np.linalg.norm(v)\n",
    "    if sigma1 > 0:\n",
    "        v = v / sigma1\n",
    "    return u, v, sigma1  # left vec, right vec, top singular value (approx)\n",
    "\n",
    "\n",
    "def time_svd(m, n, trials=3):\n",
    "    t_top = t_svd = 0.0\n",
    "    max_err = 0.0\n",
    "    for _ in range(trials):\n",
    "        A = np.random.randn(m, n)\n",
    "        t0 = time.time()\n",
    "        u, v, s1 = top_singular_vector(A)\n",
    "        t_top += time.time() - t0\n",
    "        t0 = time.time()\n",
    "        U, S, VT = np.linalg.svd(A, full_matrices=False)\n",
    "        t_svd += time.time() - t0\n",
    "        max_err = max(max_err, abs(s1 - S[0]))\n",
    "    return t_top / trials, t_svd / trials, max_err\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    for shape in [(100, 100), (200, 100), (100, 200)]:\n",
    "        t1, t2, err = time_svd(*shape)\n",
    "        print(\n",
    "            f\"{shape} | Power-Top-SV {t1:.4f}s | NumPy SVD {t2:.4f}s | max|Delta_sigma1|={err:.3e}\"\n",
    "        )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc810071",
   "metadata": {},
   "source": [
    "### Question 4: Principal Component Analysis (PCA)\n",
    "\n",
    "**Reminder**: PCA steps:\n",
    "\n",
    "1. **Center data**: $X_c = X − \\bar{X}$.\n",
    "2. **Compute covariance**: $C = \\frac{1}{n-1} X^T_c X_c$\n",
    "3. **Find _eigenvectors/eigenvalues_** of $C$.\n",
    "4. **Project data** on top $k$ eigenvectors.\n",
    "\n",
    "#### Task:\n",
    "\n",
    "- Implement PCA manually (following above steps).\n",
    "- Compare with `sklearn.decomposition.PCA`.\n",
    "- Use the **digits** dataset from scikit-learn and compare execution times and results\n",
    "\n",
    "#### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a9057ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np, time\n",
    "from sklearn.datasets import load_digits\n",
    "from sklearn.decomposition import PCA\n",
    "\n",
    "\n",
    "def pca_manual(X, k):\n",
    "    # Center, covariance, eigen-decomposition, sort, project\n",
    "    X = np.asarray(X, dtype=float)\n",
    "    Xc = X - X.mean(axis=0, keepdims=True)\n",
    "    C = (Xc.T @ Xc) / (Xc.shape[0] - 1)\n",
    "    w, V = np.linalg.eigh(C)  # symmetric\n",
    "    idx = np.argsort(w)[::-1]\n",
    "    w, V = w[idx], V[:, idx]\n",
    "    Wk, Vk = w[:k], V[:, :k]\n",
    "    Z = Xc @ Vk\n",
    "    return Z, Vk, Wk\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    digits = load_digits()\n",
    "    X = digits.data  # shape (n_samples, n_features)\n",
    "    k = 20\n",
    "\n",
    "    t0 = time.time()\n",
    "    Zm, Vm, Wm = pca_manual(X, k)\n",
    "    t_manual = time.time() - t0\n",
    "\n",
    "    t0 = time.time()\n",
    "    pca = PCA(n_components=k, svd_solver=\"full\").fit(X)\n",
    "    Zsk = pca.transform(X)\n",
    "    t_sklearn = time.time() - t0\n",
    "\n",
    "    # Compare subspaces via principal angles: SVD of Vm.T * components.T\n",
    "    U, S, VT = np.linalg.svd(Vm.T @ pca.components_[:k].T, full_matrices=False)\n",
    "    subspace_cosines = S  # in [0,1]; closer to 1 => better alignment\n",
    "\n",
    "    print(f\"Manual PCA time:  {t_manual:.4f}s\")\n",
    "    print(f\"sklearn PCA time: {t_sklearn:.4f}s\")\n",
    "    print(\"Subspace cosines (principal angles):\", subspace_cosines)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d92378ff",
   "metadata": {},
   "source": [
    "### Bonus: Cosine Similarity\n",
    "\n",
    "**Reminder**: For two vectors $x, y \\in \\mathbb{R}^n$:\n",
    "\n",
    "$$\n",
    "\\cos(\\theta) = \\frac{x \\cdot y}{||x|| ||y||}\n",
    "$$\n",
    "\n",
    "#### Task\n",
    "\n",
    "Implement cosine similarity manually. Compare with `sklearn.metrics.pairwise.cosine_similarity`. Test with $10^5$ vectors of dimension $300$, and compare execution times.\n",
    "\n",
    "#### Solution\n",
    "\n",
    "Will not work as intended due to memory issues.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02f11657",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.metrics.pairwise import cosine_similarity\n",
    "import time\n",
    "\n",
    "# Generate random data: 10^5 vectors of dimension 300\n",
    "n_samples, dim = 10**5, 300\n",
    "X = np.random.randn(n_samples, dim)\n",
    "Y = np.random.randn(n_samples, dim)\n",
    "\n",
    "\n",
    "# ------------------------------\n",
    "# Manual Implementation\n",
    "# ------------------------------\n",
    "def manual_cosine_similarity(X, Y):\n",
    "    # Dot products between corresponding rows\n",
    "    dot = np.sum(X * Y, axis=1)\n",
    "    # Norms of each vector\n",
    "    norm_x = np.linalg.norm(X, axis=1)\n",
    "    norm_y = np.linalg.norm(Y, axis=1)\n",
    "    # Avoid division by zero\n",
    "    return dot / (norm_x * norm_y + 1e-10)\n",
    "\n",
    "\n",
    "# Time manual implementation\n",
    "start = time.time()\n",
    "manual_result = manual_cosine_similarity(X, Y)\n",
    "manual_time = time.time() - start\n",
    "print(f\"Manual Cosine Similarity Time: {manual_time:.4f} seconds\")\n",
    "\n",
    "# ------------------------------\n",
    "# Scikit-Learn Implementation\n",
    "# ------------------------------\n",
    "# sklearn expects 2D arrays; it computes all pairwise similarities\n",
    "# so we compute only diagonal values (same pairs)\n",
    "start = time.time()\n",
    "sklearn_result_full = cosine_similarity(X, Y)\n",
    "sklearn_result = np.diag(sklearn_result_full)\n",
    "sklearn_time = time.time() - start\n",
    "print(f\"Sklearn Cosine Similarity Time: {sklearn_time:.4f} seconds\")\n",
    "\n",
    "# ------------------------------\n",
    "# Comparison\n",
    "# ------------------------------\n",
    "diff = np.mean(np.abs(manual_result - sklearn_result))\n",
    "print(f\"Mean absolute difference: {diff:.6f}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
