Sections7.1-7.4.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "7.1 The Curse of Dimensionality"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"http://yaroslavvb.com/research/reports/curse-of-dim/pics/sphere.gif\">\n",
      "\n",
      "The ratio between (1) a hypersphere with radius r and (2) a hypercube with sides of length 2r, in D dimensions:\n",
      "\n",
      "$f_2\\approx78.5\\%$\n",
      "\n",
      "$f_3\\approx52.3\\%$\n",
      "\n",
      "$f_D=\\frac{V_D(r)}{2r^D}=\\frac{\\pi^{D/2}}{D2^{D-1}\\Gamma(D/2)}$\n",
      "\n",
      "$\\lim_{D \\to \\inf} f_D = 0$\n",
      "\n",
      "E.g. for a sample of $3.57\\times10^{8}$ SDSS spectra, each described by 30 attributes (flux, size, ellipticity, etc.), the probability of having one source reside within the hypersphere would be only $7\\times10^{-6}$.\n",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from scipy import *\n",
      "import numpy as np\n",
      "from scipy import special\n",
      "from pylab import *\n",
      "%matplotlib inline\n",
      "\n",
      "D = arange(2,50)\n",
      "fD = pi**(D/2)/(D*2.0**(D-1.0)*special.gamma(D/2.0))\n",
      "loglog(D, fD, linewidth=3)\n",
      "xlabel('D')\n",
      "ylabel('$f_D$')\n",
      "show()\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAZcAAAEWCAYAAACqitpwAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xt0lNW5x/FvIICAKKABCcMxKMilgFEbqlBKhKIgQjhQ\nINACQigKTXLwFMRbj5SiRxR1AR6J4VbBw6VcJCxTYkMwFD0aVKCiIBcBheAFpRAMUCCZ88c2TAKB\nZDIz2e/M/D5rzfLdk5k3T9pZ87Df/e7niXC73W5ERET8qIbtAEREJPQouYiIiN8puYiIiN8puYiI\niN8puYiIiN8puYiIiN8puYiIiN8puYiIiN9F2g7AF4WFhUyYMIE6deoQHx/P8OHDbYckIiIE+cxl\nzZo1DBkyhPT0dNatW2c7HBER+ZHjksuYMWNo2rQpHTt2LPN8VlYWbdu2pXXr1syYMQOA/Px8WrRo\nAUDNmjWrPVYRESmf45LL6NGjycrKKvNcUVERycnJZGVlsXPnTpYtW8auXbtwuVwcOnQIgOLiYhvh\niohIORyXXLp160ajRo3KPLdlyxZatWpFTEwMtWrVIjExkYyMDAYOHMjq1auZMGEC/fv3txSxiIhc\nLCgW9Etf/gJwuVzk5eVRr149Fi5ceMX3Nm/enCNHjgQ6RBGRkBIdHU1+fn6V3++4mUt5IiIiqvze\nI0eO4Ha7g/rRu7cbcANP/fjfqj0iItw0a+amc2c3gwa5efhhNy++6GbVKjd5eW6OHHFTVFT2dz/1\n1FN+/3t8PWdV3+/N+yr72ope5+vPg+Vh6+8Ilc+njc9mRa/x9R/lQTFzad68+YW1FYBDhw7hcrks\nRlS91q+HggJYvTqeG26AQ4fM48svPf89fBj+9a8rn8fthq++Mo8tW8p/Ta1a4HLBv/0btGgBZ8/G\n88gj5r3FxZd/ePPzgoJ45s6FHj3gllvA2387xMfHe/eGKryvsq+t6HVVjTXY2Po7A/F7fT1nVd5v\n47Pp7e/1VoTb7XZcs7CDBw/Sr18/duzYAcD58+dp06YNOTk5REdH07lzZ5YtW0a7du0qPFdERAQO\n/BP9zu2Go0fLJpyLk9CRI+Z1ThIdDXffbRJNjx4QE2M7ouo1depUpk6dajsMkUv4+t3puOQybNgw\nNm3axPfff0+TJk2YNm0ao0ePZv369UycOJGioiKSkpJ47LHHKnW+cEkulXHunEkwl0s+X34Jx47Z\njTEmxiSZu+82j+bN7cYTaLm5uWEzu5HgEnLJxd+UXLxTWGgusZUknG+/hRo1zKWrGjUufVTl+fx8\nePttyM2FEyeuHE+bNp6ZTXw8REVVx/8KIqLkUgElF+cqKoJt20yi2bgRNm82ye1KOnaE7t2haVOo\nW9fzqFev7Pji5+rXh6uvrp6/SyQUKLlUQMkleJw7Bx98YBLNxo3wf/9X8U0K3mjXDsaPh5Ej4dpr\n/XdekVCk5FIBJZfgdeYMvPeeZ2aTlwfnz/t+3vr1YcQI+N3voEMH388nEoqUXCqg5BI6fvgB3n0X\ntm41x6dPm8epU57jy41PnDAzo4t1726SzIAB5jZsETGUXCqg5CJgktHrr8P//A988smlP4+OhnHj\nzKNZs+qPT8Rpwj65ZGRkkJmZSUFBAUlJSfTq1avMz5VcpDS3G/7+d5Nk1qwxNxWUFhkJAwdCYqLZ\nRNqsGTRpolmNhJ+wTy4ljh8/zqRJk5g/f36Z55Vc5HKOHIH0dHj1Vfj668u/LiICrr/eJJrSj+ho\n6N0bWrWqvphFqkvIJJcxY8aQmZlJkyZNLuzMB9PHpWTz5NixY5kyZUq57580aRK/+c1viI2NLfO8\nkotU5OxZeOMNM5vZvNm790ZGwn/8B/zXf8E11wQmPhEbQia5bN68mauvvpqRI0deSC5FRUW0adOG\nDRs20Lx5c+Li4li2bBkffvghW7duZfLkyTRr1oxHH32Ue+65h549e15yXiUX8cbHH8OiRfDZZ546\nbEePVlw2p1kzeP55GD7c+1ppIk4UMskFLq0p9t577/HHP/7xQvOwZ599FoBHH330wntmz57N4sWL\niYuLIzY2lgcffLDMOZVcxFfnz5tKBSXJpuSRnQ3vvFP2td26wcsvQ6dOdmIV8RdfvzsdXRX5cn1c\nSktNTSU1NfWK54mPjycmJoaYmBji4+NVy0m8Ehlp1leio8s+/4c/wLJlMGmSSTZgLqvdfru5vfmP\nf4SGDas/XpGqyM3NJTc3l4MHD3Lw4EGfz+fo5OJLH5fScnNz/XIekdIiIsxlsH794E9/gpdeMrOc\noiKYPdsknqefhvvuM4lJl8vEyS7+h7ev37+ObhYW7n1cJDg0aADPPWfWa0ov+x09avbNuFzQqBH8\n/Ofw0EPmstnbb5ufi4QqRyeXn/70p+zdu5eDBw9y9uxZVqxYQf/+/W2HJVKudu3MOszKlWaPTGkn\nTpjqAq++CikppspzkyZwxx3lb+oUCXaOSS7Dhg2jS5cu7NmzhxYtWrBo0SIiIyN5+eWXuffee2nf\nvj1Dhw6tVIMwEVsiIuBXv4Jdu8ylsq5dr1wkc+tW+NnPYPny6otRpDo46m6xQNDdYmKb22162Hzy\niXl8+qn578cfmz02JSZONJfXVA1AnCCkbkUOBCUXcapPPjGlZvbu9TzXrRv85S9www324hIB3787\nHXNZTCTcdOhg+tckJHieK7mV+d137cUl4g9KLiIWXXutKaD5zDOmDTSYPTPx8WafzD/+AcXFVkMU\nqRJdFhNxiOxsGDYMvv++7PPXXWf6ztx9t3m0b689MxJ4WnOpgJKLBJMvvoBBg+Cjjy7/mpgY+POf\nTcIRCZSwX3MpLCwkLi6OzMxM26GI+OzGG816y4IFMGQIREVd+pqDB6FPH9iwodrDE6m0oJ+5PPXU\nUzRo0IB27drRt2/fS36umYsEM7cbdu40O/o3boScHCgoMD+76ipYuxbuvddujBKaQmLmMmbMGJo2\nbUrHjh3LPJ+VlUXbtm1p3bo1M2bMuOR92dnZtG/fnqjy/nknEgIiIuAnP4HkZLPw/9FHppwMwJkz\n0L8/aNIuTuSImUtVe7m88sorFBYWsnPnTurWrcsbb7xxSbE1zVwk1Ozfbxb2v/zSjGvVMiVnSt/S\nLOKrkFnQr0ovlxKvvfYaUVFR3HfffZf8TMlFQtEXX5gEc+CAGUdGmirMv/qV3bgkdIRsP5fK9HIp\nMWrUqCueS/1cJNTceCP8/e8mwezbZ0r9Dx5sNmAOGwZDh15aPFPkSsKmn4u/ermA+rlIaHK5YNMm\nU2F5927z3Nat5jF5sinxP3w4jBkDderYjVWcL2z6uaiXi0jFoqNNghk6FGrXLvuzd96BCRPM3WSl\nC2SKVAfHJhf1chGpnKZNTcn+b76BRYvgnnugZk3PzzdtMk3KtPQo1ckRyUW9XER817AhPPAAvPUW\nHDkCkyZ5frZoETz/vLXQJAw55m6xQNHdYhKu3G6z3vLnP5txRASsXg3//u9Ww5IgETK3IgeKkouE\ns7NnoVcvc2cZQL16nrL+Ilei5FIBJRcJd999B3feCZ9/bsbR0aZ+WUyM1bDE4UKi/IuIBM7118Ob\nb5reMWDWY9q0gdGjTatlkUDQzEUkTGzYAL17Q1FR2ed79oQpU8zlM5ESmrmISKX88pemIdldd5V9\nPifH3L786qt24pLQFNQzF7fbzZNPPsnJkyf56U9/ysiRIy95jWYuIpd6/3146SVYtcrTRvmqq+CD\nD6BDB7uxiTOE9cxl7dq15OfnU7t2be3eF/HCnXfCihVmkb9TJ/PcmTOmLtmZM3Zjk9DgiORS1X4u\ne/bsoWvXrsycOZO5c+dWV7giISMmxlRTvuoqM/7kE7P+IuIrRySX0aNHXyitX6KoqIjk5GSysrLY\nuXMny5YtY9euXSxZsoSHH36YI0eO4HK5aNiwIQA1ajjiTxEJOu3bw4svesazZ8Nf/2ovHgkNjllz\nqUo/l9OnT5OSkkK9evVo164d48ePv+S8WnMRqZjbDQMGwLp1ZtykiblNuWlTu3GJPWHdz6Vu3brM\nnz+/wnOpn4vIlUVEwPz5Zv3l66/h229NKf8XXzRVlSX0qZ9LFaifi0jFoqJg8WJzWzLAzp1mX0yv\nXvDccxAbazc+CSz1cxGRgOnVC+bONTXISmRnm1pk5XQYF7ksxyYX9XMRseOhh0zr5N/+Fkruk3G7\nYcYMyMiwG5sED0ckF/VzEXGWZs0gPR127IDSS5QpKfDDD9bCkiDimLvFAkV3i4n45tgxaNsWjh41\n4//8T3jhBbsxSeCF9Q59EQm8xo3LJpNZs2D7dnvxSHDQzEVEKuR2m+rJb79txj/7mekJU7Om3bgk\ncDRzEZGAi4gwd5HVrm3GeXmQlmY3JnE2JRcRqZQ2bcrejpySAhMnQmGhvZjEuXRZTEQq7cwZuO02\n+Owzz3M33QQLF0L37vbiEv8L68tihw8fZuDAgSQlJZVbNVlE/Ouqq0xzsT59PM/t329uV543z1pY\n4kBBnVx27NjBoEGDWLBgAdu2bbMdjkhYiI6GzExYtAiuvdbz/O9/77ldWcQRyaWq/Vy6dOlCeno6\nPXv2pHfv3tUVrkjYi4iABx4w9cduucU8d/IkTJ9uNSxxEEesuWzevJmrr76akSNHXii5X1RURJs2\nbdiwYQPNmzcnLi6OZcuW8eGHH7J161YmT57MX/7yF+644w66devG4MGDWbly5SXn1pqLSGCtWwcJ\nCea4Vi3YtQtuvtluTOK7kFhz6datG40aNSrz3JYtW2jVqhUxMTHUqlWLxMREMjIyGDFiBC+99BLR\n0dH06NGDWbNmMX78eFq2bGkpepHw1q8f/Pzn5vjcOXjiCbvxiDM4tuR+Zfq5dOrUiVWrVlV4LvVz\nEQmciAhTkr9LFzNescKsv8TF2Y1LvKN+LlWgfi4igXXXXTBoEKxebcaPPAIbN5rEI8FB/VxExJGe\necZTDiY3FwYPhoICqyGJRY5NLurnIhJcbrkFkpM949WroXNn+PRTezGJPY5ILurnIhIann/elIUp\nsXu3STCbNtmLSexwxK3IgaRbkUWq39KlppPlqVNm3K4dfPKJp7OlOF9I3IosIqFl+HBTOblBAzPe\ntQveeMNuTFK9lFxEJCA6dIDf/c4znj7d9IWR8KDLYiISMN9+CzExcPq0Gb/5JvTtazUkqSRdFhMR\nx2rSBB580DP+0580ewkXmrmISEAdOQItW8LZs2a8YYNpmSzOFlYzlwMHDjB27FgGDx4MQGFhIaNG\njWLcuHEsXbrUcnQiUp7oaEhK8ownToRvvrEXj1SPoEouLVu2ZP78+RfGa9asYciQIaSnp7Nu3TqL\nkYnIlUyZApE/Fpv65BNTh2zfPrsxSWBZSS5V7d9ysdLFLWuW1J0QEce58UZIT/fsc9m/3ySYjz6y\nG5cEjpXkMnr0aLKysso8V1RURHJyMllZWezcuZNly5axa9culixZwsMPP8yRI0cuOY/L5bpQf6y4\nuLhaYheRqhk92ux1ueoqMz561JTrP3PGblwSGFaqInfr1u2Sks6l+7cAF/q3PProo4wYMQKAY8eO\n8fjjj7Nt2zZmzJhBSkoKycnJZGZmXrHumEruizhD//6Qk2NuRz5+HL76yuzmHzPGdmQSsiX3K9O/\npXHjxqSlpZV5buHChRWeWyX3RZyjSxd4/HFTlh9g1iwzq1F5frtCtuS+P/u3iIizjR0L9eqZ448/\nNiX6JbQ4Jrmof4tI+GjUCEaN8oxnzbIXiwSGY5KL+reIhJfUVM/xunXw+ef2YhH/s5Jc1L9FRNq2\nhd69zbHbDXPm2I1H/EvlX0TEmqws6NPHHNesCStWwKBBdmMSw9fvTiUXEbGmuBjuvBM++MCMIyNh\n1SpISLAbl4RZbTERCS01apj1lltuMePz52HwYPjb3+zGJb7TzEVErMvPh+7dPYv6N90Ee/eqLbJN\nmrmISNBr3hzefhsaNjTj/fth40a7MYlvlFxExBFatICRIz3j9HR7sYjvgiq5XNzPJSMjg3HjxpGY\nmEh2drbl6ETEV7/9red47VpT3FKCU1All4v7uSQkJJCenk5aWhorVqywGJmI+EOHDnDXXeb43Dl4\n7TW78UjVBXU/lxLTp08nOTnZ32GKiAWlZy/z5pkNlhJ8grqfi9vtZsqUKfTp04fY2NjqCl9EAmjI\nELjmGnO8Z4+KWgaroOznsn37dp599lnq169PTk4OBQUF7Nu3jwcffLDc36d+LiLBo359+PWvYe5c\nM05Kgvfeg6ZN7cYV6vzdz8XaPpeDBw/Sr18/duzYAcCqVat46623mDdvHgCvv/46eXl5zPGx4JD2\nuYgEn717ITYWTp0y486dza3KJWX6JfBCZp+L+rmISInWrU2dsZJNlFu2wG9+o/WXYOKY5KJ+LiJS\n2v33l62U/MYbZvYiwcExyUX9XETkYhMmwAMPeMZLllgLRbykfi4i4mjjx3uOV6/2rMOIs6lwpYg4\nmtttGovt2WPGy5ZBYqLdmMJByCzoi4iUJyLCLOaXeP11e7FI5WnmIiKOt38/3HyzOa5ZE44cgSZN\n7MYU6jRzEZGQd9NN0LWrOS4qguXL7cYjFVNyEZGg8GOhDgD++7/hq6/sxSIV02UxEQkKJ06YzZUl\nZfi7djX7XmrVshtXqAqry2IX93MBKCwsJC4ujszMTIuRiUigXXutuVOsZNf+u+/CpEl2Y5LLq1Jy\n2b9/P1OmTGHatGlldtUH2sX9XACee+45hg4dWm0xiIg9PXvCM894xrNnwz/+YS8eubwqJZc333yT\nqVOnMnz4cJYuXUpeXp5X7/dXP5fs7Gzat29PVFSUV79fRILXI49A796esRb3nalKyaVTp07UrVuX\nVq1aMWXKFL744guv3u+vfi6bNm3i/fffZ+nSpcybN09rKyJhICKi7K79lStV0NKJqtTPZebMmeze\nvZtu3brRvn17oqOjvXq/P/q5zJgxg+nTpwPw2muvERUVddnKyurnIhJa7rkHGjSAkyfh889h+3a4\n7TbbUQU3f/dzqTC5rF27ltjY2Atf+gAvvPACZ86cYePGjcyZM4dDhw7x5ptv+hRIfn4+LVq0uDB2\nuVyXXG5r3LgxaWlpl7x31KhRVzx3rlrZiYSUq66C/v3hf//XjFeuVHLx1cX/8Pa1DUqFyWXTpk24\nXC5iYmLIyMggISGBNm3aAHDrrbcC8Omnn/oUBKifi4h4Z8iQssnl6afNJTNxhgqTS79+/Xj66ac5\nc+YMp0+fZs+ePXTs2JGOHTvSvHlzAH7yk5/4HIj6uYiIN0pfGtu3z9w1FhtrOyopUeGCfo8ePXjj\njTdYv349/fr1o3Pnzuzfv5+nn36aAQMGkJyczO7du30ORP1cRMQbJZfGSsyday8WuZTPO/SXL1/O\noUOHmDx5cqXfM2zYMDZt2sT3339PkyZNmDZtGqNHj2b9+vVMnDiRoqIikpKSeOyxx3wJDdAOfZFQ\n9te/Qt++nvH69WVvU5aq8/W70+fksmbNGmrVqkW/fv18OU3AKLmIhC63GwYMgHXrzLhpU9ixA7T1\nzXfWk4vTKbmIhLajR6FTJ/j6azMeMgRWrLAbUyhQcqmAkotI6MvKgj59zHGNGvDtt3DddXZjCnZh\nVbhSRKQ8vXvDXXeZ4+JiUB1b+5RcRCQklL5zrGQNRuzRZTERCQm7dkH79ua4fn347jtzu7JUTVhd\nFru4n0txcTFPPPEEqampLF682HJ0ImJT27bQqpU5LiyEjRvtxhPugiq5XNzPJSMjg/z8fGrXrq3d\n/CJhLiICEhI8Y10as8tKcvFXP5c9e/bQtWtXZs6cyVxtzxUJexcnl+Jie7GEOyvJxV/9XFwuFw0b\nNgSgRo2gmoSJSADcdZfnFuSvvoIFC+zGE86q1M/FV772c9m2bRszZswgNTWVlJQUNm/efMUeLern\nIhIeIiPhoYdMhWSAyZNNeRgvW06FJX/3c7F2t9jBgwfp168fO3bsAGDVqlW89dZbzJs3D4DXX3+d\nvLw85syZ49Pv0d1iIuHl9Gm49VbYu9eMBwyANWtUjt9bIXO3mPq5iIg/1K0LP/4bFYC1a2HzZnvx\nhCvHJBf1cxERf+neHUaO9IzXrrUXS7hyTHJRPxcR8adhwzzH69fbiyNcWUkuw4YNo0uXLuzZs4cW\nLVqwaNEiIiMjefnll7n33ntp3749Q4cOpV27djbCE5EQ0L27Z4f+Z5+BH9aoxQsq/yIiIeu++zyz\nlldegfHj7cYTTEJmQV9ExN9KyvCDLo1VN81cRCRk7dsHrVub4/r14fvvoU4duzEFC81cREQuo1Wr\nssUsc3OthhNWlFxEJKTdd5/n+KmnVG+suii5iEhIS0mB2rXNcV4eqDtH9Qiq5HJxP5fDhw8zcOBA\nkpKSKlVFWUTCT6tWMGmSZzxlCpw4YS+ecBFUyeXifi47duxg0KBBLFiwgG3btlmMTESc7PHHoaTg\nx7ffQnq63XjCQVD3c+nSpQvp6en07NmT3r17BypcEQly9evDH/7gGb/1lr1YwkVQ93NZtGgR06dP\nJycnh8zMzOoKX0SCUOmF/XfeMdWTJXCCsp/L9u3bmTFjBn369GHatGksXbqUli1bXvb3qZ+LiLhc\n0LatKQXzr3/Bu+/CL39pOyrn8Hc/FyvJpTz5+fm0aNHiwtjlcpGXl1fmNY0bNyYtLa3Mc6tWrarw\n3Lm6uV1EMMnks8/M8YYNSi6lXfwPb1/boDhmQV/9XEQk0Eonk+xse3GEA8ckF/VzEZFAi4+HmjXN\n8bZt8N13VsMJaY5JLurnIiKBdu210LmzOXa7NXsJJPVzEZGwcs89nuMZM1QOJlBUFVlEwspXX5ld\n+6dOmfHixfDjDalSiqoii4h4oVkz+P3vPeMnn4QzZ+zFE6qUXEQk7EyeDFFR5vjLL2H5crvxhCIl\nFxEJOw0awMSJnnFOjr1YQpWSi4iEpdIL+7m55u4x8Z+gWtDPyMggMzOTgoICkpKS6Nq1K+PHj6dO\nnTrEx8czfPjwS96jBX0RKc/583DddVBQYMb79sHNN9uNyUl8/e4MquRS4vjx40yaNIn4+HgaNWpE\n3759SUxMZHk5F06VXETkcu6/H0pq3s6fD0lJduNxkqC8W8zXkvvTp08nOTmZw4cPX9jFX7Nk262I\nSCV17+45VglC/wqqkvtut5spU6bQp08fYmNjcblcHD58GIBi7YQSES+VLpCudRf/CqqS+7NnzyYn\nJ4eCggL27dvHiBEjSE5OJjMzU6ViRMRrt91m7hw7eRIOH4bPPzcbLMV3QVVyPzU1ldTU1DLPLVy4\nsMJzq5+LiJQnMhJ+8QvPuktaGsycaTcmW0K2n0sgS+6rn4uIXM5vf+tJLq+8ApMmwQ032I3JhpDt\n56KS+yJiQ//+cPvt5vj0aVPMUnznmOSikvsiYkNEBEyd6hmnpcE//2ktnJChkvsiEvbuvx9Kdkac\nOQObN9uNJxQE5SZKb2gTpYhUxqRJ8MIL5njyZHjuObvx2BaUmyhFRJzm5z/3HL/zjr04QoVmLiIi\nwNGj0KSJOa5VC06cgLp17cZkk2YuIiJ+EBUFbdua43Pn4IMP7MYT7JRcRER+pEtj/qPkIiLyIyUX\n/wmqNZeL+7mcOnWqzLhXr16XvEdrLiJSWaVri9WrB4cOQePGdmOyJaz7ucyfP7/ccWlKLiJSWW43\n3Hor7NhhxtOmwR/+YDcmW4JyQd9f/VwuNxYRqYqICHjkEc941iwoLLQXTzAL6n4uF49FRHyVmAg/\ndv7g+++hEoXXpRxB3c/l7NmzZcYPPvhgNf8lIhJqIiPNbv2SiyErV0JKit2YgpFjSu5XtZ9LSiX+\nX1c/FxHxxsCBnuTy4Ydm30utWnZjCjT1c6kC9XMREW80awY33ghffGHK8H/8Mdxxh+2oAkv9XERE\nqsGdd3qO33vPXhzByjHJRf1cRMRJ7rrLc6zk4j31cxERKUfp5PL++/biCFZBuYnSG9pEKSJVcfYs\nXHMN/OtfZvzNN56qyeEgKDdRiog4Xe3aZRfxVWvMO0ouIiKX8YtfeI4XLLAXRzDSZTERkcvYuxfa\ntDE1xwA++8yMw4Eui4mIBEjr1nD//Z7x7Nn2Ygk2mrmIiFzBxo3Qs6c5rlfPtEOuV89uTNUhrGYu\nGRkZjBs3jsTERLKzswEoLCwkLi6OzMxMy9GJSCi6+25Pj5dTp2DrVrvxBIugSi4JCQmkp6eTlpbG\nihUrAHjuuecYOnSo5chEJFRFRECXLp7xBx/YiyWYBHU/l+zsbNq3b09UVFSgQxaRMNa5s+d4yxZ7\ncQSToO7nsmnTJt5//32WLl3KvHnztLYiIgFROrlo5lI5Qd3PZfr06QC89tprREVFBbSysoiEr06d\nTMn9c+fg889NE7HrrrMdlbM5puR+Vfu5AIwaNeqK51Y/FxHxRZ06EBvrmbV8+CHce6/dmPxN/Vyq\nQP1cRMRXcXGe5LJlS+glF/VzERGxoPS6y8aN9uIIFo5JLurnIiJO1rMn1PjxGzM3F/bssRqO46mf\ni4hIJbhcZUvBpKXZiyUYqPyLiEglvfUW9O5tjhs1gsOHQ7cUTFiVfxERsalXL7j5ZnP8z3/C3/5m\nNx4nU3IREamkGjVgwADP+MMP7cXidEouIiJeKN2d8qOP7MXhdEouIiJeuDi5aEm3fFrQFxHxQnEx\nNGwIJ0+a8aFD5k6yUBNWC/oX93Nxu9088cQTpKamsnjxYtvhiUgYqFEDbr/dM9alsfI5pvxLZSQk\nJJCQkMDx48eZNGkShYWF5Ofnc/3112s3v4hUm9tvh02bzPHWrZCQYDceJwrqfi67d++ma9euzJw5\nk7lz5wY6bBERQIv6lRHU/VxcLhcNGzY0f0iNoLrCJyJBrHRy2bzZtD+WsoK6n8vIkSNJSUlh8+bN\nKqMvItWmTRto3Rr27oWCAli9Gn78mpIfOWbNpar9XObPn1/hudXPRUT8KSICxoyBxx4z4wULgj+5\nqJ9LFaifi4j426hR8OSTUFRkFvf37jWzmWClfi4iIg7QrBncd59nnJlpLxYnckxyUT8XEQk2vXp5\njrdvtxcA+0hIAAAEaUlEQVSHE6mfi4hIFcXGeo6VXMpS+RcRkSoqKIBrrzXHkZHwww9Qp47dmPwl\nrMq/iIg4yTXXePq7nD8PO3fajcdJlFxERHygS2PlU3IREfGBkkv5lFxERHxQOrls22YvDqfRgr6I\niA/y8z39XBo0gOPHTVn+YOfrd6djduhXRkZGBpmZmRQUFJCUlES7du1ITU2lUaNG3HLLLUyZMsV2\niCISZqKj4frr4exZM4s5cQIaNbIdlX1BOXMp6ecyaNAgjh07xq9//WsSExNZvnz5Ja/VzEWcLDc3\nV7XuQsDXX0OTJqExYykRlLci+6ufS5cuXUhPT6dnz5707t070GGL+J3q3oWGG24IrcTiD0Hdz2XR\nokVMnz6dnJwcMsOgsI+NL6JA/E5fz1nV93vzvsq+tqLXhUvysPV3hsrn08Zn09vf6y0ryaVbt240\nuuiiZOl+LrVq1brQz2XEiBG89NJLREdHM2fOHHJycli1ahWvvvoqPXr0YNasWYwfP56WLVva+FOq\nlZKLb+9XcgkcJRff3h+KyQW3JQcOHHB36NDhwnjlypXusWPHXhgvWbLEnZyc7PPviY6OdgN66KGH\nHnp48YiOjvbpu9cxd4sFqp9Lfn5+QM4rIiKX55glKPVzEREJHY5JLurnIiISOtTPRURE/C4oN1GK\niIizOeaymIiIhI6wSy6FhYWMGjWKcePGsXTpUtvhiJRx4MABxo4dy+DBg22HIlJGRkYG48aNIzEx\nkezs7ApfH3aXxZYsWULjxo3p27fvZeuRidg2ePBgVq5caTsMkUuU1HacP3/+FV8XEjMXb2qV5efn\n06JFCwBq1qxZ7bFK+PG1lp5IoFTls1lS27EiIZFcvKlV5nK5LuynKS4uthGuhBlvPp8i1cmbz6b7\notqOFQmJ5OJNrbKBAweyevVqJkyYoH00Ui28+XweO3aMhx56iO3bt2s2IwHnzWfz5ZdfLlPbsSKO\nKf/ib6UvfwG4XC7y8vKoV68eCxcutBiZyOU/n40bNyYtLc1iZBLuLvfZnDNnDikpKZU+T0jMXMoT\nqFplIv6gz6c4lb8+myGbXFSrTJxMn09xKn99NkM2uahWmTiZPp/iVP76bIZEclGtMnEyfT7FqQL5\n2Qy7TZQiIhJ4ITFzERERZ1FyERERv1NyERERv1NyERERv1NyERERv1NyERERv1NyERERv1NyEalm\nNWvW5LbbbqNDhw7Exsby4osvou1mEmpCtiqyiFPVq1ePbdu2AXD06FGGDx9OQUEBU6dOtRuYiB9p\nh75INWvQoAEnT568MD5w4ABxcXF89913FqMS8S9dFhOxrGXLlhQVFXH06FHboYj4jZKLiIj4nZKL\niGX79++nZs2aREVF2Q5FxG+UXEQsOnr0KA899JBX7WNFgoEW9EWqWWRkJB07duTcuXNERkYycuRI\nHn74YbU+lpCi5CIiIn6ny2IiIuJ3Si4iIuJ3Si4iIuJ3Si4iIuJ3Si4iIuJ3Si4iIuJ3Si4iIuJ3\n/w9iRXB9GerJdgAAAABJRU5ErkJggg==\n",
       "text": [
        "<matplotlib.figure.Figure at 0x103a9f490>"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "<u>``Intrinsic dimensionality'' come to resecue!</u><br>\n",
      "Find these dimensions or axes to reduce the dimensionality of the data."
     ]
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "7.2 The Data Sets Used in This Chapter"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<a class=\"reference internal image-reference\" href=\"http://www.astroml.org/_images/fig_spec_examples_1.png\"><img alt=\"../../_images/fig_spec_examples_1.png\" class=\"align-center\" src=\"http://www.astroml.org/_images/fig_spec_examples_1.png\" style=\"width: 500.0px; height: 400.0px;\" /></a><p>Figure 7.1</p>\n",
      "<p>A sample of 15 galaxy spectra selected from the SDSS spectroscopic data set\n",
      "(see Section 1.5.5). These spectra span a range of galaxy types, from\n",
      "star-forming to passive galaxies. Each spectrum has been shifted to its rest\n",
      "frame and covers the wavelength interval 3000-8000 Angstroms. The specific\n",
      "fluxes, <img class=\"math\" src=\"http://www.astroml.org/_images/math/832cd0d9dc73b2a4d16fa92d6500d2dcacb1df60.png\" alt=\"F_\\lambda(\\lambda)\"/>, on the ordinate axes have an arbitrary\n",
      "scaling. There are 1000 wavelength bins (or 1000 dimensions).</p>\n"
     ]
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "7.3 Principal Component Analysis (PCA)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<strong>PCA Steps</strong>: First, find the first axis that maximize the variance of the data. Then, find a second axis that is orthogonal to the first axis and maximize the residual variance, and so on. \n",
      "\n",
      "<img src=\"http://georgemdallas.files.wordpress.com/2013/10/pca3.jpg?w=400\">\n",
      "Find principal components for these data.\n",
      "\n",
      "<img src=\"http://georgemdallas.files.wordpress.com/2013/10/pca9.jpg?w=400\"> \n",
      "Nah.\n",
      "\n",
      "<img src=\"http://georgemdallas.files.wordpress.com/2013/10/pca8.jpg?w=400\">\n",
      "Good!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"http://www.astroml.org/_images/fig_PCA_rotation_1.png\" style=\"width: 500.0px; height: 500.0px;\">\n",
      "<p>Figure 7.2</p>\n",
      "<p>A distribution of points drawn from a bivariate Gaussian and centered on the\n",
      "origin of x and y. PCA defines a rotation such that the new axes (x&#8217; and y&#8217;)\n",
      "are aligned along the directions of maximal variance (the principal components)\n",
      "with zero covariance. This is equivalent to minimizing the square of the\n",
      "perpendicular distances between the points and the principal components.</p>\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**3 ways to do PCA**\n",
      "\n",
      "+ SVD of $X$\n",
      "+ eigenvalue decomposition of $C_X$\n",
      "+ eigenvalue decomposition of $M_X$\n",
      "\n",
      "$X$ is a $N \\times K$ matrix, of $N$ observations and $K$ features (dimensions). \n",
      "\n",
      "$X$ can be decomposed to:\n",
      "\n",
      "$U\\Sigma V^T = \\frac {1} {\\sqrt{N-1}}X$, where $V^T$ and $U$ are rotations, and $\\Sigma$ is a scaling.\n",
      "\n",
      "$C_X = \\frac{1}{N-1}X^TX = R C_Y R^T = R \\Sigma^2 R$ (covariance matrix)\n",
      "\n",
      "$M_X = \\frac{1}{N-1}XX^T = U \\Sigma^2 U^T$ (correlation matrix)\n",
      "\n",
      "\n",
      "where R are the eigenvectors (or principal components), diagonal terms of $C_Y$ define the amount of variance contained within each component.\n",
      "\n",
      "$R=V=\\frac{1}{\\sqrt{N-1}} X^T U \\Sigma^{-1}$\n",
      "\n",
      "<img src='http://i.stack.imgur.com/IM6Fn.png' width=600>\n",
      "\n"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Application to SDSS data"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "<img src=\"http://www.astroml.org/_images/fig_spec_decompositions_1.png\" style=\"width: 500.0px; height: 400.0px;\">\n",
      "\n",
      "<p>Figure 7.4</p>\n",
      "<p>A comparison of the decomposition of SDSS spectra using PCA (left panel -\n",
      "see Section 7.3.1), ICA (middle panel - see Section 7.6) and NMF (right panel\n",
      "- see Section 7.4). The rank of the component increases from top to bottom. For\n",
      "the ICA and PCA the first component is the mean spectrum (NMF does not require\n",
      "mean subtraction). All of these techniques isolate a common set of spectral\n",
      "features (identifying features associated with the continuum and line\n",
      "emission). The ordering of the spectral components is technique dependent.</p>\n",
      "\n",
      "<img src=\"http://www.astroml.org/_images/fig_eigenvalues_1.png\" style=\"width: 500.0px; height: 375.0px;\" >\n",
      "<p>Figure 7.5 ``'scree plot'</p>\n",
      "<p>The eigenvalues for the PCA decomposition of the SDSS spectra described in\n",
      "Section 7.3.2. The top panel shows the decrease in eigenvalue as a function\n",
      "of the number of eigenvectors, with a break in the distribution at ten\n",
      "eigenvectors. The lower panel shows the cumulative sum of eigenvalues\n",
      "normalized to unity. <strong>94% of the variance in the SDSS spectra can be captured\n",
      "using the first ten eigenvectors</strong>.</p>\n",
      "\n",
      "<img src=\"http://www.astroml.org/_images/fig_spec_reconstruction_1.png\" style=\"width: 500.0px; height: 500.0px;\">\n",
      "<p>Figure 7.6</p>\n",
      "<p>The reconstruction of a particular spectrum from its eigenvectors. The input\n",
      "spectrum is shown in gray, and the partial reconstruction for progressively\n",
      "more terms is shown in black. The top panel shows only the mean of the set of\n",
      "spectra. By the time 20 PCA components are added, the reconstruction is very\n",
      "close to the input, as indicated by the expected total variance of 94%.</p>\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Choosing the Level of Truncation**\n",
      "\n",
      "+ Too many components will introduce noise\n",
      "\n",
      "+ Too few may not capture the complete physical correlations\n",
      "\n",
      "+ Most common criterion: set a bound (normally 0.7-0.95) on the amount of variance we want to capture\n",
      "\n",
      "+ Cut at the turning point in the scree plot\n",
      "\n",
      "+ If not sharp turn, then use a log scree plot instead (if noise decay geometrically, variation in the eigenvalues should drop as a linear function??)\n"
     ]
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "7.4 Non-negative Matrix Factorization (NMF)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "I don't understand.."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Jia Liu 4/21/2014"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}