Deep Learning Book Notes Ch 2 Exercises.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 2 Linear Algebra Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "* [Source](https://www.deeplearningbook.org/linear_algebra.pdf) \n",
    "    * Given the expression $ \\alpha \\pmb{u} $ for $ \\alpha \\in \\mathbb{R} $ and a unit vector $ \\pmb{u} \\in \\mathbb{R}^n $, such that varying $\\alpha$ defines a set of points (aka a line) along the direction of $\\pmb{u}$, and given an arbitrary $\\pmb{x} \\in \\mathbb{R}^n$, derive the expression defining $\\pmb{y}$ such that $\\pmb{y} = \\alpha \\pmb{u} $ where $\\pmb{y}$ is the point along the line that lies closest to the point $\\pmb{x}$.\n",
    "    * Solution:\n",
    "        * Defining the variable $d$ as the distance between $\\pmb{x}$ and $\\pmb{y}$, we can state that $ d = \\lVert \\pmb{x} - \\pmb{y} \\rVert $. \n",
    "        * We can restate this as $ d = \\lVert \\pmb{x} - \\alpha\\pmb{u} \\rVert $, since $\\pmb{y} = \\alpha \\pmb{u} $ \n",
    "        * In order to find the minimum $d$, we can vary $\\alpha$ such for the point at which $d$ is the minimum, the derivative of $d$ wrt to $\\alpha$ is zero; in other words $\\frac{dd}{d\\alpha} = 0$\n",
    "        * We can also include the observation that squaring the distance $d$ does not change the point $\\pmb{y}$ closest to $\\pmb{x}$, since $d$ is always positive or zero.\n",
    "        * so we can redefine $ d = \\lVert \\pmb{x} - \\alpha\\pmb{u} \\rVert^2 $ and at the point where $d$ is the minimum, the derivative of $d$ wrt to $\\alpha$ is still zero as above; in other words, the following still holds: $\\frac{dd}{d\\alpha} = 0$.\n",
    "        * Expanding the equation\n",
    "$$\n",
    "0 = \\frac{dd}{d\\alpha} =\n",
    "\\frac{d\\lVert \\pmb{x} - \\alpha\\pmb{u} \\rVert^2}{d\\alpha} =\n",
    "\\frac{d}{d\\alpha}\\lVert \\pmb{x} - \\alpha\\pmb{u} \\rVert^2 =\n",
    "\\frac{d}{d\\alpha}[(\\pmb{x} - \\alpha\\pmb{u})^T(\\pmb{x} - \\alpha\\pmb{u})] =\n",
    "\\frac{d}{d\\alpha}[(\\pmb{x}^T - \\alpha\\pmb{u}^T)(\\pmb{x} - \\alpha\\pmb{u})] =\n",
    "\\frac{d}{d\\alpha}(\\pmb{x}^T\\pmb{x} -  \\alpha\\pmb{u}^T\\pmb{x} - \\pmb{x}^T\\alpha\\pmb{u} + \\alpha\\pmb{u}^T\\alpha\\pmb{u}) =\n",
    "\\frac{d}{d\\alpha}(\\pmb{x}^T\\pmb{x} - \\alpha(\\pmb{u}^T\\pmb{x} + \\pmb{x}^T\\pmb{u}) + \\alpha^2\\pmb{u}^T\\pmb{u})\n",
    "$$\n",
    "        Since the matrix multiplication transpose rule for vectors $x$ and $y$ states that $\\pmb{x}^T\\pmb{y} = \\pmb{y}^T\\pmb{x}$, then $\\pmb{u}^T\\pmb{x} = \\pmb{x}^T\\pmb{u}$ and since $\\pmb{u}^T\\pmb{u} = 1$ (as per definition of a unit vector),  the above equation simplifies to \n",
    "$$\n",
    "0 = \\frac{dd}{d\\alpha} =\n",
    "\\frac{d}{d\\alpha}(\\pmb{x}^T\\pmb{x} - \\alpha(\\pmb{u}^T\\pmb{x} + \\pmb{u}^T\\pmb{x}) + \\alpha^2\\pmb{u}^T\\pmb{u}) =\n",
    "\\frac{d}{d\\alpha}(\\pmb{x}^T\\pmb{x} - 2\\alpha\\pmb{u}^T\\pmb{x} + \\alpha^2) =\n",
    "\\frac{d}{d\\alpha}\\pmb{x}^T\\pmb{x} -2\\frac{d}{d\\alpha}\\alpha\\pmb{u}^T\\pmb{x} + \\frac{d}{d\\alpha}\\alpha^2 = \n",
    "0 - 2\\pmb{u}^T\\pmb{x} + 2\\alpha\n",
    "$$\n",
    "Solving for $\\alpha$,\n",
    "$$\n",
    "0 = -2\\pmb{u}^T\\pmb{x} + 2\\alpha \\\\\n",
    "2\\pmb{u}^T\\pmb{x} = 2\\alpha \\\\\n",
    "\\alpha = \\pmb{u}^T\\pmb{x}\n",
    "$$\n",
    "So\n",
    "$$\n",
    "\\pmb{y} = \\alpha\\pmb{u} =\n",
    "\\pmb{u}^T\\pmb{x}\\pmb{u} =\n",
    "\\pmb{x}^T\\pmb{u}\\pmb{u}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Source: Contributed by James\n",
    "    * Given the definition of the Trace operator, $ Tr(\\pmb{C}) = \\sum_{i=1}^{n}C_{i,i} $, prove that $Tr(\\pmb{AB}) = Tr(\\pmb{BA}) $ for any $\\pmb{A} \\in \\mathbb{R}^{m \\times n} $ and $\\pmb{B} \\in \\mathbb{R}^{n \\times m}$\n",
    "    * Solution:\n",
    "        * Given the definition of a Matrix Product of $\\pmb{C} = \\pmb{AB}$, where $C_{i,j} = \\sum_{k=1}^{n}A_{i,k}B_{k,j}$, then $\\pmb{C} \\in \\mathbb{R}^{m \\times m} $\n",
    "        * This means that for any diagonal element $C_{i,i}$ for $i \\in (1,n)$, since based on the alternative formulation that $ C_{i,j} $  is dot product of row $ i $ of $\\pmb{A}$ and column $ j $ of $ \\pmb{B} $, then $ C_{i,i} $  is dot product of row $ i $ of $\\pmb{A}$ and column $ i $ of $ \\pmb{B} $. In other words,\n",
    "$$\n",
    "C_{i,i} = \\sum_{k=1}^{n}A_{i,k}B_{k,i}\n",
    "$$\n",
    "and \n",
    "$$\n",
    "Tr(C) = \\sum_{i=1}^{m}C_{i,i} =\n",
    "\\sum_{i=1}^{m}\\sum_{k=1}^{n}A_{i,k}B_{k,i}\n",
    "$$\n",
    "Expanding the terms of $Tr(C)$, we get\n",
    "$$\n",
    "Tr(C) = \\\\\n",
    "\\sum_{i=1}^{m}\\sum_{k=1}^{n}A_{i,k}B_{k,i} =  \\\\\n",
    "\\sum_{i=1}^{m}(a_{i,1}b_{1,i} + a_{i,2}b_{2,i} + \\dotsb + a_{i,n}b_{n,i}) = \\\\\n",
    "(a_{1,1}b_{1,1} + a_{1,2}b_{2,1} + \\dotsb + a_{1,n}b_{n,1}) + \\\\\n",
    "(a_{2,1}b_{1,2} + a_{2,2}b_{2,2} + \\dotsb + a_{2,n}b_{n,2}) + \\\\\n",
    "\\vdots  \\\\\n",
    "(a_{m,1}b_{1,m} + a_{m,2}b_{2,m} + \\dotsb + a_{m,n}b_{n,m})\n",
    "$$\n",
    "        * On the other hand let $\\pmb{D} = \\pmb{BA}$, so that $\\pmb{D} \\in \\mathbb{R}^{n \\times n} $ then\n",
    "$$\n",
    "D_{i,i} = \\sum_{k=1}^{m}B_{i,k}A_{k,i}\n",
    "$$\n",
    "and\n",
    "$$\n",
    "Tr(D) = \\sum_{i=1}^{n}D_{i,i} =\n",
    "\\sum_{i=1}^{n}\\sum_{k=1}^{m}B_{i,k}A_{k,i}\n",
    "$$\n",
    "Likewise, expanding the terms of $Tr(D)$, we get\n",
    "$$\n",
    "Tr(D) = \\\\\n",
    "\\sum_{i=1}^{n}\\sum_{k=1}^{m}B_{i,k}A_{k,i} = \\\\\n",
    "\\sum_{i=1}^{n}(b_{i,1}a_{1,i} + b_{i,2}a_{2,i} + \\dotsb + b_{i,m}a_{m,i}) = \\\\\n",
    "(b_{1,1}a_{1,1} + b_{1,2}a_{2,1} + \\dotsb + b_{1,m}a_{m,1}) + \\\\\n",
    "(b_{2,1}a_{1,2} + b_{2,2}a_{2,2} + \\dotsb + b_{2,m}a_{m,2}) + \\\\\n",
    "\\vdots \\\\\n",
    "(b_{n,1}a_{1,n} + b_{n,2}a_{2,n} + \\dotsb + b_{n,m}a_{m,n})\n",
    "$$\n",
    "Rearranging the terms since $ a_{i,j}b_{j,i}  = b_{j,i}a_{i,j} $, we have\n",
    "$$\n",
    "(a_{1,1}b_{1,1} + a_{2,1}b_{1,2} + \\dotsb + a_{m,1}b_{1,m}) + \\\\\n",
    "(a_{1,2}b_{2,1} + a_{2,2}b_{2,2} + \\dotsb + a_{m,2}b_{2,m}) + \\\\\n",
    "\\vdots \\\\\n",
    "a_{1,n}(b_{n,1} + a_{2,n}b_{n,2} + \\dotsb + a_{m,n}b_{n,m})\n",
    "$$\n",
    "and by transposing terms from the columns into rows, we end up with \n",
    "$$\n",
    "(a_{1,1}b_{1,1} + a_{1,2}b_{2,1} + \\dotsb + a_{1,n}b_{n,1}) + \\\\\n",
    "(a_{2,1}b_{1,2} + a_{2,2}b_{2,2} + \\dotsb + a_{2,n}b_{n,2}) + \\\\\n",
    "\\vdots  \\\\\n",
    "(a_{m,1}b_{1,m} + a_{m,2}b_{2,m} + \\dotsb + a_{m,n}b_{n,m})\n",
    "$$\n",
    "which is equal to \n",
    "$$\n",
    "\\sum_{i=1}^{m}(a_{i,1}b_{1,i} + a_{i,2}b_{2,i} + \\dotsb + a_{i,n}b_{n,i}) = \n",
    "\\sum_{i=1}^{m}\\sum_{k=1}^{n}A_{i,k}B_{k,i} =\n",
    "Tr(\\pmb{AB})\n",
    "$$\n",
    "So $Tr(\\pmb{D}) = Tr(\\pmb{BA}) = Tr(\\pmb{AB})$. Q.E.D. :D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Derivation of PCA (to be completed)"
   ]
  },
  {
   "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.7.7"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}