{ "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": {} } ] }