\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 6, 2019\\
\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}$ are 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$, \emph{i.e.} the number of required basic arithmetic operations for a given $n$). Give the complexity and explain your reasoning (you need not prove ``lower bounds''), implement your procedure, demonstrate that your code scales correctly by timing your code as $n$ is increased and providing corroborating evidence (a sufficiently clear plot will suffice). You may reorder and modify the expressions in any way you choose, so long as the result remains mathematically equivalent to the given statement.
\begin{enumerate}
\item $\Tr(D+uv^T)$
\item $uv^TA$
\item $v^T(I+uu^T)v$
\item $v^TABu$
\end{enumerate}
\textbf{Remarks:} Up to constants, we expect these arithmetic complexities, and hence the time taken for sufficiently large $n,$ to behave like $n^q$ for some non-negative $q.$ When you are construing your plots think carefully about how you can generate a plot where the slope of the corresponding line can be used to determine/estimate $q.$ Here is a quick hint, simply plotting $t(n),$ the time taken, vs $n$ does not have this property and is not an easy way to distinguish between various complexities. Lastly, for a given $n$ run your timing experiment multiple times\textemdash how consistent are the measurements? What are the potential implications of this and are there ways to mitigate them?
\subsection*{Question 2:}
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.$
\item For any orthogonal matrix $Q\in \R^{n\times n}:$ $\|QA\|_2 = \|A\|_2.$
\end{enumerate}
\subsection*{Question 3:}
For this problem, let $V\in \R^{m \times n}$ with $m > n$ be a matrix with linearly independent columns, prove that
\begin{enumerate}
\item $V^TV$ is positive definite
\item $VV^T$ is positive semi-definite but not positive definite
\end{enumerate}
\subsection*{Question 4:}
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 5:}
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 your language of choice (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 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}