06_SVD.ipynb

{
 "metadata": {
  "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
  },
  "orig_nbformat": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "## SVD\n",
    "\n",
    "* Eigen Value approach not possible bcos in EV the matrix is square\n",
    "\n",
    "* In SVD, it can be of any size -> rectangular\n",
    "    * $ Ax = \\lambda x $ is not possible with rectangular as Ax will alter the dimension and wont b equal to x\n",
    "\n",
    "* Comparison with EV and SVD:\n",
    "    * In EV: we had $ S = Q \\Lambda Q^T $ where S - Symmetric matrix, Q - orthogonal matrix\n",
    "\n",
    "    * In SVD : we have $ A = u \\sum V^T $ where A $(m*n)$ - rect matrix; u $(m*r)$, V $(r*n)$ are singular vectors\n",
    "        * $\\sum$ - r*r : singular diag matrix of r dimension    \n",
    "        * u, v are orthogonal (implies rotations)\n",
    "        * $\\sum$ are diag (implies streching)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## Towards SVD:\n",
    "\n",
    "* Consider A = m, n matrix\n",
    "\n",
    "* Case 1 : $ A^T A = V \\Lambda V^T $\n",
    "    * LHS is n, n size\n",
    "    * $\\Lambda$ has n,n size\n",
    "\n",
    "* Case 2 : $ A A^T = u \\Lambda u^T $\n",
    "    * LHS is m, m size\n",
    "    $\\Lambda$ has m,m size\n",
    "\n",
    "* m < n -> case 2 will have fewer evals or they will be zero in those extra dimensions\n",
    "\n",
    "* SVD in-deed takes u from case 2 and v from case 1 to factorize"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "* For rectangular matrix, we are looking for:\n",
    "\n",
    "* $ Av = \\sigma u $\n",
    "    * We are looking for set of orthogonal vectors, v in input space which on transformation with A leads to other bunch of orthogonal vectors in u in output space\n",
    "    * $\\sigma$ are diag matrix \n",
    "\n",
    "* Multiply above with $v^T$ and rearranging -> $ A = u \\sum v^T $\n",
    " \n",
    "* Check $A^T A$  \n",
    "    * $= v \\sum^T u^T u \\sum v^T $\n",
    "\n",
    "    * $= v (\\sum^T \\sum) v^T $\n",
    "    \n",
    "    * Above equation is similar to $ S = Q \\Lambda Q^T $ bcos  $A^T A$  is symmetric and implies v is evectors of  $A^T A$  and evals are $\\sum^2$\n",
    "\n",
    "* Check $A A^T $  \n",
    "    * $= u \\sum^T v^T v \\sum u^T $\n",
    "\n",
    "    * $= u (\\sum^T \\sum) u^T $\n",
    "    \n",
    "    * Above equation is similar to $ S = Q \\Lambda Q^T $ bcos  $A A^T $  is symmetric and implies u is evectors of  $A A^T$  and evals are $\\sum^2$\n",
    "\n",
    "* In general, how to do SVD given A\n",
    "    * Calculate $A^T A$\n",
    "    * factorize above to get v\n",
    "    * Use this $Av = \\sigma u$ equation to calculate u\n",
    "    * Then we have down SVD of A"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## What SVD does to a vector:\n",
    "\n",
    "* $ (A)x = (u \\sum v^T)x $\n",
    "\n",
    "* u, v : Orthogonal matrices : Rotates the basis vectors\n",
    "* $\\sum$ : diagonal matrices : scales/streches the basis as per value in $\\sigma_1, \\sigma_2.. $\n",
    "\n",
    "* Consider x : vectors along x, y axis (consider a circle with unit radius with basis alone x, y axis)\n",
    "    * $V^Tx$ -> rotates the basis into some angle\n",
    "\n",
    "    * $\\sum V^Tx $ -> deforms the circle to ellipse with the axis of length corresponding to  $\\sigma_1, \\sigma_2$. The new vectors are $\\sigma_1*v_1, \\sigma_2*v_2 $\n",
    "\n",
    "    * Finally, $u \\sum V^Tx $ -> rotates the above ellpise in direction of u1, u2\n",
    "\n",
    "* When u = v, it is only possible if A is symmetric! in that case u, v are equal to Q and $\\sum = \\Lambda$ and A should be + definite\n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "* As per above steps, for a 2*2 matrix :\n",
    "    * Need one $\\theta$ parameter to determine rotation (x, y axis basis are together rotated by $\\theta$)\n",
    "    * Need two parameter $\\sigma_1, \\sigma_2$ to determine streching\n",
    "    * Need one $\\theta$ parameter to determine rotation again\n",
    "    * Total 4 parameters\n",
    "    \n",
    "* As per above steps, for a 3*3 matrix :\n",
    "    * Need three $\\theta$ parameter to determine rotation (roll, pitch, yaw) (x, y axis basis are together rotated by $\\theta$)\n",
    "    * Need three parameter $\\sigma_1, \\sigma_2, \\sigma_3$ to determine streching\n",
    "    * Need three $\\theta$ parameter to determine rotation again\n",
    "    * Total 9 parameters\n",
    "    \n",
    "\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## Principal Components\n",
    "\n",
    "* $ A = u \\sum v^T $\n",
    "\n",
    "* $ A =  \\begin{bmatrix} u1 & .. & ur \\end{bmatrix} \\begin{bmatrix} \\sigma_1 & 0 & 0 \\\\ 0 & \\sigma_2 & 0 \\end{bmatrix} \\begin{bmatrix} v_1^t \\\\ .. \\\\ v_2^T \\end{bmatrix} $\n",
    "\n",
    "* Data science is all above pulling out the biggest information in above\n",
    "\n",
    "* That can be done thro pulling the first principal component in $ u1 * \\sigma_1 * v_1^T $"
   ],
   "cell_type": "markdown",
   "metadata": {}
  }
 ]
}