{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reduced singular value decomposition (SVD) decomposes $A$ with rank $r$ into a left singular vector matrix $U$, a diagonal singular value matrix $\\Sigma$, and a right singular vector matrix $V$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "\\underset{m\\times n}{A}  &= \\underset{m \\times r,}{U} \\underset{r \\times r,}{\\Sigma} \\underset{r \\times n}{V^{T}}\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$U$ and $V$ are composed of orthonormal columns."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One way to calculate reduced SVD is as follows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\underset{n\\times n}{A^TA} \n",
    "&= (V \\Sigma^T U^T)U \\Sigma V^T \\\\\n",
    "&= V \\Sigma^T \\Sigma V^T\\\\\n",
    "\\underset{n \\times r}{A^T A V}\n",
    "&= V \\Sigma^T\\Sigma \\\\\n",
    "&= V \\Sigma^2\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note, the last equation fits the pattern of eigendecomposition, $BX = X\\Lambda$, so eigendecompose $A^TA$ would find $\\Sigma^2$ and $V$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, $U$ can be obtained by"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "U &= AV\\Sigma^{-1}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "\\underset{m \\times m}{A A^T}\n",
    "&= U \\Sigma V^T \\left( V \\Sigma^T U^T \\right ) \\\\\n",
    "&= U \\Sigma \\Sigma^T U^T \\\\\n",
    "\\underset{m \\times r}{A A^T U}\n",
    "&= U \\Sigma \\Sigma^T \\\\\n",
    "&= U \\Sigma^2\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The last equation also fits the pattern of eigendecomposition, $BX = X\\Lambda$, so eigendecompose $A A^T$ would find $\\Sigma^2$ and $U$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, $V$ can be found by"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "V^T \n",
    "&= \\Sigma^{-1} U^T A \\\\\n",
    "V\n",
    "&= A^T U \\Sigma^{-1}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For comparison of full SVD vs reduced SVD vs truncated SVD, see https://math.stackexchange.com/questions/2627005/are-reduced-svd-and-truncated-svd-the-same-thing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Demo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sympy as sp\n",
    "\n",
    "import svd_reduced_utils"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 1: $m = 2, n = 3, r=2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 2 & 2\\\\2 & 3 & -2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3, 2,  2],\n",
       "[2, 3, -2]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# An example taken from http://www.d.umn.edu/~mhampton/m4326svd_example.pdf\n",
    "A = sp.Matrix(\n",
    "    [\n",
    "        [3, 2, 2],\n",
    "        [2, 3, -2],\n",
    "    ]\n",
    ")\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rank()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "U, Σ, V = svd_reduced_utils.svd(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2}\\\\\\frac{\\sqrt{2}}{2} & - \\frac{\\sqrt{2}}{2}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[sqrt(2)/2,  sqrt(2)/2],\n",
       "[sqrt(2)/2, -sqrt(2)/2]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}5 & 0\\\\0 & 3\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[5, 0],\n",
       "[0, 3]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Σ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2} & 0\\\\\\frac{\\sqrt{2}}{6} & - \\frac{\\sqrt{2}}{6} & \\frac{2 \\sqrt{2}}{3}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[sqrt(2)/2,  sqrt(2)/2,           0],\n",
       "[sqrt(2)/6, -sqrt(2)/6, 2*sqrt(2)/3]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 2 & 2\\\\2 & 3 & -2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3, 2,  2],\n",
       "[2, 3, -2]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert A == U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 2: $m = 3, n = 2, r=2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 2\\\\2 & 3\\\\2 & -2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3,  2],\n",
       "[2,  3],\n",
       "[2, -2]])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = sp.Matrix(\n",
    "    [\n",
    "        [3, 2],\n",
    "        [2, 3],\n",
    "        [2, -2],\n",
    "    ]\n",
    ")\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rank()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "U, Σ, V = svd_reduced_utils.svd(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{\\sqrt{2}}{2} & - \\frac{\\sqrt{2}}{6}\\\\\\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{6}\\\\0 & - \\frac{2 \\sqrt{2}}{3}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[sqrt(2)/2,   -sqrt(2)/6],\n",
       "[sqrt(2)/2,    sqrt(2)/6],\n",
       "[        0, -2*sqrt(2)/3]])"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}5 & 0\\\\0 & 3\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[5, 0],\n",
       "[0, 3]])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Σ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2}\\\\- \\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[ sqrt(2)/2, sqrt(2)/2],\n",
       "[-sqrt(2)/2, sqrt(2)/2]])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 2\\\\2 & 3\\\\2 & -2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3,  2],\n",
       "[2,  3],\n",
       "[2, -2]])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert A == U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 1: $m = 2, n = 3, r=1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 2 & 2\\\\3 & 2 & 2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3, 2, 2],\n",
       "[3, 2, 2]])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# An example taken from http://www.d.umn.edu/~mhampton/m4326svd_example.pdf\n",
    "A = sp.Matrix(\n",
    "    [\n",
    "        [3, 2, 2],\n",
    "        [3, 2, 2],\n",
    "    ]\n",
    ")\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rank()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "U, Σ, V = svd_reduced_utils.svd(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{\\sqrt{2}}{2}\\\\\\frac{\\sqrt{2}}{2}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[sqrt(2)/2],\n",
       "[sqrt(2)/2]])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\sqrt{34}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([[sqrt(34)]])"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Σ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{3 \\sqrt{17}}{17} & \\frac{2 \\sqrt{17}}{17} & \\frac{2 \\sqrt{17}}{17}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([[3*sqrt(17)/17, 2*sqrt(17)/17, 2*sqrt(17)/17]])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 2 & 2\\\\3 & 2 & 2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3, 2, 2],\n",
       "[3, 2, 2]])"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert A == U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 1: $m = 3, n = 2, r=1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 3\\\\2 & 2\\\\2 & 2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3, 3],\n",
       "[2, 2],\n",
       "[2, 2]])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = sp.Matrix(\n",
    "    [\n",
    "        [3, 3],\n",
    "        [2, 2],\n",
    "        [2, 2],\n",
    "    ]\n",
    ")\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A.rank()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "U, Σ, V = svd_reduced_utils.svd(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{3 \\sqrt{17}}{17}\\\\\\frac{2 \\sqrt{17}}{17}\\\\\\frac{2 \\sqrt{17}}{17}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3*sqrt(17)/17],\n",
       "[2*sqrt(17)/17],\n",
       "[2*sqrt(17)/17]])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\sqrt{34}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([[sqrt(34)]])"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Σ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}\\frac{\\sqrt{2}}{2} & \\frac{\\sqrt{2}}{2}\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([[sqrt(2)/2, sqrt(2)/2]])"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}3 & 3\\\\2 & 2\\\\2 & 2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[3, 3],\n",
       "[2, 2],\n",
       "[2, 2]])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert A == U @ Σ @ V.T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TODO: convert the above examples into a table."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}