Implementation of SVD in Python from scratch.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "6e14741e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np \n",
    "from scipy.linalg import svd "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe9f3c84",
   "metadata": {},
   "source": [
    "The line import numpy as np imports the numpy library and assigns it the alias np. This allows you to use various numerical and array operations provided by NumPy.\n",
    "\n",
    "The line from scipy.linalg import svd imports the svd function from the scipy.linalg module. The svd function is a high-level implementation of the Singular Value Decomposition algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "01cf8fa1",
   "metadata": {},
   "outputs": [],
   "source": [
    "#This function calculates the Eigenvectors corresponding for U matrice\n",
    "def calculU(M): \n",
    "    B = np.dot(M, M.T) \n",
    "        \n",
    "    eigenvalues, eigenvectors = np.linalg.eig(B) \n",
    "    ncols = np.argsort(eigenvalues)[::-1] \n",
    "    \n",
    "    return eigenvectors[:,ncols] "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e26fdda5",
   "metadata": {},
   "source": [
    "This function takes a matrix M as input. It first computes newM by performing the dot product between M and its transpose using np.dot(M, M.T).\n",
    "\n",
    "Next, it calculates the eigenvalues and eigenvectors of newM using np.linalg.eig. The eigenvalues and eigenvectors variables store the eigenvalues and corresponding eigenvectors, respectively.\n",
    "\n",
    "The line ncols = np.argsort(eigenvalues)[::-1] sorts the eigenvalues in descending order and stores the corresponding indices in ncols. This step ensures that the eigenvectors are arranged in the correct order.\n",
    "\n",
    "Finally, the function returns the eigenvectors corresponding to the sorted eigenvalues by using the [:, ncols] indexing. This ensures that the returned eigenvectors maintain the same order as the sorted eigenvalues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "be6b1748",
   "metadata": {},
   "outputs": [],
   "source": [
    "#This function calculates the Eigenvectors corresponding for V matrice\n",
    "def calculVt(M): \n",
    "    B = np.dot(M.T, M)\n",
    "        \n",
    "    eigenvalues, eigenvectors = np.linalg.eig(B) \n",
    "    ncols = np.argsort(eigenvalues)[::-1] \n",
    "    \n",
    "    return eigenvectors[:,ncols].T \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2754fc1",
   "metadata": {},
   "source": [
    "This function takes a matrix M as input. It begins by comparing the sizes of the matrices np.dot(M, M.T) and np.dot(M.T, M) using np.size. If the former is larger, it calculates newM as the dot product of M.T and M, otherwise as the dot product of M and M.T. This ensures that newM corresponds to the matrix used for the calculation of singular values.\n",
    "\n",
    "Next, it computes the eigenvalues and eigenvectors of newM using np.linalg.eig. The eigenvalues and eigenvectors variables store the resulting eigenvalues and corresponding eigenvectors, respectively.\n",
    "\n",
    "The line eigenvalues = np.sqrt(eigenvalues) takes the square root of each eigenvalue, as singular values are typically obtained by taking the square root of eigenvalues in the SVD.\n",
    "\n",
    "Finally, the function returns the eigenvalues in descending order using eigenvalues[::-1]. This step ensures that the eigenvalues are sorted in the same order as the SVD implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "f603cf40",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Function that calculates Eigenvalues corresponding to the Sigma Matrix \n",
    "def calculSigma(M): \n",
    "    if (np.size(np.dot(M, M.T)) > np.size(np.dot(M.T, M))): \n",
    "        newM = np.dot(M.T, M) \n",
    "    else: \n",
    "        newM = np.dot(M, M.T) \n",
    "        \n",
    "    eigenvalues, eigenvectors = np.linalg.eig(newM) \n",
    "    eigenvalues = np.sqrt(eigenvalues) \n",
    "    #Sorting in descending order as the svd function does \n",
    "    return eigenvalues[::-1] "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c74edbcf",
   "metadata": {},
   "source": [
    "This function takes a matrix M as input. It starts by comparing the sizes of the matrices np.dot(M, M.T) and np.dot(M.T, M) using np.size. If the former is larger, it calculates newM as the dot product of M.T and M, otherwise as the dot product of M and M.T. This step determines the appropriate matrix for eigenvalue calculation.\n",
    "\n",
    "Next, it computes the eigenvalues and eigenvectors of newM using np.linalg.eig. The eigenvalues and eigenvectors variables store the resulting eigenvalues and corresponding eigenvectors, respectively.\n",
    "\n",
    "The line eigenvalues = np.sqrt(eigenvalues) takes the square root of each eigenvalue since singular values are typically obtained by taking the square root of eigenvalues in the SVD.\n",
    "\n",
    "Finally, the function returns the eigenvalues in descending order using eigenvalues[::-1]. This ensures that the eigenvalues are sorted in the same order as the SVD implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "d1752724",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Creating our matrix \n",
    "A = np.array([[4,2,0],[1,5,6]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "2c3f12b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Calling the corresponding Fuctions and saving the values in variables \n",
    "U = calculU(A) \n",
    "Sigma = calculSigma(A) \n",
    "Vt = calculVt(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "dee863d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-------------------U-------------------\n",
      "[[-0.28978415 -0.95709203]\n",
      " [-0.95709203  0.28978415]]\n",
      "\n",
      "--------------Sigma----------------\n",
      "[8.13872588 3.97003036]\n",
      "\n",
      "-------------V transpose---------------\n",
      "[[-0.26001965 -0.65919758 -0.70558368]\n",
      " [-0.89132415 -0.11719389  0.43795758]\n",
      " [ 0.37139068 -0.74278135  0.55708601]]\n"
     ]
    }
   ],
   "source": [
    "print(\"-------------------U-------------------\")\n",
    "print(U)\n",
    "print(\"\\n--------------Sigma----------------\")\n",
    "print(Sigma)\n",
    "print(\"\\n-------------V transpose---------------\")\n",
    "print(Vt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "5da26061",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4 2 0]\n",
      " [1 5 6]] \n",
      "\n",
      "[[4.00000000e+00 2.00000000e+00 2.22044605e-16]\n",
      " [1.00000000e+00 5.00000000e+00 6.00000000e+00]]\n"
     ]
    }
   ],
   "source": [
    "#Checking if we can remake the original matrix using U,Sigma,Vt\n",
    "\n",
    "newSigma = np.zeros((2, 3))\n",
    "newSigma[:2, :2] = np.diag(Sigma[:2])\n",
    "\n",
    "print(A,\"\\n\")\n",
    "\n",
    "A_remake = (U @ newSigma @ Vt)\n",
    "print(A_remake)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e82bd764",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ae363f1",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "77aaa4e8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41ef9211",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61a51fbf",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a7518b6",
   "metadata": {},
   "outputs": [],
   "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.9.13"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}