{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "internals": {
     "slide_type": "subslide"
    },
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Least Squares via Calculus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "internals": {},
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# for QR codes use inline\n",
    "%matplotlib inline\n",
    "qr_setting = 'url'\n",
    "#\n",
    "# for lecture use notebook\n",
    "# %matplotlib notebook\n",
    "# qr_setting = None\n",
    "#\n",
    "%config InlineBackend.figure_format='retina'\n",
    "# import libraries\n",
    "import numpy as np\n",
    "import matplotlib as mp\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import laUtilities as ut\n",
    "import slideUtilities as sl\n",
    "import demoUtilities as dm\n",
    "import pandas as pd\n",
    "from importlib import reload\n",
    "from datetime import datetime\n",
    "from IPython.display import Image\n",
    "from IPython.display import display_html\n",
    "from IPython.display import display\n",
    "from IPython.display import Math\n",
    "from IPython.display import Latex\n",
    "from IPython.display import HTML;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__One more proof.__\n",
    "\n",
    "As mentioned, one way to express the least squares problem is:\n",
    "\n",
    "$$\\hx = \\arg\\min_{\\vx}\\Vert A\\vx - \\vb\\Vert$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we write it like this, it is clear that this is a _minimization_ problem (or an _optimization_).\n",
    "\n",
    "We want to find the $\\vx$ that minimizes the function $g(\\vx) = \\Vert A\\vx - \\vb\\Vert$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, we can use standard methods from calculus to find the minimum of this function.\n",
    "\n",
    "Let's see how to do it. It is simpler to minimize \n",
    "\n",
    "$$f(\\vx) = \\Vert A\\vx - \\vb\\Vert^2$$ \n",
    "\n",
    "which has the same minimum as $g(\\vx)$.\n",
    "\n",
    "Let's assume the function is convex (opens upward).  In following lectures, we'll see that this is always true (because $A^TA$ is _positive definite._) Then its minimum occurs where its derivative is zero.\n",
    "\n",
    "$$\\frac{d}{d\\vx}f(\\vx) = 0$$\n",
    "\n",
    "So:\n",
    "\n",
    "$$ f(\\vx) = \\Vert A\\vx - \\vb\\Vert^2 $$\n",
    "\n",
    "$$ = (A\\vx - \\vb)^T(A\\vx - \\vb)$$\n",
    "\n",
    "$$ = (\\vx^TA^T - \\vb^T)(A\\vx - \\vb)$$\n",
    "\n",
    "$$ = \\vx^TA^TA\\vx - \\vb^TA\\vx - \\vx^TA^T\\vb + \\vb^T\\vb$$\n",
    "\n",
    "$$ = \\vx^TA^TA\\vx -  2\\vx^TA^T\\vb + \\vb^T\\vb$$\n",
    "\n",
    "Now, \n",
    "\n",
    "$$ \\frac{d}{d\\vx}f(\\vx) = 2A^TA\\vx - 2A^T\\vb$$\n",
    "\n",
    "Setting the derivative to zero, we confirm the normal equations:\n",
    "\n",
    "$$ A^TA\\vx = A^T\\vb$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how to take the derivative of $\\vx^TA^TA\\vx$.  For simplicity, we'll do this for the case in whcih $A^TA$ is $2\\times 2$.\n",
    "\n",
    "So $$A^TA = \\mat{{cc}a_{11}&a_{12}\\\\a_{21}&a_{22}}.$$  \n",
    "\n",
    "Now $$A^TA\\vx = \\mat{{c}a_{11}x_1 + a_{12}x_2\\\\a_{21}x_1+a_{22}x_2}$$\n",
    "\n",
    "So $$\\vx^TA^TA\\vx = a_{11}x_1^2 + a_{12}x_1x_2 + a_{21}x_2x_1 + a_{22}x_2^2$$\n",
    "\n",
    "Let's denote this function $$h(x_1, x_2) = a_{11}x_1^2 + a_{12}x_1x_2 + a_{21}x_2x_1 + a_{22}x_2^2$$\n",
    "\n",
    "Now $\\frac{d}{d\\vx} \\vx^TA^TA\\vx = \\frac{d}{d\\vx} h(x_1,x_2)$ is defined as a two element vector: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\mat{{c}\\frac{d}{dx_1}h(x_1,x_2)\\\\\\frac{d}{dx_2}h(x_1,x_2)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So $$\\frac{d}{d\\vx} h(x_1,x_2) = \\mat{{c}2a_{11}x_1+a_{12}x_2+a_{21}x_2\\\\2a_{22}x_2+a_{12}x_1+a_{21}x_1}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Now $A^TA$ is symmetric, so $a_{12} = a_{21}$.   So the above is the same as:\n",
    "\n",
    "$$\\frac{d}{d\\vx} h(x_1,x_2) = \\mat{{c}2a_{11}x_1+2a_{12}x_2\\\\2a_{21}x_1+2a_{22}x_2}= 2A^TA \\vx.$$"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}