{"nbformat_minor": 0, "cells": [{"execution_count": 32, "cell_type": "code", "source": "Pkg.rm(\"Homework\")\nPkg.clone(\"https://github.com/shashi/Homework.jl.git\")\nusing Homework", "outputs": [{"output_type": "stream", "name": "stderr", "text": "INFO: Removing Homework (unregistered)\nINFO: Cloning Homework from https://github.com/shashi/Homework.jl.git\nINFO: Computing changes...\nINFO: No packages to install, update or remove\n"}], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": 59, "cell_type": "code", "source": "Homework.progress()", "outputs": [{"output_type": "display_data", "data": {"text/plain": "Options{:ToggleButtons,ASCIIString}([Input{ASCIIString}] score,\"report\",\"score\",\"Score\",[\"Score\"=>\"score\",\"Incorrect attempts\"=>\"attempts\"])", "text/html": ""}, "metadata": {}}, {"execution_count": 59, "output_type": "execute_result", "data": {"text/plain": "1x16 DataFrame\n| Row | Names | 1a | 1b |\n|-----|-------|------------------------|------------------------|\n| 1 | \"MAX\" | Colored(\"black\",\"2.0\") | Colored(\"black\",\"1.0\") |\n\n| Row | 1c | 2 |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"1.0\") | Colored(\"black\",\"2.0\") |\n\n| Row | 3 | 4a |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"2.0\") | Colored(\"black\",\"0.5\") |\n\n| Row | 4b | 4c |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"1.0\") | Colored(\"black\",\"0.5\") |\n\n| Row | 5a | 5b |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"1.0\") | Colored(\"black\",\"1.0\") |\n\n| Row | 6a | 7a |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"2.0\") | Colored(\"black\",\"2.0\") |\n\n| Row | 7b | 7c |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"2.0\") | Colored(\"black\",\"2.0\") |\n\n| Row | total |\n|-----|-----------------------|\n| 1 | Colored(\"black\",20.0) |", "text/html": "
Names1a1b1c234a4b4c5a5b6a7a7b7ctotal
1MAX2.01.01.02.02.00.51.00.51.01.02.02.02.02.020.0
"}, "metadata": {"reactive": true, "comm_id": "db023df2-7ac8-4f42-ba66-eec7db7a31a7"}}], "metadata": {"collapsed": false, "trusted": true}}, {"source": "## 1. Linear Transformations\n\n1a (2 pts) Which transformations with input v=(v$_1$,v$_2$) are linear?

\n\n1. T(v)=(v$_2$,v$_1$)
\n2. T(v)=(v$_1$,v$_1$)
\n3. T(v)=(0,v$_1$)
\n4. T(v)=(0,1)
\n5. T(v)=v$_1$-v$_2$
\n6. T(v)= v$_1$v$_2$\n\nFormat: If 1,2,and 6 are linear write [1,2,6] etc.\n\n", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "1a", "collapsed": false, "max_score": 2, "trusted": true, "max_attempts": 2}}, {"source": "1b (1 pt) Which transformations satisfy T(v+w)=T(v)+T(w). The input is v=(v$_1$,v$_2$,v$_3$).

\n\n1. T(v)=v/$\\|v\\|$
\n2. T(v)=v$_1$+v$_2$+v$_3$
\n3. T(v)=(v$_1$,2v$_2$,3v$_3$)
\n4. T(v) = largest component of v\n\nFormat: If 1 and 4 work write [1,4] etc.", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "1b", "collapsed": false, "max_score": 1, "trusted": true, "max_attempts": 2}}, {"source": "1c (1 pt.) Which transformations satisfy T(cv)=cT(v). The input is v=(v$_1$,v$_2$,v$_3$)\n\n\n1. T(v)=v/$\\|v\\|$
\n2. T(v)=v$_1$+v$_2$+v$_3$
\n3. T(v)=(v$_1$,2v$_2$,3v$_3$)
\n4. T(v) = largest component of v\n\nFormat: If 1 and 4 work write [1,4] etc.", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "1c", "collapsed": false, "max_score": 1, "trusted": true, "max_attempts": 2}}, {"source": "## 2. Transpose as a Linear Transformation\n\n(2 pts.) The transformation T that transposes every matrix is definitely linear. Which of these extra properties are true? \n\n1. T$^2$ = the identity transformation.
\n2. The kernel of T is the zero matrix.
\n2. Every matrix is in the range of T.
\n4. T(M) = \u2212M is impossible\n\nFormat: If 1 and 4 are true write [1,4] etc.\n\n", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "2", "collapsed": false, "max_score": 2, "trusted": true, "max_attempts": 2}}, {"source": "## 3. Derivative as a Linear Transformation\n\n(2 pts.) The transformation S takes the second derivative. Let 1,x,x$^2$,x$^3$ be an ordered basis for degree 3 polynomials in x. Find the 4 by 4 matrix B for S with respect to this ordered basis.\n\nFormat: [[1 2 3 4],[1 2 3 4],[1 2 3 4],[1 2 3 4]]", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "3", "collapsed": false, "max_score": 2, "trusted": true, "max_attempts": 5}}, {"source": "## 4. Fibonacci Matrix SVD\n\nLet the SVD of $A=\\left[\\begin{matrix}1 & 1\\\\1 & 0\\end{matrix}\\right]$\nbe $A=U\\Sigma V^T$ where the first row of $U$ is positive.\n\nEnter U, $\\Sigma$ and $V$ numerically, we will check a few decimal places.\n\n(If you want to use Julia, try -svd(A)[1], diagm(svd(A)[2]), -svd(A)[3] to\nmatch the format of MITx)\n\n4a.(.5 pts) U=", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "4a", "collapsed": false, "max_score": 0.5, "trusted": true, "max_attempts": 5}}, {"source": "4b.(1 pt) $\\Sigma$=", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "4b", "collapsed": false, "max_score": 1, "trusted": true, "max_attempts": 5}}, {"source": "4c. (.5 pts) V=", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "4c", "collapsed": false, "max_score": 0.5, "trusted": true, "max_attempts": 5}}, {"source": "## 5. Constructing a matrix of rank one\n\n5a (1 pt.) What is the matrix A with rank one that has Av=12u for v=$\\frac{1}{2}$(1,1,1,1) and u=$\\frac{1}{3}$(2,2,1)?\n\n", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "5a", "collapsed": false, "max_score": 1, "trusted": true, "max_attempts": 5}}, {"source": "5b. (1 pt.) What is the (non-zero) singular value of $A$?", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "5b", "collapsed": false, "max_score": 1, "trusted": true, "max_attempts": 5}}, {"source": "## 6. Singular Value Decomposition of a Symmetric Matrix\n\n6a. (2 pts.)\nSuppose A is a 2 by 2 symmetric matrix with unit eigenvectors u$_1$ and u$_2$ and corresponding eigenvalues \u03bb$_1$=3 and \u03bb$_2$=\u22122. What are possible singular value decompositions for A?\n\n1. U=(u$_1$,u$_2$), $\\Sigma=\\left[\\begin{matrix}3 & 0\\\\0 & -2\\end{matrix}\\right]$, V=(u$_1$,u$_2$)
\n2. U=(u$_1$,-u$_2$), $\\Sigma=\\left[\\begin{matrix}3 & 0\\\\0 & 2\\end{matrix}\\right]$, V=(u$_1$,u$_2$)
\n3. U=(u$_1$,u$_2$), $\\Sigma=\\left[\\begin{matrix}3 & 0\\\\0 & 2\\end{matrix}\\right]$, V=(u$_1$,u$_2$)
\n4. U=(u$_1$,u$_2$), $\\Sigma=\\left[\\begin{matrix}3 & 0\\\\0 & 2\\end{matrix}\\right]$, V=(u$_1$,-u$_2$)
\n\nFormat: If 1 and 4 work write [1,4] etc.", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "", "outputs": [], "metadata": {"question": "6a", "collapsed": false, "max_score": 2, "trusted": true, "max_attempts": 2}}, {"source": "## 7. Linear Fitting of Data\n\n\nSuppose you have the following 3 dimensional points:\n\n{\u27e80,2,1\u27e9,\u27e80,4,3\u27e9,\u27e81,4,5\u27e9,\u27e81,8,6\u27e9,\u27e81,8,10\u27e9,\u27e84,8,14\u27e9,\u27e85,9,13\u27e9}

\nWe'd like to find the best fit plane that will fit these data points. There are many ways that we can attempt this.\n\nWe can use least squares approximation\n\n$\\begin{bmatrix} x_1 & y_1 & 1 \\\\ x_2 & y_2 & 1\\\\ x_3 & y_3 & 1 \\\\ \\vdots & \\vdots & \\vdots \\end{bmatrix} \\begin{bmatrix} A\\\\ B \\\\ C \\end{bmatrix} = \\begin{bmatrix} z_1 \\\\ z_2 \\\\ z_3 \\\\ \\vdots \\end{bmatrix}\n$\n\nto find the best fit plane of the form z=Ax+By+C.\nHowever, you might ask yourself why is the z-coordinate on the right, and x and y on the left?\nWhy should z be different? This strategy \nassumes that the x and y coordinates are correct, and the error is all in the z-direction, perpendicular to the xy-plane.\n\nWe could instead assume the error is along the x or the y direction and use least square approximation to find the best fit plane of the form x=Ay+Bz+C or y=Ax+Bz+C. However, each of these methods makes a pretty strong assumption about in which direction the error or noise in the data occurs.\n\nAnother method is to make an assumption that the data is mostly correct, and lies on some plane, and that the error is small in comparison. A priori, we make no assumption about the direction of this error. This method is called principal component analysis and applies SVD. Let's see how.\n\nPRINCIPAL COMPONENT ANALYSIS\n\nWe will explain this method in the context of the problem we are using. Let A be the matrix whose rows are the data of 3 dimensional points above. However, a more general method is described below. First, find the mean data point \u03bc=[\u03bc$_x$ \u03bc$_y$ \u03bc$_z$]. We use this mean to create a matrix M with zero mean by taking the rows of A and subtracting \u03bc from each row.\n\nOnce we find the plane P that the data in M lie on, the data from A lie on P+\u03bc.\n\nQuestion: Which plane do the data in M come from? The answer is to use SVD. If we look at svd(M), we get M=USV$^T$. S has 3 nonzero singular values if our data is not already on a plane. However, one singular value will be smaller than the other two. The matrix V=[v$_1$ v$_2$ v$_3$] consists of orthogonal vectors. The conjecture is that the data come from the plane spanned by v$_1$ and v$_2$, and that the error occurs in the direction of v$_3$. Because v$_3$ corresponds to the smallest singular value, this minimizes the magnitude of the error in this data.\n\nGENERAL PRINCIPAL COMPONENT ANALYSIS\n\nSuppose your data is a collection of m-dimensional vectors: D=[d$_1$, \u2026, $d_n$]. But we suppose that this data should fit some k-dimensional subspace. It doesn't because there is error, noise that is perpendicular to this k-dimensional subspace. The question posed is: what subspace did this data most likely come from? And what dimension is that subspace?\n\nMethod.\n\n* Find the expected value of your data \u03bc=$\\sum_{i=1}^n d_i/n$.\n\n* Create a new, zero mean matrix M whose ith row is d$_i$\u2212\u03bc.\n\n* Find svd(M)=USV$^T$.\n\n* Identify k such that \u03c3$_k$>>\u03c3$_{k+1}$.\n\n* Conjecture that data came from the span of \u03bc and the first k columns of V. These vectors are called the principal components.", "cell_type": "markdown", "metadata": {"collapsed": true}}, {"source": "7a) (2 pts)\n\n\nThis problem is exercise 14.4 in \n\n\u201cLinear Algebra and Probability for Computer Science Applications\", by Ernest Davis.\n\nConsider the following set of three dimensional points we introduced earlier.\n\n{\u27e80,2,1\u27e9,\u27e80,4,3\u27e9,\u27e81,4,5\u27e9,\u27e81,8,6\u27e9,\u27e81,8,10\u27e9,\u27e84,8,14\u27e9,\u27e85,9,13\u27e9}\nFind the least squares estimate for z taken as a linear combination of x and y; e.g. z=ax+by+c.\n\nDefine a matrix A whose rows are the data above:", "cell_type": "markdown", "metadata": {}}, {"execution_count": 20, "cell_type": "code", "source": "# Complete A (currently with three points) to the seven data points (not graded) \nA= [ 0 2 1\n 0 4 3\n 1 4 5 ]\n\n\n# Also obtain A_ls (least squares)\nA_ls = [A[:,1:2] ones(size(A,1))]\nz = A[:,3]", "outputs": [{"output_type": "display_data", "data": {"text/plain": "Html(\"\")", "text/html": ""}, "metadata": {}}, {"output_type": "display_data", "data": {"text/plain": "Html(\"\")", "text/html": ""}, "metadata": {}}, {"execution_count": 20, "output_type": "execute_result", "data": {"text/plain": "3-element Array{Int64,1}:\n 1\n 3\n 5"}, "metadata": {}}], "metadata": {"collapsed": false, "trusted": true, "alert": "info"}}, {"source": "Let zz be the data predicted by the least squares approximation. (You can use backslash: \"\\\" )
\nCompute norm(zz-z), the norm of the difference between zz and the actual data for the z-coordinates ", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "# Fill in the blanks for two points\nzz = ?? #(Hint: Use A_ls, z, *, and \\ )\nnorm(z-zz)", "outputs": [], "metadata": {"collapsed": false, "question": "7a", "precision": 3, "max_score": 2, "trusted": true, "max_attempts": 5}}, {"source": "7b) ( 2 pts.)\n\n\nTake the same data from before.\n\n{\u27e80,2,1\u27e9,\u27e80,4,3\u27e9,\u27e81,4,5\u27e9,\u27e81,8,6\u27e9,\u27e81,8,10\u27e9,\u27e84,8,14\u27e9,\u27e85,9,13\u27e9}
\nThis time, find the least squares estimate for x as a linear combination of y and z; e.g. x = A + By + Cz. Do you think the error will be larger or smaller than in part (a)? Compute norm(x-xx)\n", "cell_type": "markdown", "metadata": {}}, {"execution_count": null, "cell_type": "code", "source": "A_ls = # Use 2:3 this time\nx=\nxx = # Use x this time\nnorm(x-xx)", "outputs": [], "metadata": {"collapsed": false, "question": "7b", "precision": 3, "max_score": 2, "trusted": true, "max_attempts": 5}}, {"source": "7c) (2 pts.)\n\nLooking at the same data one last time.\n\n{\u27e80,2,1\u27e9,\u27e80,4,3\u27e9,\u27e81,4,5\u27e9,\u27e81,8,6\u27e9,\u27e81,8,10\u27e9,\u27e84,8,14\u27e9,\u27e85,9,13\u27e9}
\nFind the best-fit plane from a principal component analysis. Use U,S,V = svd(A) to find the 3 singular value decomposition of A. (Julia stores the diagonal of S as a vector which is less wasteful than storing a whole matrix)", "cell_type": "markdown", "metadata": {}}, {"execution_count": 47, "cell_type": "code", "source": "# We can't grade you but try to understand how this works\n\u03bc = mean(A,1)\nM = broadcast(-,A,\u03bc) # Make mean 0\nU,S,V = svd(M)\nbest_fit = broadcast(+, U[:,1:2]*diagm(S[1:2])*V[:,1:2]', \u03bc) # Make rank 2 and add back mean", "outputs": [{"execution_count": 47, "output_type": "execute_result", "data": {"text/plain": "7x3 Array{Float64,2}:\n -0.14732 1.94221 1.08145\n 0.0728165 4.02856 2.95974\n 1.1453 4.05699 4.91967\n 0.449134 7.78393 6.30457\n 1.96438 8.37827 9.4668 \n 4.4242 8.16639 13.7655 \n 4.0915 8.64365 13.5023 "}, "metadata": {}}], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": null, "cell_type": "code", "source": "# For two points create a vector of length three which\n# has norm(best_fit[:,j]-A[:,j]) for j=1:3\n\n", "outputs": [], "metadata": {"collapsed": false, "question": "7c", "precision": 3, "max_score": 2, "trusted": true, "max_attempts": 5}}, {"source": "## 8. COMPRESSION ALGORITHMS\n\n(5 pts.) The following is a classical example of an application of svd, although it is not typically used for image compression .\n\nA compression algorithm \u03a6 takes in data D and constructs a representation E=\u03a6(D) such that:\n\nThe computer memory required to record E is less than that required by natural encoding of D.\n\nThere is a decompression algorithm \u03a8 to reconstruct D from E. If \u03a8(E)=D, the algorithms \u03a6 is called lossless compression. If \u03a8(E) is approximately D, then \u03a6 is called lossy compression.\n\nThe singular value decomposition gives lossy compression algorithms.\n\nSuppose image data is stored in an m by n matrix M, let USV$^T$=svd(M). Choose k<Homework.create_problemset(); Homework.refresh_messages()\")", "text/html": ""}, "metadata": {}}], "metadata": {"collapsed": false, "trusted": true}}, {"execution_count": 56, "cell_type": "code", "source": "Homework.progress()", "outputs": [{"output_type": "display_data", "data": {"text/plain": "Options{:ToggleButtons,ASCIIString}([Input{ASCIIString}] score,\"report\",\"score\",\"Score\",[\"Score\"=>\"score\",\"Incorrect attempts\"=>\"attempts\"])", "text/html": ""}, "metadata": {}}, {"execution_count": 56, "output_type": "execute_result", "data": {"text/plain": "1x16 DataFrame\n| Row | Names | 1a | 1b |\n|-----|-------|------------------------|------------------------|\n| 1 | \"MAX\" | Colored(\"black\",\"2.0\") | Colored(\"black\",\"1.0\") |\n\n| Row | 1c | 2 |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"1.0\") | Colored(\"black\",\"2.0\") |\n\n| Row | 3 | 4a |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"2.0\") | Colored(\"black\",\"0.5\") |\n\n| Row | 4b | 4c |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"1.0\") | Colored(\"black\",\"0.5\") |\n\n| Row | 5a | 5b |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"1.0\") | Colored(\"black\",\"1.0\") |\n\n| Row | 6a | 7a |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"2.0\") | Colored(\"black\",\"2.0\") |\n\n| Row | 7b | 7c |\n|-----|------------------------|------------------------|\n| 1 | Colored(\"black\",\"2.0\") | Colored(\"black\",\"2.0\") |\n\n| Row | total |\n|-----|-----------------------|\n| 1 | Colored(\"black\",20.0) |", "text/html": "
Names1a1b1c234a4b4c5a5b6a7a7b7ctotal
1MAX2.01.01.02.02.00.51.00.51.01.02.02.02.02.020.0
"}, "metadata": {"reactive": true, "comm_id": "afdbfebc-c071-4032-a2ad-4ff74df61b32"}}], "metadata": {"collapsed": false, "trusted": true}}], "nbformat": 4, "metadata": {"kernelspec": {"display_name": "Julia 0.3.6", "name": "julia 0.3", "language": "julia"}, "language_info": {"version": "0.3.6", "name": "julia"}, "homework": {"course": "MIT-18.06", "admins": ["mit.edelman@gmail.com"], "mode": "answering", "problemset": "pset9"}}}