\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\DeclareMathOperator{\Tr}{Tr}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 4220 / MATH 4260: Homework 1}\\
Instructor: Anil Damle\\
Due: February 7, 2018\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please refrain from looking at their code or writeups (or sharing your own). Ultimately, you must implement your own code and write up your own solution to be turned in. Your solution, including plots and requested output from your code should be typeset and submitted via the CMS as a pdf file. Additionally, please submit any code written for the assignment via the CMS as well.\\
\hrule
\subsection*{Question 1:}
Suppose $A,B\in \R^{n\times n},$ be general square matrices, $D\in\R^{n\times n}$ is a diagonal matrix, and $u,v\in\R^n$ are vectors of length $n.$ For the following mathematical expressions: determine an optimal way to compute them (in terms of complexity in $n$), give the complexity and explain your reasoning, implement your procedure, demonstrate that your code scales correctly by timing your code as $n$ is increased and providing a plot (think carefully about how to scale the axes). You may reorder, modify the expressions in any way you choose, so long as the result remains mathematically equivalent to the given statement.
\begin{enumerate}
\item $\Tr(A+uv^T)$
\item $Auv^T$
\item $v^T(I+uu^T)v$
\item $v^TABu$
\end{enumerate}
\subsection*{Question 2:}
Say that we would like to compute $e^{-x}$ for $x>0$ given only the four basic arithmetic operations. A natural method to consider would be via the Taylor series of the exponential truncated to some number of terms and evaluated at $-x$. Try this, does it seem to work? Why might this not be such a good idea? In particular, for $x=20$ are you able to accurately compute $e^{-20}$? You may compare with the built in function for computing the exponential in MATLAB or Julia (they use schemes to compute the exponential that are outside the scope of this course, and for the purpose of this assignment you can consider them as the ground truth).
Given the leading questions in the preceding part of the question, you may have surmised that na\"{i}ve application of the Taylor series is problematic. However, there is still a way to use Taylor series to compute the desired quantity, albeit requiring extra arithmetic operations. How might you accomplish this? Implement and test your method for $x=20$ and show you can compute $e^{-20}$ to at least $10^{-8}$ relative error.
\subsection*{Question 3:}
For this problem, let $A\in \R^{n \times n}$ be a square matrix and $x\in\R^n$ be a vector of length $n.$ Prove the following:
\begin{enumerate}
\item $\|x\|_{\infty} \leq \|x\|_2 \leq \sqrt{n}\|x\|_{\infty}$
\item $\|A\|_2 \leq \sqrt{n}\|A\|_{\infty}$
\item For any orthogonal matrix $Q\in \R^{n\times n}:$ $\|Qx\|_2 = \|x\|_2.$
\item $\|A\|_2 = \sigma_{\max},$ where $\sigma_{\max}$ is the largest singular value of $A.$
\end{enumerate}
\subsection*{Question 4:}
For this problem, let $V\in \R^{m \times n}$ with $m > n$ be a matrix with linearly independent columns, prove that
\begin{itemize}
\item $V^TV$ is positive definite
\item $VV^T$ is positive semi-definite but not positive definite
\end{itemize}
\subsection*{Question 5:}
For differentiable functions $f(x),$ where the input $x$ may be a vector $x = (x_1, x_2,\ldots,x_n),$ we define the relative condition number $\kappa_{2}(x)$ of computing $f(x)$ at $x$ as
\[
\kappa_{2}(x) \equiv \frac{\|J(x)\|_{2}}{\|f(x)\|_{2}/\|x\|_{2}},
\]
where $J$ is the Jacobian of $f.$
\begin{enumerate}
\item Compute $\kappa_{2}(x)$ for subtraction, \emph{i.e.} $f(x) = x_1 - x_2.$ When, if ever, is this an ill-conditioned problem?
\item Compute $\kappa_{2}(x)$ for multiplication, \emph{i.e.} $f(x) = x_1x_2.$ When, if ever, is this an ill-conditioned problem?
\end{enumerate}
\subsection*{Question 6:}
Let $x,y \in \R^{n}$ be two vectors of length $n.$ Bound the floating point error of computing $x^Ty$ in terms of $\epsilon$ (machine precision) and $n.$
\end{document}