{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "View the description of this assignment at [http://www.cs.ubc.ca/~nando/540-2013/lectures/homework2.pdf](http://www.cs.ubc.ca/~nando/540-2013/lectures/homework2.pdf)"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Exercise 1"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The ridge method solves the following minimization problem\n",
      "$$\\min_{\\boldsymbol{\\theta} \\in \\mathbb{R}^d} \\|\n",
      "\\mathbf{y} - \\mathbf{X}\\boldsymbol{\\theta} \\|^{2}_{2} +\n",
      "\\delta^2 \\| \\boldsymbol{\\theta} \\|^2_2$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This expression can be written as\n",
      "$$\\left( \\mathbf{y} - \\mathbf{X}\\boldsymbol\\theta \\right)^T\\left( \\mathbf{y} - \\mathbf{X}\\boldsymbol\\theta \\right)\n",
      "+ \\delta^2 \\boldsymbol\\theta^T \\boldsymbol\\theta =\n",
      "\\mathbf{y}^T\\mathbf{y} + \\boldsymbol\\theta^T\\mathbf{X}^T\\mathbf{X}\\boldsymbol\\theta\n",
      "- 2 \\boldsymbol\\theta^T\\mathbf{X}^T\\mathbf{y}\n",
      "+ \\delta^2\\boldsymbol\\theta^T\\boldsymbol\\theta$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "to find the minimum we differentiate w.r.t. $\\boldsymbol\\theta$ and set it equal to zero\n",
      "$$2\\mathbf{X}^T\\mathbf{X}\\boldsymbol\\theta -\n",
      "2 \\mathbf{X}^T \\mathbf{y} +\n",
      "2 \\delta^2 \\boldsymbol\\theta =0$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$\\boldsymbol\\theta = \\delta^{-2} \\left( \\mathbf{X}^T\\mathbf{y} - \\mathbf{X}^T\\mathbf{X}\\boldsymbol\\theta \\right) =\n",
      "\\mathbf{X}^T\\boldsymbol\\alpha$$\n",
      "where $\\boldsymbol\\alpha = \\delta^{-2}\\left( \\mathbf{y} - \\mathbf{X}\\boldsymbol\\theta \\right)$"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Exercise 2"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lemma:\n",
      "$$A \\left( A^TA + aI \\right)^{-1} = \\left( AA^T + aI \\right)^{-1} A$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Proof:\n",
      "Multiply both sides by $\\left( A^TA + aI \\right)$ to get:\n",
      "$$A = \\left( AA^T + aI \\right)^{-1} A \\left( A^TA + aI \\right)$$\n",
      "$$=\\left( AA^T + aI \\right)^{-1} \\left( AA^TA + aA \\right)$$\n",
      "$$=\\left( AA^T + aI \\right)^{-1} \\left( AA^T + aI \\right)A = A \\; \\blacksquare$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "From exercise 1 we know that\n",
      "$$\\boldsymbol\\alpha = \\delta^{-2}\\left( \\mathbf{y} - \\mathbf{X}\\boldsymbol\\theta \\right)$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "so now we substitute $\\boldsymbol\\theta$ and then apply the matrix identity that we have proved before\n",
      "$$\\boldsymbol\\alpha = \\delta^{-2}\\left( \\mathbf{y} - \\mathbf{X} \n",
      "\\left( \\mathbf{X}^T\\mathbf{X} + \\delta^2I \\right)^{-1} \\mathbf{X}^T\\mathbf{y} \\right)$$\n",
      "$$=\\delta^{-2}\\left( I - \n",
      "\\left( \\mathbf{X}\\mathbf{X}^T + \\delta^2I \\right)^{-1} \\mathbf{X}\\mathbf{X}^T \\right)\\mathbf{y}$$\n",
      "$$=\\delta^{-2} \\left( \\mathbf{X}\\mathbf{X}^T + \\delta^2I \\right)^{-1}\n",
      "\\left( \\left( \\mathbf{X}\\mathbf{X}^T + \\delta^2I \\right) - \\mathbf{X}\\mathbf{X}^T \\right)\\mathbf{y}$$\n",
      "$$=\\left( \\mathbf{X}\\mathbf{X}^T + \\delta^2I \\right)^{-1}\\mathbf{y}$$"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}