{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "View the assignment description [here](http://www.cs.ubc.ca/~nando/540-2013/lectures/homework1.pdf)"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Exercise 1"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$\\newcommand{\\vect}[1]{\\boldsymbol{\\mathbf{#1}}}$\n",
      "The cost function is defined by:\n",
      "$$J(\\vect x_u) = \\sum _{i=1} ^n c_{ui} \\left( p_{ui} - \\vect x_u \\vect y_i \\right)^2 +\n",
      "\\lambda \\| \\vect x_u \\| _2 ^2$$\n",
      "where $\\vect x_u \\in \\mathbb R^{1 \\times f}$ and $\\vect y_i \\in \\mathbb R^{f \\times 1}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The first term can be rewritten as\n",
      "$$\\sum _{i=1} ^n c_{ui} \\left( \\vect p_u - \\vect x_u \\vect Y \\right)_i \\left( \\vect p_u - \\vect x_u \\vect Y \\right)_i$$\n",
      "where $\\vect p_u \\in \\mathbb R^{1 \\times n}$ and $\\vect Y \\in \\mathbb R^{f \\times n}$,\n",
      "so that $\\left( \\vect p_u - \\vect x_u \\vect Y \\right) \\in \\mathbb R^{1 \\times n}$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Using the definition of the dot product we can then rewrite the first term as\n",
      "$$\\left( \\vect p_u - \\vect x_u \\vect Y \\right)\n",
      "\\left[ \\begin{array}{c}\n",
      "c_{u1}\\left( \\vect p_u - \\vect x_u \\vect Y \\right)_1 \\\\\n",
      "\\vdots \\\\\n",
      "c_{un}\\left( \\vect p_u - \\vect x_u \\vect Y \\right)_n \\end{array} \\right]$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "And finally by using the definition of matrix multiplication the first term become\n",
      "$$\\left( \\vect p_u - \\vect x_u \\vect Y \\right)\n",
      "\\vect C_u\n",
      "\\left( \\vect p_u - \\vect x_u \\vect Y \\right)^T$$\n",
      "where $\\vect C_u = \\left[ \\begin{array}{ccc}\n",
      "c_{u1} & 0 & 0 \\\\\n",
      "0 & \\ddots & 0 \\\\\n",
      "0 & 0 & c_{un} \\end{array} \\right]$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The second term can be rewritten as\n",
      "$$\\lambda \\| \\vect x_u \\| _2 ^2 = \\lambda\\sum_{i=1}^n x_{ui}^2 \n",
      "= \\lambda \\vect x_u \\vect x_u^T$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So we have showed that\n",
      "$$J(\\vect x_u) =\n",
      "\\left( \\vect p_u - \\vect x_u \\vect Y \\right)\n",
      "\\vect C_u\n",
      "\\left( \\vect p_u - \\vect x_u \\vect Y \\right)^T\n",
      "+ \\lambda \\vect x_u \\vect x_u^T$$"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Exercise 2"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To find $\\hat{\\vect x}_u$ we differentiate $J(\\vect x_u)$ w.r.t. $\\vect x_u$ and set it equal to zero.\n",
      "$$J(\\vect x_u) = \\vect p_u \\vect C_u \\vect p_u^T - 2\\vect p_u \\vect C_u \\vect Y^T \\vect x_u^T\n",
      "+ \\vect x_u \\vect Y \\vect C_u \\vect Y^T \\vect x_u^T\n",
      "+ \\lambda \\vect x_u \\vect x_u^T$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$\\frac \\partial {\\partial\\vect x_u} J(\\vect x_u) = \n",
      "-2 \\vect p_u \\vect C_u \\vect Y^T + 2 \\vect x_u \\vect Y \\vect C_u \\vect Y^T \n",
      "+ 2 \\lambda \\vect x_u = 0$$"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$\\hat{\\vect x}_u = \\vect p_u \\vect C_u \\vect Y^T \\left( \\vect Y \\vect C_u \\vect Y^T \n",
      "+ \\lambda I\\right)^{-1}$$"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}