{
 "metadata": {
  "name": "",
  "signature": "sha256:e53ded21cad7027a87852a2c6de534aca80aab06af2223be74aae95ca3908826"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import os\n",
      "import sys\n",
      "import glob\n",
      "import matplotlib.pyplot as plt\n",
      "import numpy as np\n",
      "import pandas as pd\n",
      "%matplotlib inline\n",
      "%precision 4\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "u'%.4f'"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "u = np.array([1,2,3]).reshape((-1,1))\n",
      "c = np.diag([1,2,3])\n",
      "np.dot(u. T, np.dot(c, u))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "array([[36]])"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Lecutre outline\n",
      "----\n",
      "\n",
      "- Preliminaries\n",
      "    - $u, v, w, x, b, \\beta$ are general $n \\times 1$ (column) vectors\n",
      "    - $u^T, v^T, w^T, w^T, x^T, b^T, \\beta^T$ are $1 \\times n$ (row) vectors\n",
      "    - $A, M, X$ are $(m \\times n)$ matrices with $m$ rows and $n$ columns\n",
      "    - $i, j$ will be used to indicate row and columnn indices in a matrix\n",
      "    - Will often write a system of linear equations in matrix form as either $Ax = b$ or $X\\beta = y$ depending on context \n",
      "    - Names for special matrices\n",
      "        - square\n",
      "        - symmetric, skew symmetric\n",
      "        - diagnoal\n",
      "        - upper and lower tringular\n",
      "- Many problems in statistics can be reformulated as solving systems of linear equations\n",
      "    - Important because we have *efficient* methods of solving larges sets of linear equations\n",
      "    - Otherwise many large problems would be simply comptuationally intractable\n",
      "    - System of linear equations in matrix form\n",
      "- Solving systems of linear equationss with square matrices\n",
      "    - LU Decomposition\n",
      "        - Review of Gaussian elimination\n",
      "        - Gaussain elimination as series of elmeentary reow and permuation matrix mutliplications\n",
      "        - Derivation of PA = LU (our first matrix decomposition)\n",
      "        - Solving $Ax = b$ by back-substtituion\n",
      "        - Comparing LU with using $x = A^{-1}b$\n",
      "        - Numerical example\n",
      "    - Cholesky (square root decomposition)\n",
      "        - Postive defintite matrices\n",
      "            - $uT A u$ > 0 for any conforming vector $u$\n",
      "            - Equivalent to requiring all eigenvalues > 0\n",
      "            - Equivalent to triangular matrix with all entires on diagonal > 0\n",
      "        - covariance matrices as positive defintie matrices\n",
      "        - The Cholesky decomposition $A = LL^T$\n",
      "        - Numerical example\n",
      "        \n",
      "- Solving systems of equations with $n \\times m$ matrices\n",
      "    - Review of matrices and linear algebra\n",
      "        - Linear independence\n",
      "        - Dot product in Euclidean space\n",
      "        - Orthgonal vectors\n",
      "        - Inner prodcut as geenralization of dot product\n",
      "        - Vector spaces as generalization of Euclidean space\n",
      "        - Matrix norms\n",
      "            - Vector p-norms\n",
      "            - Induced vector p-norms\n",
      "            - Elementwise norms\n",
      "                - Frobenius norm\n",
      "            - Submultiplicative property\n",
      "        - Eigendecomposition\n",
      "            - Eigenvalues and eigenvectors\n",
      "            - Singular values\n",
      "            - Spectrum\n",
      "            - Spectral radius $\\rho(A)$\n",
      "                - Any induced matrix norm $\\le$ spectral radius\n",
      "        - [Four fundamental subspaces]((http://www.eng.iastate.edu/~julied/classes/CE570/Notes/strangpaper.pdf))\n",
      "            - column space of matrix is image (rnange) of coresponding transformation\n",
      "            - dim(column space) = rank\n",
      "            - left null space (the null space of $A^T$) is the orthogonal complement to the column space of A.\n",
      "            - kernel of matrix\n",
      "            - kernel as solution set to homogeneous equations\n",
      "            - row space\n",
      "            - kernel is orthogonal complement of row space\n",
      "            - solution to non-homogeneous equations \n",
      "                - solution of Ax = b is a translation of the kernel by a vector v \n",
      "            - simple matrix example\n",
      "            - rank-nullity theorem\n",
      "        - 3 ways of interpreting a linear matrix equation\n",
      "            - Element view\n",
      "            - Row view\n",
      "            - Column view (conceptually most useful)\n",
      "    - The Projection operator\n",
      "        - idempotent\n",
      "        - let $P$ be a projection on $W$. Then $W = U + V$ where $U$ is the range(column space)  of $P$ and $V$ is the kernel of $P$\n",
      "        - $P$ is the identity operator for $U$ - if $x \\in U$, $Px = x$\n",
      "        - every vextor $x$ in $W$ is decomposable into $u \\in Px$ and $v \\in (I-P)x$\n",
      "        - eigenvalues of a projection operator are only 0s or 1s\n",
      "        - an orthogonal projection - $U$ and $V$ are orthogonal subspaces $<Px, (I-P)y> = 0$\n",
      "        - orthogonal projections are self-adjoint $<Av, w> = <v, Aw>$\n",
      "        - orthogonal projections are bounded\n",
      "        - orthogonal projection onto a line $P = uu^T$\n",
      "        - orthogonal projection onto orthonormal basis $P = AA^T$ if the columns $u$ of A are orthonormal\n",
      "        - If $u$ are not orthonormal, then $P = A(A^TA)^{-1}A^T$\n",
      "        - $(A^TA)^{-1}$ is a normalizing factor (u^Tu)^{-1} means divide by length in 1D\n",
      "        - diagonalization of P\n",
      "        - centering matrix as an example of a projection (onto subspace of vectors whose components sum to zero)\n",
      "    - Eigendecomposition\n",
      "    - SVD\n",
      "    - Condition numebr of a matrix\n",
      "        - [Prove](http://nm.mathforcollege.com/mws/gen/04sle/mws_gen_sle_spe_adequacy.pdf) that $\\frac{||\\Delta X||}{||X + \\Delta X||} \\le ||A||||A^{-1}||\\frac{||\\Delta A||}{||A||}$\n",
      "        - the number $\\kappa = ||A||||A^{-1}||$ is the condition number of a matrix\n",
      "        - If the conditioning number is huge, check\n",
      "            - Can the variabels be rescaled to reduce the condiiton number?\n",
      "            - Use preconditioning - i.e. instead of $AX - b = 0$, solve $P^{-1}(AX - b) = 0$ where $P^{-1}A$ has a smaller condition number than $A$.  Unfortunately, there is no easy way to choose an appropriate pre-conditionner $P$.\n",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import os\n",
      "import sys\n",
      "import glob\n",
      "import matplotlib.pyplot as plt\n",
      "import numpy as np\n",
      "import pandas as pd\n",
      "%matplotlib inline\n",
      "%precision 4\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "u'%.4f'"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = np.array([1,2,3])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "np.dot(x,x)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "14"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}