\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{url}
\usepackage{fancyvrb}
\usepackage{color,hyperref}
\usepackage{enumerate}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}

\usepackage{preamble}

\begin{document}

\section*{Math 5490 -- Homework 2: Due Feb 8 by 11:59pm}
\thispagestyle{empty}

\subsection*{Instructions:}

\begin{itemize}
\item  Complete the problems below, and submit your solutions and Python code by uploading them to the Google form: \url{https://forms.gle/zSteKSYk1KztzUT1A}
\item Submit all your Python code in a single .py file using the function templates given in each problem. I will import your functions from this file and test your code.
\item If you use LaTeX to write up your solutions, upload them as a pdf file. Students who use LaTeX to write up their solutions will receive bonus points on the homework assignment (equivalent to 1/3 of a letter grade bump).
\item If you choose to handwrite your solutions and scan them, please either use a real scanner, or use a smartphone app that allows scanning with you smartphone camera. It is not acceptable to submit photos of your solutions, as these can be hard to read.
\end{itemize}


\subsection*{Problems:}

For some problems, we need the following definition.
\begin{definition}\label{def:hadamard}
The \emph{Hadamard product} between two vectors $\x,\y\in \R^n$, denoted as $\x\circ \y$, is the vector $\z\in \R^n$ with entries $z_i = x_iy_i$. Similarly, the \emph{Hadamard product} of two matrices $A,B\in \R^{n\times m}$, denoted again as $A\circ B$, is the matric $C\in \R^{n\times m}$ with entries $C_{ij}=A_{ij}B_{ij}$. 
\end{definition}
The Hadamard product of two matrices or two vectors is simply the elementwise product. The reader should be careful to note that the Hadamard product is not the same as the matrix product. The Hadamard product applies only to vectors or matrices of the same size, and produces a vector or matrix of the same size. The Hadamard product is also clearly commutative, that is, $A \circ B = B\circ A$ and $\x \circ \y = \y \circ \x$, and satisfies the usual properties of multiplication (e.g., associativity). 


\begin{enumerate}
\item Let $\x,\y\in \R^n$. Show that
\begin{equation}\label{eq:rankoneschur}
(\x\x^T) \circ (\y\y^T) = (\x \circ \y) (\x \circ \y)^T.
\end{equation}
[Hint: Compare the components of the matrices on each side.]
\item Let $A$, $B$ be symmetric and positive semidefinite matrices. Prove that $A\circ B$ is also symmetric and positive semidefinite. This is known as the \emph{Schur Product Theorem}. 
[Hint: Since $A$ and $B$ are symmetric, they can be diagonalized and written in the form
\[A = \sum_{i=1}^n \lambda_i \u_i\u_i^T \ \ \text{and} \ \ B = \sum_{i=1}^n \mu_i \v_i\v_i^T,\]
where $\u_1,\dots,\u_n$ and $\lambda_1,\dots,\lambda_n$ are the orthonormal eigenvectors and eigenvalues of $A$, while $\v_1,\dots,\v_n$ and $\mu_1,\dots,\mu_n$ are those of $B$. Continue from here, writing out $A\circ B$ using the expressions for $A$ and $B$ above, and then use part 1.] 
\item Let $A$ be positive definite and symmetric and let $\x$ be the solution of the linear system
\[A\x=\b.\]
Let $0< \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ be the eigenvalues of $A$ and $\v_1,\dots,\v_n$ the corresponding orthonormal eigenvectors. 
\begin{enumerate}[(i)]
\item Show that $\x$ can be written as 
\[\x = \sum_{i=1}^n \lambda_i^{-1}(\b\cdot \v_i)\v_i.\]
[Hint: Show by direct computation that $A\x=\b$.]
\item Define the spectrally truncated approximate solution 
\begin{equation}\label{eq:spect}
\x_N = \sum_{i=1}^N \lambda_i^{-1}(\b\cdot \v_i)\v_i.
\end{equation}
Show that
\[\|\x_N - \x\| \leq  \lambda_{N+1}^{-1}\|\b\|.\]
[Comment: In practice, it is often tractable to compute a few of the eigenvectors of $A$, say the first $N$, where $N \ll n$, even if computing all eigenvectors is intractable. In this case, the spectrally truncated approximate solution \eqref{eq:spect} can be an efficient way to solve $A\x=\b$, provided $N$ is chosen so that $\lambda_{N+1}$ is large. ]
\end{enumerate}
\item Assume we are in dimension $n=1$. Show that the radial basis function kernel $\K(x,y) = e^{-\gamma(x-y)^2}$ can be expressed as 
\[\K(x,y) = \sum_{m=0}^\infty \phi_m(x)\cdot \phi_m(y)\]
where the functions (i.e., feature maps) $\phi_m:\R\to \R$ are given by 
\[\phi_m(x) = e^{-\gamma x^2}x^m\sqrt{\frac{(2\gamma)^m}{m!}}.\]
[Hint: Write
\[\K(x,y) = e^{-\gamma x^2}e^{-\gamma y^2}e^{2\gamma xy},\]
and use a Taylor expansion on the last exponential term.]
\end{enumerate}

\end{document}

