\documentclass[12pt,letterpaper,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\usepackage{amsmath,amssymb}
\usepackage{algorithm2e}
\usepackage{enumerate}

% info for header block in upper right hand corner
\name{\_\_\_\_\_}
\class{Math 173}
\assignment{Problem Set 7}
\duedate{Monday, November 19, 2018}
\setlength\parindent{0pt}

\begin{document}

\begin{problem}[1]
    Read the introduction to Woodruff's monograph on \emph{Sketching as a Tool
    for Numerical Linear Algebra}. Summarize the introduction in about half a page,
    and argue \emph{why} sketching is useful for solving least squares problems.
\end{problem}

\begin{solution}
    \vfill
\end{solution}

\begin{problem}[2]
    Woodruff's introduction proposes an argument of why $\ell^2$ sketching works.
    In particular, this relies on the fact that if $S\in\mathbb{R}^{r\times (d+1)}$
    is a matrix with entries independently distributed as $\mathcal{N}(0,1/r)$ then
    $\|Sx\|_2^2 = (1\pm\epsilon)\|x\|_2^2$ for any fixed vector $x$ with probability
    at least $1 - e^{-d}$ (up to a constant). Prove this from first principles.
\end{problem}

\begin{solution}
    \vfill
\end{solution}
\clearpage


\end{document}
