\documentclass{amsart}

\usepackage[left=1.5in, right=1.5in, top=1in]{geometry}
\usepackage{setspace}
%\usepackage{eulervm}

%\usepackage[exercise]{amsthm}

\newtheorem{defn}{Definition}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}{Proposition}

\newtheorem{exer}{Exercise}[section]

\theoremstyle{remark}
\newtheorem*{rmk}{Remark}
\newtheorem*{soln}{Solution}

\newtheorem*{prf}{Proof}

\begin{document}
\title{Basic sampling, frames, and wavelets notes}
\begin{abstract}
These notes were taken during the 2004 Texas A\&M 2004 Research Experience for Undergraduates (REU) in Math. I was in the wavelets group, under Dr. Dave Larson, which had a daily~(?) seminar. Wonderful stuff, all accessible to undergraduates with calculus and linear algebra courses under their belts. The best REU ever! At some point, I will add a link to more comprehensive notes, as I've been following up on this material.
\end{abstract}

\maketitle
\begin{quote}
	Think big, but be satisfied with small positive steps.
\end{quote}
\begin{center}
---Dave Larson
\end{center}
\onehalfspacing

\section{Inner product and normed spaces}

\begin{defn}
An inner product space is a vector space $X$ with a function $\langle x, y \rangle$ which satisfies:
\begin{enumerate}
\item $\langle x, x \rangle \geq 0$ and $\langle x, x \rangle = 0 \Leftrightarrow x = 0$
\item $\langle x+y, z \rangle = \langle x, z \rangle + \langle y, z \rangle$ and $\langle \lambda x, z \rangle = \lambda \langle x, z \rangle$
\item $\langle x, y \rangle = \overline{\langle y, x \rangle}$ 
\end{enumerate}
for all $x,y,z \in X$ and all $\lambda \in F$, where $F$ is the field associated with $X$.
\end{defn}

\begin{exer}[Equivalent definition of an inner product space]
Show that a vector space $X$ equipped with an operation $\langle x, y \rangle$ which satisfies:
\begin{enumerate}
\item $\langle x, x \rangle \geq 0$ and $\langle x, x \rangle = 0 \Leftrightarrow x = 0$
\item $\langle x+y, z \rangle = \langle x, z \rangle + \langle y, z \rangle$ and $\langle \lambda x, y \rangle = \lambda \langle x, y \rangle$
\item $\langle x, y+ z \rangle = \langle x, y \rangle + \langle x, z \rangle$ and $\langle x, \lambda y \rangle = \overline{\lambda} \langle x, y \rangle$.
\end{enumerate}
for all $x,y,z \in X$ and all $\lambda \in F$, where $F$ is the field associated with $X$, is an inner product space. In other words, show that a function satisfying positive definiteness, linearity in the first position, and conjugate linearity in the second position is necessarily conjugate symmetric, and is therefore an inner product.
\end{exer}

\begin{soln}
Let $x, y \in X$ and $\alpha \in F$, then $\langle x + \alpha y, x + \alpha y \rangle = \langle x, x \rangle + \langle \alpha y, \alpha y \rangle + \alpha \langle y, x \rangle + \overline{\alpha} \langle x, y \rangle.$ Since $\langle x + \alpha y, x + \alpha y \rangle \in {\mathbb R}$, $\alpha \langle y, x \rangle + \overline{\alpha} \langle x, y \rangle \in {\mathbb R}.$

Let $\langle y, x \rangle = a + bi$ and $\langle x, y \rangle = c+ di$. Let $\alpha = 1$, then $a + c + (b + d)i \in \mathbb R$, so $b = -d.$ Let $\alpha = i$, then $(a-c)i + (d-b) \in \mathbb R$, so $a=c.$ Since $b = -d$ and $a = c$, $\langle x, y \rangle = \overline{ \langle y, x \rangle }.$ 
\end{soln}

\begin{defn}
A normed space is a vector space $X$ with a function $\|\cdot\|: X \rightarrow [0, \infty)$ satisfying:
\begin{enumerate}
\item $\|x\| = 0 \Leftrightarrow x = 0$
\item $\|\lambda x\| = |\lambda| \|x\|$ for all $x \in X$ and $\lambda \in F$, where $F$ is the field associated with $X$
\item $\|x + y \| \leq \|x\| + \|y\|$ for all $x,y \in X$.
\end{enumerate}
\end{defn}

\begin{defn}
Let $\|\cdot\|_1$ and $\|\cdot\|_2$ be two norms on a vector space $X$. The two norms are said to be equivalent if there are constants $A,B \geq 0$ such that for all $x \in X$:
$$A\|x\|_1 \leq \|x\|_2 \leq B \|x\|_1.$$
\end{defn}

\begin{exer}
Prove that all norms over a finite dimensional vector space are equivalent.
\end{exer}

\begin{exer}
Prove that in an inner product space, $|\langle x, x \rangle |^{1/2}$ is a norm. This norm is known as the norm induced by the inner product.
\end{exer}

\begin{exer}[Proof of the Cauchy-Schwarz inequality]
Prove that for all $x, y \in H$, $| \langle x, y \rangle | \leq \|x\| \|y \|$.
\end{exer}

\begin{defn}
An orthonormal family in $X$ is a set $\{e_i\}$ of vectors such that $\|e_i\|=1$ and $\langle e_i, e_j \rangle = \delta_{ij}$.
\end{defn}

\begin{defn}
An orthonormal basis for $X$ is an orthonormal family $\{e_i\}$ in $X$ which is also a basis for $X$, i.e. $\overline{\mathop{\rm span}\{e_i\}} = X$.
\end{defn}

\section{Hilbert spaces}

\begin{defn}
A Hilbert space $H$ is a vector space with an inner product such that $H$ is a complete space under the norm associated with the inner product (i.e. all Cauchy sequences of vectors in $H$ converge to a vector $x \in H$.)
\end{defn}

\begin{exer}[Proof of Parseval's reconstruction formula]
Let $H$ be a Hilbert space (finite or infinite dimensional) and let $\{e_i\}$ be an o.n.b in $H$. Show that the reconstruction formula holds for all $x \in H$:
$$ x = \sum_i \langle x, x_i \rangle x_i. $$
\end{exer}

\begin{defn}
The Hilbert space $L^2({\mathbb R})$ is the set of all functions $f:{\mathbb R} \rightarrow {\mathbb C}$ such that $\int_{\mathbb R} |f|^2 dx < \infty$. The inner product on $L^2({\mathbb R})$ is defined as
$$ \langle f, g \rangle = \int_{\mathbb R} f(x)\overline{g(x)} dx $$
\end{defn}

\begin{exer}
Show that if $g\in L^2({\mathbb R})$ and $c \in \mathbb R\backslash \{0\}$, then $\|g(ct)\| = \frac{1}{\sqrt{|c|}} \|g(t)\|$.
\end{exer}
\section{Frames}

\begin{defn}
A frame in the Hilbert space $H$ is a collection $\{x_i\}$ of vectors in $H$ such that there exist constants $A, B > 0$ such that for all $x \in H,$
$$ A\|x\|^2 \le \sum_i |\langle x, x_i\rangle|^2 \le B \|x\|^2. $$
The constants $A,B$ are called the frame bounds.When $A=B$, the frame is a {\it tight} frame, or more specifically, an $A$-tight frame. Furthermore, a 1-tight frame is referred to as a {\it Parseval} frame.
\end{defn}

Note that:
\begin{enumerate}
\item $\{x_i\}$ must span the space (otherwise, $A$ is necessarily 0).
\item In a finite dimensional Hilbert space, every finite spanning set is a frame.
\end{enumerate}

\begin{thm}[Reconstruction]
$\{x_i\}$ is a Parseval frame iff for all $x \in H$, $x = \sum_i \langle x, x_i \rangle x_i$.
\end{thm}

\begin{thm}
If $\dim H = n$ and $\{x_i\}_{i=1}^n$ is a Parseval frame in $H$, then $\{x_i\}_{i=1}^n$ is an orthonormal basis of $H$.
\end{thm}

\begin{exer}
What conditions must the vectors $\{x_i\}_{i=1}^k \subset {\mathbb R}^n$ satisfy in order to be a tight frame in ${\mathbb R}^n$?
\label{tightframechar}
\end{exer}

\begin{soln}
Let $E$ be the $k \times n$ matrix whose rows are the vectors $\{x_i\}_{i=1}^k$:
$$ 
E =
\begin{pmatrix}
x_{i,1} & \cdots & x_{i, n} \\
\vdots  & \ddots & \vdots \\
x_{k,1} & \cdots & x_{k,n}
\end{pmatrix}.
$$
Then the tight frame condition $\sum_{i=1}^k | \langle x, x_i \rangle |^2 = A \|x\|^2 $ gives $(Ex)^TEx=Ax^Tx$ for all $x \in {\mathbb R}^n$, or $E^TE = AI_n$:
$$
E^TE = 
\begin{pmatrix}
\sum_{i=1}^k x_{i,1} x_{i,1} & \cdots & \sum_{i=1}^k x_{i,1} x_{i,k} \\
\vdots & \ddots & \vdots \\
\sum_{i=1}^k x_{i,k} x_{i, 1} & \cdots & \sum_{i=1}^k x_{i,k} x_{i, k}
\end{pmatrix}
= 
\begin{pmatrix}
A & \cdots 0 \cdots & 0 \\
\vdots & \ddots & \vdots \\
0 & \cdots 0 \cdots & A
\end{pmatrix} = AI_n.
$$

Therefore, the vectors 
$$
\left\{ x_i =
\begin{pmatrix}
x_{i,1} \\
\vdots \\
x_{i,n}
\end{pmatrix}
\right\}_{i=1}^k
\subset {\mathbb R}^n $$ are an A-tight frame iff the vectors
$$
\left\{ x^\prime_i =
\begin{pmatrix}
x_{1,i} \\
\vdots \\
x_{k,i}
\end{pmatrix}
\right\}_{i=1}^n
\subset {\mathbb R}^k,$$ i.e., the columns of $E$, are all of norm $\sqrt{A}$ and form an orthogonal family.

\end{soln}

\begin{exer}
Given positive constants $\{c_1, \ldots c_k\}$ ($k\ge 2$), does there exist a tight frame for ${\mathbb R}^2$, $\{x_i\}_{i=1}^k$, with $\| x_i \|^2 = c_i$?
\end{exer}

\begin{exer}
Given a spanning set of unit vectors in ${\mathbb R}^2$, $\{u_i\}_{i=1}^k$ ($k \ge 2$), do there exist positive constants $\{a_i\}_{i=1}^k$ such that $\{a_i u_i\}_{i=1}^k$ is a Parseval frame? Are there any restrictions on $\{u_i\}$ for this to be possible? Are these $\{a_i\}$ unique to that set?
\end{exer}

\begin{soln}
Start with a tight frame 
$
\left\{ a_i \left[
\begin{array}{c}
\cos \alpha_i \\
\sin \alpha_i 
\end{array} \right]
\right \}_{i=1,\ldots,n}
$. We would like to add a vector
$
b \left[
\begin{array}{c}
\cos \beta \\
\sin \beta 
\end{array} \right]
$
such that we have a tight frame of $n+1$ vectors, by changing $a_n$ to $d$ and $a_{n-1}$ to $c$.

By equivalence of frames under rotation, we can assume that $\alpha_n = 0$. 

We are given the two conditions
$$
\left\{
\begin{array}{l}
\sum_1^n a_i^2 \cos (2\alpha_i) = 0 \\
\sum_1^n a_j^2 \sin (2\alpha_i) = 0 
\end{array} 
\right.
$$
and must choose values for $d$ and $c$ to satisfy the conditions
$$
\left\{
\begin{array}{l}
\sum_1^{n-2} a_i^2 \cos (2\alpha_i) + c^2 \cos(2\alpha_{n-1}) + d^2 \cos(2\alpha_n) + b^2 \cos(2\beta) = 0 \\
\sum_1^{n-2} a_j^2 \sin (2\alpha_i) + c^2 \sin(2\alpha_{n-1}) + d^2 \sin(2\alpha_n) + b^2 \sin(2\beta) = 0 
\end{array} 
\right.
$$
which are equivalent to the conditions
$$
\left\{
\begin{array}{c}
( c^2 - a_{n-1}^2 ) \cos(2\alpha_{n-1}) + (d^2 - a_n^2) \cos(2\alpha_n) + b^2 \cos(2\beta) = 0 \\
( c^2 - a_{n-1}^2 ) \sin(2\alpha_{n-1}) + (d^2 - a_n^2) \sin(2\alpha_n) + b^2 \sin(2\beta) = 0
\end{array}
\right.
$$
or, since $\alpha_n=0$,
$$
\left\{
\begin{array}{c}
(c^2 - a^2_{n-1}) \cos(2\alpha_{n-1}) + (d^2 - a_n^2) + b^2 \cos(2\beta) = 0 \\
(c^2 - a^2_{n-1}) \sin(2\alpha_{n-1}) + b^2 \sin(2\beta) = 0 
\end{array}
\right.
$$
Note that this system can always be solved for a nonzero $b$--- in particular, if $\alpha_{n-1}=m\pi/2$, $m \in {\mathbb Z}$, we can avoid the necessity of $b=0$ by permuting the frame elements; a tight frame in ${\mathbb R}^2$ with more that $2$ elements must contain a vector at some suitable angle. If we let $b=1$, then this system can be solved for $d, c$:
$$
\begin{array}{c}
d^2 = a_n^2 + \sin(2\beta)\cot(2\alpha_{n-1}) - \cos(2\beta) \\
c^2 = a_{n-1}^2 - \displaystyle \frac{\sin(2\beta)}{\sin(2\alpha_{n-1})}
\end{array}
$$
$d^2$ and $c^2$ are guaranteed to be positive after a suitable scaling of the $a_n$. 

By induction this has shown that if there are $n>3$ vectors in a tight frame and 3 vectors can be scaled to yield a tight frame, then $n+1$ (the original $n$ plus another arbitrary one) can be scaled to yield one also.

Since the $a_i$ values depend upon the order of the frame elements used to determine $d$ and $c$, the $a_i$ are not unique. Also note that the only restriction placed on the $u_i$ have been identified.
\end{soln}

\begin{defn}
A $k$-tuple $(x_1, \ldots, x_k)$ in ${\mathbb R}^n$ is an external Parseval frame for a subspace $E \subseteq {\mathbb R}^n$ if for all $u \in E$ we have $u = \sum_{i=1}^k \langle u, x_i \rangle x_i$.
\end{defn}

\begin{prop}[Nate's Proposition]
If $\{x_i\}_{i=1}^k \subseteq {\mathbb R}^n$, and $\binom{n}{2}$ rank 2 orthogonal projections of the vectors are Parseval frames in ${\mathbb R}^2$, they are a Parseval frame in ${\mathbb R}^n$.
\end{prop}

\begin{prf}
Suppose we are given a set $S = \{S_i = [x_{1,i}; x_{2, i}; \ldots; x_{n,i}]\}_{i=1,\ldots,k}$ where $k \geq n$ and $\{[x_{r,i}, x_{t,i}]\}_{i=1,\ldots,k}$ are Parseval frames. We then have the relation $\sum_{i=1}^k x_{t,i} x_{r,i} = \delta_{tr}$. 

Consider a vector $v=[v_1; v_2; \ldots; v_n]$.

\begin{eqnarray*}
\sum_{i=1}^k \langle v, S_i \rangle S_i & = & \sum_{i=1}^k \left( \sum_{b=1}^n v_b x_{b,i} \right) [x_{1,i}; \ldots; x_{n,i}] \\
		& = & \sum_{i=1}^k \left[ \sum_{b=1}^n v_b x_{b,i} x_{1,i}; \ldots; \sum_{b=1}^n x_{b,i} x_{n,i} \right] \\
		& = & \sum_{b=1}^n v_b \left[ \sum_{i=1}^k x_{b,i} x_{1, i}; \ldots; \sum_{i=1}^n x_{b,i} x_{n, i} \right] \\
		& = & \sum_{b=1}^n v_b \left[ \delta_{b1}; \ldots; \delta_{bn} \right] \\
		& = & [v_1; \ldots; v_n] = v
\end{eqnarray*}
Therefore $S$ is a Parseval frame.
\end{prf}

\begin{exer}
Given the frame $\{x_i\}_{i=1}^k \subset {\mathbb R}^2$ such that $\|x_i\|=1$, characterize all scaling sets $\{a_i\}_{i=1}^k$ such that $\{a_i x_i\}_{i=1}^k$ is a tight frame. Is the set of all such scaling sets, $S$, a connected set?
\end{exer}

\begin{exer}
Show that if $\{x_i\}_{i=1}^k$ is a tight frame for ${\mathbb C}^n$ with frame bound $A$, then $$A = \frac{\sum_{i=1}^k \|x_i\|^2}{n}.$$
\end{exer}

\begin{soln}
Choose an orthonormal basis $\{e_j\}_{j=1}^n$; then using the Parseval equation, $\sum_{i=1}^k | \langle e_j, x_i \rangle|^2 = A \|e_j\|^2 = A$, so $\sum_{j=1}^n \sum_{i=1}^k |\langle e_j, x_i \rangle |^2 = \sum_{i=1}^k \|x_i\|^2 = An.$

\end{soln}

\begin{defn}
A frame is ``scalable'' if there are coefficients $\{a_i\}$ in ${\mathbb R}^+ \backslash \{0\}$ such that $\{a_ix_i\}$ is a Parseval frame.
\end{defn}

\begin{defn}
A scalable frame $\{x_i\}$ is ``stablely scalable'' if $\exists \epsilon \in {\mathbb R}^+ \backslash \{0\}$ such that $\{x_i + y_i\}$ is also scalable for any $\{y_i\}$ satisfying $\forall i, \: \|y_i\| < \epsilon$.
\end{defn}

Note that a frame is scalable iff perturbing one element leaves a stablely scalable frame. Also note that scalable frames do exist in general: cf. the Mercedes-Benz frame in ${\mathbb R}^2$.

\begin{defn}
A set $\{x_i\}$ is $\epsilon$-thick in $S_n = \{ u \in {\mathbb R}^n : \: \|u\|=1\}$ iff $\forall x \in S_n, \: \exists i \in (1,\ldots,k) \hbox{ such that } \|x - u_i\| < \epsilon$, where $\epsilon > 0$.
\end{defn}

\begin{exer}
Is there a constant $c>0$ such that if $\{x_i\}$ is $c$-thick in $S_n$, then $\{x_i\}$ is a scalable frame?
\end{exer}

\begin{defn}
Let $\{x_i\}$ be a frame. Then for all $x$,
$$x = \sum_{i=1}^k \langle x, x_i \rangle x_i^d = \sum_{i=1}^k \langle x, x_i^d \rangle x_i$$
for $\{x_i^d\}$, a dual frame of $\{x_i\}$. The ``canonical dual'' is $\{ x_i^\ast = (\theta^\ast \theta)^{-1}x_i\}$.
\end{defn}

Notice that a frame does not have a unique dual frame in general (Parseval frames do--- they are self-dual); for tight frames, $x_i^d = c x_i$ for some constant $c >0$.

\begin{exer}
Prove that $\{ x_i^\ast = (\theta^\ast \theta)^{-1} x_i \}$ is a frame with the expected properties, and find its frame bounds in terms of the frame bounds $A, B$ of $\{x_i\}$.
\end{exer}

\begin{exer}
Show that if $S$ is an invertible matrix and $\{x_i\}$ is a frame, then $\{S^{-1} x_i\}$ is a frame, and find the frame bounds in terms of the frame bounds $A, B$ of $\{x_i\}$ and the norm of $S$.
\end{exer}

\begin{exer}
Show that if $\{x_i\}$ is a scalable frame with scaling set $\{a_i\}$, then $\{a_i^2 x_i\}$ is a dual frame for $\{x_i\}$.
\end{exer}

\begin{exer}
Given a frame, when is there a scalable dual frame? If $\{x_i\}$ has a scalable dual $\{y_i\}$, does this imply that $\{x_i\}$ is also scalable?
\end{exer}

\section{Operators related to Frames}

Let $\dim H = n$ and $\{x_i\}_{i=1}^k$ be a frame in $H$ ($k \ge n$). 

\begin{defn}
The {\it analysis} operator $\theta: H \rightarrow {\mathbb C}^k$  is the function defined such that $\theta: x \mapsto (\langle x, x_i \rangle)_i.$
\end{defn}

\begin{defn}
The {\it synthesis} operator $\tau: {\mathbb C}^k \rightarrow H$ is the function defined such that $(c_i)_i^k \mapsto \sum_{i=1}^k c_i x_i.$
\end{defn}

\begin{thm}
$\tau = \theta^\ast$, that is, $\langle \theta x, y\rangle_{{\mathbb C}^k} = \langle x, \tau y\rangle_H$ for all $x \in H$ and all $y \in {\mathbb C}^k$.
\end{thm} 

\begin{prf}
\begin{eqnarray*}
\langle \theta x, y\rangle_{{\mathbb C}^k} & = & \langle (\langle x, x_i \rangle_H)_{i=1}^k, (y_i)_{i=1}^k \rangle_{{\mathbb C}^k} \\
& = & \sum_{i=1}^k \langle x, x_i \rangle_H \overline{y_i} = \sum_{i=1}^k \langle x, y_i x_i \rangle_H \\
&= & \langle x , \sum_{i=1}^k y_i x_i \rangle_H = \langle x, \tau y \rangle_H
\end{eqnarray*}
\qed
\end{prf}

\begin{defn}
The {\it frame} operator is defined as the $n\times n$ matrix $\theta^\ast\theta : H \rightarrow H$ such that $\theta^\ast\theta : x \mapsto \sum_{i=1}^k \langle x, x_i \rangle x_i$ for all $x \in H$.
\end{defn}

It has been shown in Exercise \ref{tightframechar} that $\theta^\ast\theta$ is some scalar multiple of the identity mapping iff the associated frame is tight, making the following theorem trivial.

\begin{thm}
$\{x_i\}_{i=1}^k$ is a Parseval frame (tight frame) iff\/ $\theta^\ast\theta = I_n$ (iff\/ $\theta^\ast\theta = AI_n$ for some constant $A>0$).
\end{thm}

\begin{defn}
The {\it Grammian} operator is defined as the composition $\theta \theta^\ast: {\mathbb C}^k \rightarrow {\mathbb C}^k$. 
\end{defn}

\begin{thm}
The Grammian operator has rank $n$.
\end{thm}

\begin{thm}
The Grammian and frame operators have the same nonzero eigenvalues.
\end{thm}

\begin{prop}
Tight frames in ${\mathbb R}^2$ correspond to vectors in ${\mathbb R}^2$ which sum to zero.
\end{prop}

\begin{prf}
Suppose 
$$ \left\{ x_i = a_i \left[ \begin{array}{c} \cos(\theta_i) \\ \sin(\theta_i) \end{array} \right] \right\}_{i=1}^k $$
is a tight frame. This implies $\theta^\ast \theta = AI_2 $ for some $A > 0$:
\begin{eqnarray*}
\theta^* \theta & = & 
\left[
   \begin{array}{ccc}
    \uparrow & & \uparrow \\
    x_1 & \ldots & x_k \\
    \downarrow & & \downarrow 
   \end{array}
\right]
\left[
	\begin{array}{ccc}
	 \leftarrow & x_1 & \rightarrow \\
	            & \vdots & \\
	            & \vdots & \\
	 \leftarrow & x_k & \rightarrow
	\end{array}
\right] \\
 & = & 
\left[
	\begin{array}{ccc}
		a_1 \cos(\theta_1) & \ldots & a_k \cos(\theta_k) \\
		a_1 \sin(\theta_1) & \ldots & a_k \sin(\theta_k) 
	\end{array}
\right]
\left[
	\begin{array}{cc}
		a_1 \cos(\theta_1) & a_1 \sin(\theta_1) \\
		\vdots & \vdots \\
		a_k \cos(\theta_k) & a_k \sin(\theta_k) 
	\end{array}
\right] \\
& = &
\left[
	\begin{array}{ll}
		\sum_{i=1}^k a_i^2 \cos^2(\theta_i) & \sum_{i=1}^k a_i^2 \cos(\theta_i) \sin(\theta_i) \\
		\sum_{i=1}^k a_i^2 \cos(\theta_i) \sin(\theta_i) & \sum_{i=1}^k a_i^2 \sin^2(\theta_i)
	\end{array}
\right] = AI_2
\end{eqnarray*}
Therefore, $\sum_{i=1}^k a_i^2 \cos^2(\theta_i) - \sum_{i=1}^k a_i^2 \sin^2(\theta_i) = 0$ and
$\sum_{i=1}^k \cos(\theta_i) \sin(\theta_i) = 0$. This is equivalent to the condition
$$ \sum_{i=1}^k a_i^2 
\left[
	\begin{array}{c}
		\cos(2 \theta_i) \\
		\sin(2 \theta_i) \\
	\end{array}
\right]
=
\left[
	\begin{array}{c}
		0 \\
		0 \\
	\end{array}
\right].
$$
This shows there is a bijective correspondence between all $k$-element tight frames $\{x_i\}_{i=1}^k$ and all $k$-element sets of vectors 
$$ \left\{ u_i = 
a_i^2 \left[
	\begin{array}{c}
	\cos(2\theta_i) \\
	\sin(2\theta_i) \\
	\end{array}
\right]
\right\} $$
satisfying the above condition.
\end{prf}

\begin{cor}
The Mercedes-Benz is the only tight frame of 3 unit vectors in ${\mathbb R}^2$ (up to equivalence by rotation, flips, and reordering).
\end{cor}

\begin{cor}
Every tight frame of 4 unit vectors in ${\mathbb R}^2$ is a union of 2 orthonormal bases in ${\mathbb R}^2.$
\end{cor}

\begin{cor}
Given any non-empty set of vectors, $\{x_i\}_{i=1}^k \subset {\mathbb R}^2$, there exists a vector $v \in {\mathbb R}^2$ such that $\{x_i\}_{i=1}^k \cup \{v\}$ is a tight frame in ${\mathbb R}^2.$
\end{cor}

\section{Operators}

\begin{defn}[Rank-one operator]
A rank-one operator $u\otimes v: H \rightarrow H$ is defined as $u \otimes v: w \mapsto \langle w, v \rangle u$ for all $w \in H.$
\end{defn}

\begin{defn}[Projection]
A projection $P$ is a self-adjoint, idempotent operator.
\end{defn}

Note that if $\|x\|=1$, $x \otimes x$ is a projection.

\begin{thm}
Suppose $A: {\mathbb R}^n \rightarrow {\mathbb R}$ is linear. There exists a $u \in {\mathbb R}^n$ such that for all $x \in {\mathbb R}^n$, $Ax = \langle x, u \rangle.$
\end{thm}

\begin{defn}
The operator $T: H \rightarrow H$ is self-adjoint if $T^\ast = T$, where $T$ is the unique operator (the adjoint of $T$) defined by the relation
$$ \langle Tx, y \rangle = \langle x, T^\ast y \rangle $$
for all $x,y \in H$.
\end{defn}

\begin{exer}
Prove the uniqueness and existence of $T^\ast$.
\end{exer}

\begin{defn}
The operator $T: H \rightarrow H$ is normal if $T^\ast$ commutes with $T$, i.e. $T^\ast T = T T^\ast$.
\end{defn}

\begin{thm}[Spectral theorem for finite dimensions]
Let $H$ be a finite dimensional real/complex inner product space. Then $T: H \rightarrow H$ is self-adjoint/normal iff $T$ has an orthonormal basis of eigenvectors.
\end{thm}

\begin{exer}
Suppose $(\lambda_1, v_1)$ and $(\lambda_2, v_2)$ are eigen-pairs for a self-adjoint or normal operator $T$ such that $\lambda_1 \neq \lambda_2$. Show that $\langle v_1, v_2 \rangle = 0$.
\end{exer}

\begin{defn}
The operator $T: H \rightarrow H$ is positive iff $\langle Tx, x \rangle \geq 0$ for all $x \in H$.
\end{defn}

\begin{defn}
The operator $T: H \rightarrow H$ is positive definite iff $\langle Tx, x \rangle > 0$ for all $x \neq 0$.
\end{defn}

\begin{exer}
Show that if $T$ is positive (definite), it is also self-adjoint.
\end{exer}

\begin{soln}
$\langle Tx, x \rangle = \overline{\langle x, Tx \rangle} = \langle x, Tx \rangle$, since $\langle Tx, x \rangle \in {\mathbb R}_+.$
\end{soln}

Note that if an operator is positive, it is self-adjoint, and therefore can be diagonalized (by the Spectral Theorem).

\begin{thm}
A positive operator has a unique positive square root. If $T$ is positive, we write $T^{1/2}$ or $\sqrt{T}$ to denote the positive square root of $T$.
\end{thm}

\begin{thm}
Every positive operator $T$ can be decomposed into $T=S^\ast S$ for some $S$ (the $S$ may not be unique). 
\end{thm}

As an example, let $S=T^{1/2}$. Then $S^\ast = T^{1/2}$ and $T=S^\ast S$. Note that if $T$ is positive definite, $S$ is invertible (because $\langle Tx, x \rangle = \|Sx\| > 0$ for all $x \neq 0$).

\begin{defn}
Let $T:H\rightarrow K$ (where $H, K$ are Hilbert spaces). Define the operator norm function $\|\cdot\|$ by 
\begin{eqnarray*}
\|T\| & = & \sup_{x \neq 0} \frac{\|Tx\|_K}{\|x\|_H} \\
      & = & \sup_{\|x\|_H=1} \|Tx\|_K \\
      & = & \sup_{\|x\|_H\leq 1} \|Tx\|_K.
\end{eqnarray*}
The operator norm has the following properties:
\begin{enumerate}
\item $\|T\| \geq 0$ and $\|T\|=0 \Leftrightarrow T=0$
\item $\|\alpha T\| = |\alpha|\|T\|$, where $\alpha$ is a scalar
\item $\|ST\| \leq \|S\|\|T\|$
\item $\|S+T\| \leq \|S\| + \|T\|$
\end{enumerate}
\end{defn}

\begin{exer}
Prove the norm of a self-adjoint operator is the largest absolute value of its eigenvalues. As a corollary, the norm of a positive operator is its largest eigenvalue.
\end{exer}

\begin{exer}
Show that $\|(T^\ast T)^{1/2}\|^2 = \|T^\ast T\|$.
\end{exer}

\begin{soln}
First note that $T^\ast T$ is a positive operator. Therefore $\|(T^\ast T)^{1/2}\|^2 = (\max_{i} \sqrt{\lambda_i})^2 = \max_i \lambda_i = \|T^\ast T\|$, where $\lambda_i$ denotes the $i$-th eigenvalue of $T^\ast T$.
\end{soln}

\begin{exer}
Prove that if $A$ is an invertible operator and $\|A\| < \infty$ and $\|A^{-1}\| < \infty$, then $\inf_{\|x\|=1} \|Ax\| = \left(\|A^{-1}\|\right)^{-1}$.
\end{exer}

\begin{soln}
\begin{eqnarray*}
\inf_{\|x\|=1} \|Ax\| & = & \inf_{\|x\| \neq 0} \frac{\|Ax\|}{\|x\|}
											 =  \frac{1}{\sup_{\|x\| \neq 0} \displaystyle \frac{\|x\|}{\|Ax\|}} \\
											& = & \frac{1}{\sup_{\|y\| \neq 0} \displaystyle \frac{\|A^{-1}y\|}{\|y\|}} 
											 = \left(\|A^{-1}\|\right)^{-1}
\end{eqnarray*}
\end{soln}

\begin{defn}
An isometry between two Hilbert spaces $H, K$ is a function $F: H \rightarrow K$ such that for all $x \in H$, $\|F(x)\|_K = \|x\|_H$.
\end{defn}

\section{Wavelets}

\begin{defn}
The dilation operator $D: L^2({\mathbb R}) \rightarrow L^2({\mathbb R})$ is defined as $D: f(x) \mapsto \sqrt{2} f(2x)$. 
\end{defn}

\begin{defn}
The translation operator $T: L^2({\mathbb R}) \rightarrow L^2({\mathbb R})$ is defined as $T: f(x) \mapsto f(x-1)$.
\end{defn}

\begin{exer}
Show that $D$ and $T$ are isometries on $L^2({\mathbb R})$. Also show that $D^n: f(x) \mapsto 2^{n/2}f(2^n x)$ and $T^k: f(x) \mapsto f(x -k)$.
\end{exer}

\begin{exer}
Do $D$ and $T$ commute?
\end{exer}

\begin{defn}
A function $f$ is refinable iff $f \in \mathop{\rm span}\{DT^kf\}_{k \in {\mathbb Z}}$.
\end{defn}

\begin{exer}
Show that if $f,g$ are refinable, then
\begin{itemize}
\item $f + g$ is refinable
\item $\alpha f$ is refinable for $\alpha \in \mathbb C$
\item $f \ast g$ ($f$ convolved with $g$) is refinable
\end{itemize}
\end{exer}

\begin{exer}
Show that all univariate polynomials over $\mathbb C$ are refinable.
\end{exer}

\begin{defn}
A function $\psi(x) \in L^2({\mathbb R})$ is called an orthonormal ``dyadic'' wavelet iff
$$ \{ \psi_{n,k} = D^nT^k \psi(x) = 2^{n/2} \psi(2^n x - k) :\: n,k \in {\mathbb Z}\}$$
is an orthonormal basis for $L^2({\mathbb R}).$
\end{defn}

Note that although $\psi$ may be a wavelet, $D^k \psi, \: k \in {\mathbb Z}$ may not be a wavelet.

\begin{exer}
If $\psi$ is a wavelet, under what conditions is $T^k \psi, k \in {\mathbb Z}$ a wavelet (or is a translate of a wavelet always a wavelet)?
\end{exer}

\begin{exer}
Let $\vartheta(x) = \left\{\begin{array}{c} 1 \hbox{ if $x \in [0, 1)$} \\ 0 \hbox{ otherwise}\end{array}\right. = \chi_{[0, 1)}(x)$, that is, let $\vartheta$ be the indicator function of the interval $[0, 1)$. Is $\vartheta$ a wavelet?
\end{exer}

\begin{defn}
The Haar ``wavelet'' is the function
$$ \psi(x) = \chi_{[0, 1/2)} - \chi_{[1/2, 1)}, $$
where $\chi_{[a,b)}$ is the indicator function for the interval $[a, b)$.
\end{defn}

\begin{thm}
The Haar ``wavelet'' is indeed a wavelet.
\end{thm}

\begin{prf} This is merely the outline for a proof--- particularly, the proof can be completed by proving the assumptions.

\paragraph{Assumption 1} $\{\psi_{n,k}\}_{n,k \in {\mathbb Z}}$ is an orthonormal family.

\paragraph{Assumption 2} Given $f \in L^2({\mathbb R})$, there exists $g \in L^2({\mathbb R})$ continuous with compact support which satisifies the condition $\|f - g\| < \frac{\epsilon}{3}$.

\paragraph{Assumption 3} Given $g \in L^2({\mathbb R})$ continuous with compact support, there exists a step function $h \in L^2({\mathbb R})$ such that $\|g -h \| < \frac{\epsilon}{3}$ and $h(x) = \sum_{j=1}^k c_j \chi_j(x)$ where the $\{\chi_j\}_{j=1}^k$ are characteristic functions of dyadic intervals (intervals whose endpoints can be represented in the form $\frac{k}{2^n}$ where $k, n \in {\mathbb Z}$ and $k$ is odd for uniqueness).

Given the above $h$, there exists a $p \in \mathop{\rm span}\{\psi_{n,k}\}$ such that $\|h-p\| < \frac{\epsilon}{3}$. This can be shown by exploiting the fact that there is some smallest dyadic interval of length $\kappa$ over which $h$ remains constant. Call $q_1(x)$ the step function obtained by averaging $h(x)$ at the endpoints of intervals of length $2\kappa$. Then $h(x) = q_1(x) + p_1(x)$ where $p_1(x)$ is a function in the span of $\{\psi_{n,k}\}$ due to the averaging operation used to define $q_1(x)$. By repeating this process, i.e. $q_2(x) = q_1(x) + p_2(x), \: \ldots$ and noting that the fact that $h$ is of compact support implies that $\lim_{n\rightarrow \infty} \|q_n(x)\| = 0$, we see that it is possible to find a $p \in \mathop{\rm span}\{\psi_{n,k}\}$ such that $\| h - p \| < \frac{\epsilon}{3}$. 

Therefore, there is a $p \in \mathop{\rm span}\{\psi_{n,k}\}$ such that
$$ \|f - p\| = \| f - g + g - h + h - p \| \leq \|f -g \| + \| g -h \| + \|h-p\| = \epsilon, $$
which implies that for all $f \in L^2({\mathbb R})$, $f \in \overline{\mathop{\rm span}\{\psi_{n,k}\}}$, or equivalently,  $\{\psi_{n,k}\}_{n,k \in {\mathbb Z}}$ is an orthonormal basis in $L^2({\mathbb R})$.
\qed
\end{prf}

The above sketch of the proof that the Haar ``wavelet'' is a wavelet introduces the idea of \emph{levels of detail} or \emph{multiresolution analysis}. The $\{p_n\}$ functions in the span of $\{\psi_{n,k}\}$ naturally describe the function $f$ at different levels of detail: $p_1$ provides the finest details of $f$ while $p_n$ describes coarser and coarser features of $f$ as $n$ increases. The $\{q_n\}$ can be seen as containing the smoothing information necessary for reconstructing the function $f$ from the various levels of detail $\{p_n\}$.

\section{Wavelet sets}

\begin{defn}
An orthonormal dyadic wavelet set on $\mathbb R$ is a subset $E \subset \mathbb R$ such that
\begin{enumerate}
\item $\chi_E \in L^2({\mathbb R})$ (since $\|\chi_E\| = \sqrt{m(E)}$, this implies $m(E) < \infty$)
\item $\frac{1}{\sqrt{m(E)}} \chi_E$ is the Fourier transform of an orthonormal dyadic wavelet.
\end{enumerate}
\end{defn}

\begin{prop}[Characterization of wavelet sets]
$E \subset \mathbb R$ is a (dyadic) wavelet set iff
\begin{enumerate}
\item $\{E+2\pi n\}_{n\in \mathbb Z}$ is a measurable partition of $\mathbb R$; i.e. ${\mathbb R}\backslash \bigcup_{n\in \mathbb Z} \{ E + 2\pi n\}$ has measure zero, and $\bigcap_{n=i,j} \{E+2\pi n\}$ has measure zero if $i\neq j$. In short, $E$ is a $2\pi$-translation ``tiler'' of $\mathbb R$
\item $\{2^n E\}_{n\in \mathbb Z}$ is a $2$-dilation ``tiler'' of $\mathbb R$ (once again modulo sets of measure zero).
\end{enumerate}
\end{prop}

\begin{exer}
Find (compute) all $2$-interval dyadic wavelet sets (so $E = [-2b, -b) \cup [a, 2a)$ for $a, b > 0$ is a wavelet set).
\end{exer}

\begin{exer}
Find all $3$-interval dyadic wavelet sets.
\end{exer}

\begin{exer}
Find the symmetric $4$-interval wavelet sets.
\end{exer}

\begin{defn}
A set $E$ is $2\pi$-translation congruent to a set $F$ if there is a surjection $\phi : E \rightarrow F$ such that $\forall x \in E, \: \phi(x)-x = 2\pi k$ for some $k \in {\mathbb Z}$.
\end{defn}

\begin{exer}
Suppose $E \subset {\mathbb R}$ is a set which is $2\pi$-translation congruent to $E_0$, some interval of length $2\pi$. Then for each $x \in E, \: \exists\,!\, m_x \in {\mathbb Z}$ such that $x - 2\pi m_x \in E_0$. Let $E_m = \{x :\: m_x = m\}$ for each $m \in {\mathbb Z}$. Then $\{E_m\}_{m\in {\mathbb Z}}$ is a partition of $E$ and $\{E_m - 2\pi m\}_{m \in {\mathbb Z}}$ is a partition of $E_0$.

Suppose $E = [a_1, b_1) \cup [a_2, b_2) \cup \cdots \cup [a_n, b_n)$, with $a_1 < b_1 < a_2 < b_2 < \cdots$. Does $\exists x \in {\mathbb R}$ such that if $E_0 = [ x, x+2\pi)$, then each interval $[a_i, b_i)$ is entirely contained in some $E_j$?
\end{exer}

\section{Sampling Theory}

\begin{thm}[Riesz Representation Theorem]
Let $\alpha(\cdot)$ be a continuous linear functional on a Hilbert space $H$. Then $\exists\,!\, z \in H$ such that $\forall x \in H, \: \alpha(x) = \langle x, z \rangle$.
\end{thm}

\begin{proof}
Let $\{e_i\}$ be an orthonormal basis for $H$. Then $\forall x \in H, \: x= \sum_{i=1}^\infty \langle x, e_i \rangle e_i$, so $\alpha(x) = \alpha\left( \sum_{i=1}^\infty \langle x, e_i \rangle e_i \right)$. By continuity, $\alpha(x) = \sum_{i=1}^\infty \langle x, e_i \rangle \alpha(e_i)$. Let $z = \sum_{i=1}^\infty \overline{\alpha(e_i)} e_i$, then $\alpha(x) = \langle x, z \rangle$.
\end{proof}

\begin{exer}
Use the Riesz Representation Theorem to find the vector $v$ associated with the linear functional $d_t : P_N[0,1] \rightarrow {\mathbb R}$ defined by $d_t: f \mapsto \frac{df}{dt}(t_0)$ for a fixed $t_0 \in {\mathbb R}$.
\end{exer}

\begin{exer}
Show that any continuous linear functional on a Hilbert space $H$ is in the span of the set of point evaluation functionals on $H$.
\end{exer}

\begin{defn}
Let $F$ be a Hilbert space of functions on domain $D$ with inner product $\langle \cdot, \cdot, \rangle$.

Let $T = \{t_1, t_2, \ldots\}$ be a finite or infinite sequence of points in $D$. $T$ is said to be a set of sampling for $F$ if the sampling operator $S : F \rightarrow l^2_{|T|}$ defined by 
$$S: f \mapsto \begin{pmatrix} f(t_1) \\ f(t_2) \\ \vdots \end{pmatrix}$$
is bounded (i.e. continuous) and bounded below; i.e., if 
$$\exists A, B > 0 \hbox{ such that } \forall f \in F, \: A\|f\|^2 \leq \sum_{i=1}^{|T|} |f(t_i)|^2 \leq B\|f\|^2.$$
\end{defn}

\begin{thm}
Every set of sampling $t = \{t_i\}$ determines a unique frame $g = \{g_i\}$ such that $S_t = \theta_g$.
\end{thm}

\begin{proof}
Use the Riesz representation theorem to rewrite $S_t$ in terms of vectors $\{g_i\}$ in $F$:
$$S: f \mapsto \begin{pmatrix} f(t_1) \\ f(t_2) \\ \vdots \end{pmatrix} = 
\begin{pmatrix} \langle f, g_1 \rangle \\ \langle f, g_2 \\ \vdots \end{pmatrix},$$
then note that 
$$\forall f \in F, \: A\|f\|^2 \leq \sum_{i} |\langle f, g_i \rangle|^2 \leq B\|f\|^2,$$
so the $\{g_i\}$ form a frame with bounds $A, B$, and $S_t = \theta_g$.
\end{proof}

\begin{exer}
Suppose that we are given the set of sampling $t= \{t_1, \ldots\}$ for $F$, and we know $S_t$ is isometric, i.e. $\|f\|^2 = \|Sf\|^2 = \sum_i |f(t_i)|^2.$ Can you reconstruct $f$ from $Sf$--- if so, how?
\end{exer}

\begin{soln}
Yes. Use the Riesz Representation Theorem to find the associated frame $g = \{g_i\}$ in $F$. Then $S_t =\theta_g$ is isometric, so $f = \sum_i \langle f, g_i \rangle g_i = \sum_i f(t_i) g_i$ for all $f \in F$.
\end{soln}

A set of sampling will be said to have a property such as tightness, scalability, etc. if its associated frame possesses that property.

\begin{exer}
Do the following types of sets of sampling exist in any Hilbert function space $F$? Give conditions for existence, and characterizations if possible.
\begin{enumerate}
\item tight sets of sampling
\item scalable sets of sampling
\item stablely scalable sets of sampling 
\end{enumerate}
\end{exer}

In general, sampling sets determine frames via the Riesz Representation Theorem, but not all frames determine sampling sets.

\begin{exer}
For several Hilbert function spaces, characterise which frames $\{g_i\}$ lead to sampling sets in a given Hilbert space $H$. That is, determine which frames consist solely of vectors which determine point evaluation functionals.
\end{exer}

\begin{exer}
Define an $\epsilon$-mesh ($\epsilon > 0$) on $[0,1]$ as a set $\{t_1, t_2, \ldots, t_n\}$ such that $\forall x \in [0,1], \: |x-t_i| < \epsilon$ for some $i \in \{1,\ldots, n\}$. Is there a $\delta > 0$ such that if $\epsilon < \delta$, all $\epsilon$-meshes are scalable sets of sampling in the Hilbert space $P_2[0,1]$?
\end{exer}

\end{document}