\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd}
\usepackage{graphicx, epsfig}
\usepackage{multicol}
\usepackage{boxedminipage}
\usepackage{subfigure}
\usepackage{euler,palatino,array}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
\usepackage{wrapfig}
\usepackage{bbold}


\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in} 
\setlength{\parindent}{0in}
\newcounter{prob}
\setcounter{prob}{0}
\newcommand{\problem}{\stepcounter{prob}\medskip{\bf Presentation problem \theprob.}\ }
\newcommand{\answer}{\medskip{\bf Answer to Question \theprob.}\ }
\newcommand{\solution}{\medskip{\bf Solution to Question \theprob.}\ }



% ***** Some useful abreviations *****
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\B}{\mathscr{B}}
\newcommand{\LL}{\mathscr{L}}
\newcommand{\PP}{\mathscr{P}}
\newcommand{\ra}{\rightarrow}
\newcommand{\ds}{\displaystyle}
\newcommand{\bnum}{\begin{enumerate}} %Use with \item to create numbered lists
\newcommand{\enum}{\end{enumerate}}
\newcommand{\babc}{\bnum\renewcommand{\labelenumi}{(\alph{enumi})}}%Use with \item for abc lists
\newcommand{\eabc}{\end{enumerate}}
\newcommand{\bijk}{\bnum\renewcommand{\labelenmi}{\roman{enumi}.}}%Roman numeral lists
\newcommand{\eijk}{\end{enumerate}}

\renewcommand{\ss}{\smallskip}
\newcommand{\ms}{\medskip}
\newcommand{\bs}{\bigskip}




\pagestyle{myheadings} \markright{Math 4310 (Fall 2020) \hspace{2in}
(HW10)}

\begin{document}


%% PREAMBLE

\thispagestyle{empty}

\begin{minipage}[t]{1.1in}
{\vspace{-0.2in}
  \includegraphics[width=1.1in]{cornell-logo.jpg}}
\end{minipage}
\hfill
\begin{minipage}[t]{3in}
%\vspace{.05in}
  {\large Homework \# 10

    \medskip
    Math 4310 Fall 2020

    \medskip
    
    Due Friday evening, 12/4/20 (at midnight).
  }

\end{minipage}
\hfill
\begin{minipage}[t]{3.4in}
\end{minipage}

\vskip 0.25in

%\vspace*{-66mm}


Please submit your completed homework via gradescope on canvas.
I encourage you to work with your classmates on this homework (except for the journal entries!)
When you submit your work, please {\bf list your collaborators}.
(Your grade will not be affected.)
Even if you work in a group, you should write up 
your solutions {\bf yourself}! 
You should include all computational details, and proofs should be carefully 
written with full details.
As always, please write {\bf neatly and legibly} (feel free to use \LaTeX\ to write up your solutions, if you wish!).

\vskip 4mm

%% END PREAMBLE

\noindent {\bf Journal entry.} There is no journal entry this week.

\vskip 0.1in

\noindent {\bf Exercises.} 

\vskip 0.1in

\begin{enumerate}


%% \item {\bf Givens (rotation) matrices}
%%   Recall that in the plane $\R^2$, rotation by the angle $\theta$ (counterclockwise),
%%   is a linear transformation with matrix
%%   \[ R_\theta \, = \, \begin{pmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}. \]
%%   \babc
%% \item Given $1 \le i < j \le n$, and $\theta$ an angle.  A {\bf Givens rotation} $G(i,j,\theta)$ on $\R^n$
%%   is the linear transformation which fixes $e_\ell$ for $\ell \ne i, j$, and in the $(x_i, x_j)$-plane,
%%   is given by rotation by angle $\theta$ (i.e. in $x_i, x_j$ part, the matrix is $R_\theta$).
%%   Write down the matrices of all three Givens rotations in $\R^3$.
%% \item Show that $G(i,j,\theta)$ is orthogonal. What is its inverse?
%% \item More generally, let $V = \R^n$ be equipped with the standard inner product, and suppose that
%%   $({\bf u}_1, \ldots, {\bf u}_n)$
%%   is an orthonormal basis, define what you think the Givens rotation $G(i,j,\theta) : V \to V$ should be.
%%   Is this orthogonal?  What is its inverse?
%%   \eabc
  
\item

  Let $V$ be the vector space (over $\C$) of all continuous functions
  $f(x) = g(x) + i h(x)$ from the interval $[0, 2\pi]$ to the complex
  numbers.  One example of a function in $V$ is $e^{ix} = \cos x + i
  \sin x$.  In this problem you may use the fact that the product and
  sum of two continuous functions is continuous. You may also use the fact that
  a continous function which is always nonnegative, but takes on a positive value somewhere,
  has non-zero integral.

  Integration works for these functions pretty much like over the real numbers, for example, if
  $m \ne 0$ is an integer, then
  \[ \int^{2\pi}_0 e^{imx} \ dx = \frac{1}{im} e^{imx} |^{2\pi}_0 = -\frac{i}{m} (1 - 1) = 0. \]

  \babc
\item
  Let ${\mathcal A}_r = \{ e^{imx} \mid -r \le m \le r, \text{$m$ an integer} \}$.
  For a positive integer $r$, let $V_r$ be the subspace of $V$ spanned by ${\mathcal{A}}_r$.
  Show that $V_r$ is also the span (over $\C$) of $\mathcal{B}_r$:
  \[
  {\mathcal{B}}_r := \{ \cos(mx) \mid 0 \le m \le r\} \cup \{ \sin(mx) \mid 1 \le m \le r\}.
  \]
  
\item
  Define $\langle f, g \rangle = \int^{2\pi}_0 f(x) \overline{g(x)} \, dx$.
  Prove that this is an inner product on $V$.
\item
  Find an orthonormal basis for $V_r$.
\item
  Given a continuous function $f(x) \in V$, let $a_m := \int^{2\pi}_0 f(x) e^{imx} \, dx$.
  In terms of these numbers, find the closest function (in the norm corresponding to the
  above inner product) in $V_r$ to $f(x)$.
\item
  Given a continuous function over $\R$, $f(x)$, let $c_m := \int^{2\pi}_0 f(x) \cos{mx} \, dx$,
  and let $s_m := \int^{2\pi}_0 f(x) \sin{mx} \, dx$. 
  How are the $a_m$ and $c_m, s_m$ related?
  Write the closest function in terms of this new basis.
  \eabc
  
\item

  In this problem, we consider the $QR$ factorization of a matrix $A$
  (with entries in $\R$), with linearly independent columns.
  Suppose that $A = \begin{bmatrix}{\bf a}_1 \ldots {\bf a}_n\end{bmatrix}$
  is an $m \times n$ matrix over $\R$ with linearly independent columns, and that $Q = \begin{bmatrix}{\bf u}_1 \ldots {\bf u}_n\end{bmatrix}$
    is obtained from $A$ by using the Gram-Schmidt process.

    \babc
  \item Show that there is a $n \times n$ invertible matrix $S$ such that $AS = Q$.
  \item Show that there is exactly one $n \times n$ matrix $R$, such that $A = QR$.
  \item Show that $R$ is upper triangular and invertible.  What are the entries of R?
  \item Find $A = QR$, for
    \[ A = \begin{bmatrix}
      1 & 2 & 1 \\
      0 & -1 & 1 \\
      1 & 3 & 1 \\
      1 & 1 & 1
    \end{bmatrix}
    \]
  \item Recall that the least squares solution of $A{\bf x} = {\bf y}$ is the vector ${\bf x}$
    such that $||A{\bf x} - {\bf y}||$ is minimal, and that this is given by the unique exact solution to the normal equation:
    \[ A^T A {\bf x} = A^T {\bf y}. \]
    Assume that $A = QR$ is a QR factorization of $A$.
    Rewrite the normal equations using $Q$ and $R$, simplifying as much as possible.  Explain how to get the
    solution ${\bf x}$ by only solving upper or lower triangular systems, not general systems (once the $Q$ and $R$
    have been found!).
  \eabc

\item {\bf Householder (reflection) matrices}.
  Let $V = \R^n$, equipped with the standard inner product.
  Given a nonzero vector $v$ and unit vector $u = \frac{v}{||v||}$, let
  $H \in \R^{n \times n}$ be the square matrix defined by
  \[ H = I - 2\, \frac{vv^T}{v^Tv} = I - 2\, uu^T. \]
  Notice that the displayed fraction is a matrix divided by a scalar, so $H$ is an $n \times n$ matrix.
  \babc
  \item Show that $H$ is symmetric, and $H$ is an orthogonal $n \times n$ matrix.   What is the inverse of $H$?

  \item Show that $H$ is a reflection: $H(v) = -v$, and if $w \in v^\perp$, then $H(w) = w$.
  \eabc 
  
\item (Rank one update)
  Suppose that $A$ is a square invertible matrix of size $n \times n$ over $\R$.
  Let ${\bf u}$ and ${\bf v}$ be $n \times 1$ column vectors.  Let $B = A + {\bf u}{\bf v}^T$, this is called {\bf a rank one update to the matrix $A$}.
  (This is since ${\bf u}{\bf v}^T$ is a rank one $n \times n$ matrix).

  \babc
  \item
  Find the real number $a$ such that
  \[ (A + {\bf u} {\bf v}^T)^{-1} = A^{-1} - a A^{-1} {\bf u} {\bf v}^T A^{-1}. \]
  (actually, sometimes this $a$ cannot be found, when does this happen? in this case the matrix $B$  might not be invertible).
\item Show that one can solve linear systems of the form $B {\bf y} = {\bf b}$ as follows:
  First solve $A {\bf x} = {\bf b}$ and $A {\bf z} = {\bf u}$.  Compute $D = 1 + {\bf v}^T {\bf z}$ (this is a number).
  Assume that $D \ne 0$.  Use this data to solve $B {\bf y} = {\bf b}$.
  \eabc
  
\item In supervised machine learning, a neural network consists of a bunch of ``neurons''.  The whole thing is
  a function: you give it an input, say a vector of real numbers
  ${\bf t} = (t_1, \ldots, t_n)$, and out pops
  a result $y$.  Each neuron has a number of parameters, and when you ``learn'' the network, you give it
  a lot of input vectors, and the output that is desired .  Using all this data, an algorithm will tweak all
  of the parameters in the neurons to minimize the error: i.e. try to match the data you gave it.

  In this problem, we consider the very special (yet still important) case of a single neuron.
  A single neuron in a neural network is a function which has $n$ real number inputs,
  which we represent as the $1 \times n$ matrix
  \[ {\bf t} = \begin{bmatrix} t_1 & t_2 & \ldots & t_n \end{bmatrix}. \]
  Internally, the neuron (function) has $n$ ``weights'' $x_i$, which we represent as a column vector
  \[ {\bf x} = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}. \] 
  The neuron, when given input ${\bf t}$, outputs
  \[ {\bf t} \, {\bf x} = \sum_{i=1}^{n} x_i t_i, \]
  the dot product of these two vectors.
  (Actually, it usually outputs something slightly more complicated, but we won't consider that here).

  Suppose that we have training data: the input
  ${\bf t}_i = \begin{bmatrix} t_{i1} & \ldots & t_{in} \end{bmatrix}$,
  with output $y_i$, for $i = 1..m$, with $m$ generally much larger
  than $n$. If we let $A$ be the $m \times n$ matrix with rows
  ${\bf t}_1, \ldots, {\bf t}_m$, and we let ${\bf y}$ be the $m \times 1$ column vector
  with entries $y_i$, then the optimal ${\bf x}$ which minimizes the error of the training data is
  solved by the normal equations $A^TA {\bf x} = A^T{\bf y}$.  We assume that the columns of $A$ are
  linearly independent.

  We will now investigate what happens when we have already found the
  weights ${\bf x} = {\bf x}_{old}$ which best fit the training data, but we get new
  training data.  For the purposes of this problem, we will assume we
  have one new data point:
  \[ {\bf r} = {\bf t}_{m+1}, \]
  a $1 \times n$ matrix, and it's output $y_{m+1}$.  Our goal is to update ${\bf x}_{old}$ to get ${\bf x}_{new}$,
  without starting from scratch and redoing the entire computation.

  \babc
\item The new matrix is $A' = \begin{bmatrix} A \\ {\bf r} \end{bmatrix}$, and the normal equations are:
  \[ (A')^T A' {\bf x} = (A')^T \begin{bmatrix} {\bf y} \\ y_{m+1} \end{bmatrix}. \]
  Simplify this equation, obtaining a system of $n$ equations in $n$ unknowns:
  \[ B {\bf x}_{new} = {\bf y'}, \]
  where $B$ is a rank one update of $A^TA$.

\item Let ${\bf z}$ be the solution to $A^TA {\bf z} = {\bf r}^T$.
  Use the previous problem to determine a solution for ${\bf x}_{new}$
  of the form:
  \[ {\bf x}_{new} = {\bf x}_{old} + b\, {\bf z}. \]
  What is the real number $b$?
\item (optional, open-ended): Is this worth it? Does this take less computation than the full solving?
  (recall: multiplication of $n \times n$ matrices takes $n^3$ operations, as does solving a general
  linear system of $n$ equations and $n$ unkowns.  It is possible to do better, by the way.  Solving upper or lower triangular systems
  requires on the order of $n^2$ operations).
  
  \eabc
\end{enumerate}

\end{document}



