%\documentclass{beamer}

\documentclass[handout]{beamer}  %%% produces a handout - ready to print, no frames

\setbeamertemplate{navigation symbols}{ \insertslidenavigationsymbol}     %keeps or removes navigation symbols
\setbeamercolor{navigation symbols dimmed}{fg=blue!75!black}  %changes how the bottom 
\setbeamercolor{navigation symbols}{fg=white!80!white}                  %navigation symbols look 





\mode<presentation>
{\usetheme{boxes}} 
\setbeamertemplate{items}[square] 
\hypersetup{colorlinks=true,linkcolor=gray} 




\usepackage{amsbsy,amsfonts}
\usepackage{amstext}

\usepackage{latexsym,eucal,amsmath,amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{hyperref}
\newcommand{\blob}{\rule[.2ex]{.9ex}{.9ex} \ }
\newcommand{\dd}{\rule[.2ex]{.6ex}{.6ex}}

\newcommand{\R}{\mathbb{R}}

\newcommand{\norm}[1]{\lVert#1\rVert} % norm

\newcommand{\avg}[1]{\left< #1 \right>} % average

\newcommand{\sabs}[1]{\left| #1 \right|} % smaller absolute value
\newcommand{\abs}[1]{\bigl| #1 \bigr|} % absolute value


%\newcommand{\sabs}[1]{\left| #1 \right|}


\title{
General Vector Spaces}
\author{Silvius Klein}
\date{}
\vspace{2in}

\institute{MA1202 Linear Algebra with Applications}



\AtBeginSection[]  % "Beamer, do the following at the start of every section"
{
\begin{frame}<beamer> 
\frametitle{Outline} % make a frame titled "Outline"
\tableofcontents[currentsection]  % show TOC and highlight current section
\end{frame}
}



\begin{document}


% this prints title, author etc. info from above
%\begin{frame}
%\titlepage
%\end{frame}


\begin{frame}
\frametitle{Inner products}

\underline{Definition}: An {\em inner product} on a real vector space $V$ is an operation (function) that assigns to each pair of vectors $(\vec{u}, \vec{v})$ in $V$ a \alert{scalar} $\avg{ \vec{u}, \vec{v} }$ satisfying the following axioms:

\begin{itemize}

\item[1.]  $\avg{ \vec{u}, \vec{v} } =  \avg{ \vec{v}, \vec{u} } $   \ (Symmetry)

\item[2.]   $\avg{ \vec{u} + \vec{v}, \vec{w} }   =  \avg{ \vec{u}, \vec{w} } +  \avg{ \vec{v}, \vec{w} }$  \ (Additivity)

\item[3.]  $\avg{ k \, \vec{u}, \vec{v} }  = k  \, \avg{ \vec{u}, \vec{v} }$ \ (Homogeneity)

\item[4.]  $\avg{ \vec{v}, \vec{v} } \, \ge 0$  \ and  $\avg{ \vec{v}, \vec{v} } = 0$ iff $\vec{v} = \vec{0}$ \ (Positivity)


\end{itemize}

\medskip

\pause

\underline{Theorem} (basic properties): Given vectors $\vec{u}, \vec{v}, \vec{w}$ in an inner product space $V$, and a scalar $k$, the following properties hold:

\begin{itemize}

\item $\avg{ \vec{\rm{o}}, \vec{v} } = \avg{ \vec{v}, \vec{\rm{o}} }  = 0$

\item $\avg{ \vec{u} - \vec{v}, \vec{w} }   =  \avg{ \vec{u}, \vec{w} } -  \avg{ \vec{v}, \vec{w} }$

\item $\avg{ \vec{u}, \vec{v} + \vec{w} }   =  \avg{ \vec{u}, \vec{v} } +  \avg{ \vec{u}, \vec{w} }$

\item $\avg{ \vec{u}, \vec{v} - \vec{w} }   =  \avg{ \vec{u}, \vec{v} }  -  \avg{ \vec{u}, \vec{w} }$

\item  $\avg{ \vec{u}, k \vec{ v} }  = k  \, \avg{ \vec{u}, \vec{v} }$

\end{itemize}

\end{frame}


\begin{frame}
\frametitle{Norm and distance in an inner product space}

\underline{Definition}: If $V$ is a real inner product space then we define

\begin{itemize}

\item The norm (or length) of $\vec{v}$:
$$\norm{\vec{v}} = \sqrt{ \avg{ \vec{v}, \vec{v} } } $$

\item The distance between $\vec{u}$ and $\vec{v}$:
$$ d (\vec{u}, \vec{v}) = \norm{ \vec{u} - \vec{v}} =  \sqrt{ \avg{ \vec{u} - \vec{v}, \vec{u} - \vec{v} } } $$

\end{itemize}

\medskip

\underline{Theorem} (basic properties): Given vectors $\vec{u}, \vec{v}$ in an inner product space $V$, and a scalar $k$, the following properties hold:

\begin{itemize}

\item $\norm{\vec{v}} \ge 0$ \ and \ $\norm{\vec{v}} = 0$ iff $\vec{v} = \vec{0}$.

\item $\norm{ k \vec{v}} = |k| \, \norm{\vec{v}}$

\item $d (\vec{u}, \vec{v}) = d (\vec{v}, \vec{u}) $

\item $d (\vec{u}, \vec{v} ) \ge 0$ \ and \ $d (\vec{u}, \vec{v}) = 0$ iff $\vec{u} = \vec{v}$.


\end{itemize}

\end{frame}


\begin{frame}
\frametitle{Angle between vectors}

\underline{Theorem} (Cauchy-Schwarz): If $u$ and $v$ are vectors in an inner vector space, then
$$\abs{ \avg{u, v} } \le \norm{u} \, \norm{v} $$

\medskip
\pause

\underline{Definition}: The angle between two vectors  $u$ and $v$ in an inner vector space is defined as
$$\theta = \cos^{-1} \, \frac{\avg{u,v}}{\norm{u} \, \norm{v}}  $$


\medskip
\pause

\underline{Theorem} (the triangle inequality):  If $u, v$ and $w$ are vectors in an inner vector space, then
\begin{itemize}
\item $\norm{u + v} \le \norm{u} + \norm{v}$

\item $d (u, v) \le d (u, w) + d (w, v)$
\end{itemize}

\end{frame}



\begin{frame}
\frametitle{Orthogonality}

\underline{Definition}:  Two vectors  $u$ and $v$ in an inner vector space are called {\em orthogonal} if $\avg{u, v} = 0$.

\smallskip
\pause

Clearly $u \perp v$ iff the angle between them is $\theta = \frac{\pi}{2}$.

\pause
\medskip

\underline{Theorem} (the Pythagorean theorem):  If $u$ and $v$ are \alert{orthogonal} vectors in an inner vector space, then
$$\norm{u + v}^2 = \norm{u}^2 + \norm{v}^2$$

\medskip

\underline{Definition}:  Let $W$ be a subspace of an inner product space $V$. 

The set of vectors in $V$ which are orthogonal to \alert{every} vector in $W$ is called the {\em orthogonal complement} of $W$ and it is denoted by $W^\perp$.

\pause
\medskip

\underline{Theorem}: The orthogonal complement has the following properties:
\begin{itemize}
\item $W^\perp$ is a subspace of $V$.

\item $W \cap W^\perp = \{ \vec{\rm{o}} \}$.

\item If $V$ has finite dimension then $(W^\perp)^\perp = W$.

\end{itemize}

\end{frame}


\begin{frame}
\frametitle{Orthogonal sets, orthonormal sets}

Let $(V, \avg{ \ })$ be an inner product space and let $S$ be a set of vectors in $V$.

\medskip

\underline{Definition}: The set $S$  is called {\em orthogonal} if any two vectors in $S$  are orthogonal.

The set $S$ is called {\em orthonormal} if it is orthogonal and any vector in $S$ has norm $1$.

\medskip
\pause

\underline{Theorem}: Every orthogonal set of nonzero vectors is linearly independent.

\medskip
\pause

\underline{Definition}: A set of vectors $S$  is called an {\em orthogonal} basis (OGB) for $V$ if $S$ is a basis and an orthogonal set (that is, $S$ is a basis where all vectors are perpendicular).

A set of vectors $S$  is called an {\em orthonormal} basis (ONB) for $V$ if $S$ is a basis and an orthonormal set (that is, $S$ is a basis where all vectors are perpendicular and have norm $1$).

\end{frame}

\begin{frame}
\frametitle{Orthogonal sets, orthonormal sets}

Let $(V, \avg{ \ })$ be an inner product space.

\medskip

\underline{Theorem}:  If $S = \{ v_1, v_2, \ldots, v_n \}$ is an orthogonal basis in $V$ and $u$ is any vector in $V$, then
$$u = \frac{\avg{u, v_1}}{\norm{v_1}^2} \, v_1 + \frac{\avg{u, v_2}}{\norm{v_2}^2} \, v_2 + \ldots + \frac{\avg{u, v_n}}{\norm{v_n}^2} \, v_n$$

If $S = \{ v_1, v_2, \ldots, v_n \}$ is an orthonormal basis in $V$ and $u$ is any vector in $V$, then
$$u = \avg{u, v_1} \, v_1 + \avg{u, v_2} \, v_2  + \ldots + \avg{u, v_n} \, v_n$$ 

\end{frame}


\begin{frame}
\frametitle{Projection onto a subspace}

Let $(V, \avg{ \ })$ be an inner product space.

 Let $W$ be a finite dimensional subspace.

\medskip

\underline{Theorem}:  If $S = \{ v_1, v_2, \ldots, v_r \}$ is an orthogonal basis in $W$ and $u$ is any vector in $V$, then
$${\rm proj}_W \, u  = \frac{\avg{u, v_1}}{\norm{v_1}^2} \, v_1 + \frac{\avg{u, v_2}}{\norm{v_2}^2} \, v_2 + \ldots + \frac{\avg{u, v_r}}{\norm{v_r}^2} \, v_r$$

If $S = \{ v_1, v_2, \ldots, v_r \}$ is an orthonormal basis in $W$ and $u$ is any vector in $V$, then
$${\rm proj}_W \, u= \avg{u, v_1} \, v_1 + \avg{u, v_2} \, v_2  + \ldots + \avg{u, v_r} \, v_r$$ 

\end{frame}


\begin{frame}
\frametitle{Gram-Schmidt process}

\underline{Theorem}: Every nonzero finite dimensional inner product space has an orthonormal basis.

\bigskip

Given a basis $\{ u_1, u_2, \ldots, u_n \}$, to find an orthogonal basis $ \{ v_1, v_2, \ldots, v_n \}$ we use the following procedure:

\begin{itemize}


\item[Step 1.] $v_1 = u_1$

\item[Step 2.] $v_2 = u_2  - \frac{\avg{u_2, v_1}}{\norm{v_1}^2} \, v_1 $

\item[Step 3.] $v_3 = u_3  - \frac{\avg{u_3, v_1}}{\norm{v_1}^2} \, v_1 -  \frac{\avg{u_3, v_2}}{\norm{v_2}^2} \, v_2 $

\item[Step 4.] $v_4 = u_4  - \frac{\avg{u_4, v_1}}{\norm{v_1}^2} \, v_1 -  \frac{\avg{u_4, v_2}}{\norm{v_2}^2} \, v_2 - \frac{\avg{u_4, v_3}}{\norm{v_3}^2} \, v_3$

\end{itemize}

and so on for $n$ steps, where $n = \dim (V)$.

\medskip

To obtain an orthonormal basis, we simply normalize the orthogonal basis obtained above.


\end{frame}


\begin{frame}
\frametitle{Formulation of the least squares problem}

Given an {\em inconsistent} system $A \, x = b$, find a vector $x$ that comes ''as close as possible" to being a solution.

\medskip

In other words: find a vector $x$ that {\em minimizes} the distance beyween $b$ and $A \, x$ that is, a vector that minimizes $\norm{ b - A x}$ (with respect to the Euclidian inner product).

\medskip

We call such a vector $x$ a {\em least squares solution} to the system $A \, x = b$.

\medskip

We call $b - A x$ the corresponding {\em least squares vector} and $\norm{b - A x}$ the corresponding {\em least squares error}.

\medskip

\underline{Theorem}: If $x$ is a least squares solution to the inconsistent system $A \, x = b$,  and if $W$ is the column space of $A$, then $x$ is a solution to the consistent system
$$ A \, x = {\rm proj}_{W} b$$

\medskip

\underline{Note:} The above theorem is not always practical, because finding the orthogonal projection ${\rm proj}_{W} b$ may take time (by using Gram-Schmidt).



\end{frame}


\begin{frame}
\frametitle{Solution of the least squares problem}

\underline{Theorem:} For every inconsistent system $A \, x = b$, the associated normal system
$$A^T A \, x = A^T  b$$
is consistent and its solutions are {\em least squares solutions} of  $A \, x = b$.

\smallskip

Moreover, if $W$ is the column space of $A$ and if $x$ is such a least squares solution to  $A \, x = b$, then
$${\rm proj}_{W} b = A \, x$$

\medskip

\underline{Theorem:}  For an inconsistent system $A \, x = b$ the following statements are equivalent:

\begin{itemize}

\item[a)] There is a {\em unique} least squares solution.

\item[b)] The columns of $A$ are linearly independent.

\item[c)] The matrix $A^T A$ is invertible. 

\end{itemize}

\medskip

\underline{Theorem:} If an inconsistent system $A \, x = b$ has a unique least squares solution, then it can be computed as
$$x^* = (A^T A)^{-1} A^T b$$ 

\end{frame}

\begin{frame}
\frametitle{Function approximation}

\underline{Problem}: Given a function $f$ on the interval $[a, b]$, a subspace $W$ of $C [a, b]$, find the {\em best approximation} of $f$ by a function $g$ in $W$.

\pause
\medskip

Best approximation is meant as minimizing the {\em mean square error}, where
$$\text{ mean square error } = \int_a^b [ f (x) - g (x) ]^2 \, d x$$

\pause

If we consider the (standard) inner product on $C [a, b]$, defined by
$$\avg{f_1, f_2} = \int_a^b f_1 (x) \cdot f_2 (x) \, d x$$
and the corresponding norm,
then it is easy to see that 
$$\text{ mean square error } = \avg{f-g, f-g} = \norm{f-g}^2$$

Therefore, the approximation problem can be reformulated as: find a function in $W$ that minimizes $\norm{f-g}^2$.

\pause
\medskip

\underline{Solution:} The best approximation of $f$ by a function in $W$ is 
$$g = {\rm proj}_W \, f$$

\end{frame}

\begin{frame}
\frametitle{Fourier series}

We want to approximate functions by {\em trigonometric polynomials} of a certain order. 
In this case, the subspace $W$ is $\textbf{T}_n$, the set of all trigonometric polynomials of order $\le n$. By definition,
$$\textbf{T}_n = \text{ span } \{ 1, \cos x, \cos 2 x, \ldots, \cos n x, \sin x, \sin 2 x, \ldots, \sin n x \}$$ 

\pause

The trigonometric functions above that span $\textbf{T}_n$ are {\em orthogonal}, so the set
$\{ 1, \cos x, \cos 2 x, \ldots, \cos n x, \sin x, \sin 2 x, \ldots, \sin n x \}$
forms an orthogonal basis in $\textbf{T}_n$.

\medskip
\pause

Therefore, to compute ${\rm proj}_W \, f$, we can use the formula on the slide ``Projection onto a subspace" and we get:
\begin{align*}
f (x) \approx {\rm proj}_{\textbf{T}_n} \, f = \frac{a_0}{2} & + [a_1 \cos x + a_2 \cos 2 x + \ldots + a_n \cos n x] \\
& + [b_1 \sin x + b_2 \sin 2 x + \ldots + b_n \sin n x]
\end{align*}
\pause
where  for $k = 0, 1, \dots, n$, the numbers $a_k$ and $b_k$ are called the {\em Fourier coefficients} of $f$ and they are computed as
$$a_k = \frac{1}{\pi} \, \int_0^{2 \pi} f (x) \cos k x \, dx \qquad b_k = \frac{1}{\pi} \, \int_0^{2 \pi} f (x) \sin k x \, dx$$

\end{frame}

\end{document}