\documentclass[11pt]{article}
\usepackage{fullpage,url}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
%\usepackage{latexsym}
%\usepackage{bbm}
\usepackage[normalem]{ulem}

\usepackage[letterpaper,top=1in,bottom=1in,left=1in,right=1in,nohead]{geometry}

\setlength{\parindent}{0in}
\setlength{\parskip}{6pt}



\newcommand{\s}[1]{\textsf{#1}}
\renewcommand{\c}[1]{\ensuremath{\EuScript{#1}}}
\renewcommand{\b}[1]{\ensuremath{\mathbb{#1}}}
\renewcommand{\Pr}{\textbf{\s{Pr}}}
\newcommand{\E}{\textbf{\s{E}}}
\newcommand{\Var}{\textbf{\s{Var}}}
\newcommand{\rank}{\ensuremath{\mathsf{rank}}}
\renewcommand{\span}{\ensuremath{\mathsf{span}}}
\newcommand{\diag}{\ensuremath{\mathsf{diag}}}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}


\begin{document}
\thispagestyle{empty}
{\large{\bf CS 3190: Foundations of Data Analysis \hfill Due: Tuesday 11.16 at 11:50 pm}}\\

{\LARGE{\bf Homework 4: Gradient Descent on Data and PCA}}

\noindent\rule[0.5ex]{\linewidth}{1pt}

{\bf Instructions:} Your answers are due {\color{red} at 11:50pm.}
You {\color{red} must turn in a pdf through} canvas.  I recommend using latex (\url{http://www.cs.utah.edu/~jeffp/teaching/latex/}, see also \url{http://overleaf.com}) for producing the assignment answers.  If the answers are too hard to read you will lose points, entire questions may be given a $0$
(e.g. \textbf{sloppy pictures with your phone's camera are not ok, but very careful ones are}) 

Please make sure your name appears at the top of the page. 

You may discuss the concepts with your classmates, but write up the answers entirely on your own.   {\bf Be sure to show all the work involved in deriving your answers! If you just give a final answer without explanation, you may not receive credit for that question.}

\noindent\rule[0.5ex]{\linewidth}{1pt}

We will use two datasets, here:
\url{http://www.cs.utah.edu/~jeffp/teaching/FoDA/X4.csv},
here \url{http://www.cs.utah.edu/~jeffp/teaching/FoDA/Y4.csv},
 and here:\\
\url{http://www.cs.utah.edu/~jeffp/teaching/FoDA/A.csv}
\\
There are many ways to import data in python, the \texttt{genfromtext} command in numpy provides an easy solution.  

\begin{enumerate}
\item \textbf{[50 points] }
Using data set \texttt{X4.csv} use these $n (= 30)$ rows as the explanatory variables $x \in \b{R}^3$ in a linear regression problem.  Note the first column is always $1$, so you do not need to deal specially with the offset.  Then use data set \texttt{Y4.csv} as the corresponding dependent $y$ value.  
On parts (c) and (f) of this problem, you will run gradient descent on $\alpha \in \b{R}^3$, using the dataset provided to find a linear model
\[
\hat y = \alpha_0 x_0 + \alpha_1 x_1 + \alpha_2 x_2 = \alpha_0 + \alpha_1 x_1 + \alpha_2 x_2
\]
minimizing the sum of squared errors.  You will run for as many steps as you feel necessary.  On parts (c) and (f) of this problem, on each step of your gradient descent run, print on a single line:
(i) the value of a function $f$, estimating the sum of squared errors,
and 
(ii) the norm of the gradient of $f$, and
(iii) the parameters you found ($[\alpha_0, \alpha_1, \alpha_2]$) at that step. 
For notation purposes, let $y_i$ refer to the $i$th entry of $y$, and for $j \in \{0,1,2\}$, let $x_{ji}$ refer to the $i$th entry of the $j$th explanatory variable $x_j$
\begin{enumerate}
\item For the batch gradient descent method, write down a function $f(\alpha_0,\alpha_0,\alpha_0) = \, ?$ that evaluates the loss function. After filling in ?, report the value of the loss function at $(\alpha_0 = 0, \alpha_1 = 1, \alpha_2 = 1)$ and also at $(\alpha_0 = 3, \alpha_1 = 2, \alpha_2 = 4)$.
\item For the function you wrote down in part (a), write down the gradient function. i.e $\nabla f(\alpha_0,\alpha_1,\alpha_2) = \, ?$ that evaluates the gradient of the loss function. After filling in ?, report the value of $\nabla f$ at $(\alpha_0 = 1, \alpha_1 = 1, \alpha_2 = 1)$ and $(\alpha_0 = 3, \alpha_1 = 2, \alpha_2 = 4)$
\item Now run batch gradient descent (a batch size of all $n$ points). 
\item For the incremental gradient descent method, write down a function $f_i(\alpha_0,\alpha_1,\alpha_2) = \, ?$ that evaluates the loss function for the $i$th data point. After filling in ?, report the value of the loss function for $i=1$ at $(\alpha_0 = 1, \alpha_1 = 1, \alpha_2 = 1)$ and also at $(\alpha_0 = 3, \alpha_1 = 2, \alpha_2 = 4)$.
\item For the function you wrote in part (d), write down the gradient function, i.e $\nabla f_i (\alpha_0,\alpha_1,\alpha_2) = \, ?$ that evaluates the gradient of the loss function for the $i$th data point. After filling in ?, report the value of $\nabla f_i$ for $i=1$ at $(\alpha_0 = 1, \alpha_1 = 1, \alpha_2 = 1)$ and $(\alpha_0 = 3, \alpha_1 = 2, \alpha_2 = 4)$
\item Now run incremental gradient descent.  
\end{enumerate}




Choose one method which you preferred (either is ok to choose), and explain why you preferred it to the other method.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item\textbf{[20 points]}

Consider a matrix $A \in \mathbb{R}^{200 \times 10}$ and its SVD  $[U,S,V^T] = \mathsf{svd}(A)$.    Answer the following questions.  
\begin{enumerate}
\item True or False, the \emph{first} right singular vector $v_1$ of $A$ is the direction in $\mathbb{R}^{10}$ satisfying $v_1 = \argmax_{x \in \mathbb{R}^{10},\| x \| = 1} \| A x \|_2$
\item True or False, a left singular vector of $A$ is a direction in $\mathbb{R}^{10}$
\item True or False, Suppose $s_3$ is the third singular value of $A$. Then $s_3^2$ is the third largest eigenvalue of $A A^T$ and $A^T A$.
\end{enumerate}
Let $u_1, u_2$ be the first two left singular vectors; let $v_1, v_2$ be the first two right singular vectors; and let $s_1, s_2$ be the first two singular values.  
Consider $B = s_1 u_1 v_1^T + s_2 u_2 v_2^T$.  
\begin{enumerate}\setcounter{enumii}{3}
\item What is the rank of $B$?
\item What is dimension of $B$?
\item Let $v_3$ be the third right singular vector.  What is $\|B v_3\|$?
\end{enumerate}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item\textbf{[30 points]}
Read data set \texttt{A.csv} as a matrix $A \in  \b{R}^{35 \times 8}$.  
Compute the SVD of $A$ and report 
\begin{enumerate}
\item the fourth singular value, and 
\item the rank of $A$?  
\end{enumerate}

Compute the eigendecomposition of $A A^T$.  
\begin{enumerate} \setcounter{enumii}{2}
\item For every non-zero eigenvalue, report it and its associated eigenvector. How many non-zero eigenvalues are there?
\end{enumerate}

Compute $A_k$ for $k = 3$.  
\begin{enumerate} \setcounter{enumii}{3}
\item What is $\|A - A_k\|_F^2$?  
\item What is $\|A - A_k\|_2^2$?  
\end{enumerate}

Center $A$.  Run PCA to find the best $3$-dimensional subspace $F$ to minimize 
$\|A - \pi_F(A)\|_F^2$.  Report 
\begin{enumerate} \setcounter{enumii}{5}
\item $\|A - \pi_F(A)\|_F^2$ and 
\item $\|A - \pi_F(A)\|_2^2$.  
\end{enumerate}



\end{enumerate}

\end{document}
