\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {\bf MATH888: High-dimensional probability and statistics } \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribe: #4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

% custom command used in these notes
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}

\begin{document}

\lecture{23 --- October 29, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Yuchen Li}

\section{Overview}
In the last lecture, we discussed the proof of Theorem 2 from lecture 21. In this lecture, we finish this proof. This lecture is based on Section 8.2 from Wainwright \cite{wainwright:2019}.

\section{Review of PCA in Spiked Covariance Model}
Let $\textbf{W}\in \mathbb{R}^{d}$ be an isotropic, subgaussian random vector with mean zero, and let $\epsilon$ be an independent real-valued subgaussian random variable with mean zero and variance 1. The \textbf{spiked covariance model} is given by the random vector $\mathbf{X}$ with distribution
  \begin{equation*}
    \mathbf{X} \sim  \mathbf{W} + \sqrt{\nu}\epsilon \mathbf{\theta}^{*}
  \end{equation*}
  where $\nu>0$, $\mathbf{\theta}^{*}\in \mathbb{S}^{d-1}$ are fixed.
  Since $\mathbf{X}$ is mean-zero and isotropic, the covariance is
\begin{equation*}
  \mathbf{\Sigma} = I_{d} + \nu \mathbf{\theta^{*}} \mathbf{\theta^{*}}^{\top}
\end{equation*}
where $I_{d}$ is the $d\times d$ identity matrix.
The maximal eigenvalue is $1+\nu$ with eigenvector $\mathbf{\theta^{*}}$.
Now we restate the main theorem we proved partially in last lecture,
\begin{theorem}[Cor 8.7 in \cite{wainwright:2019}]
  \label{main}
Assume $n>d$. Given $n$ iid samples from the spiked covariance model with $(*)$,  and assuming that $\sqrt{\frac{\nu+1}{\nu^{2}}}\sqrt{\frac{d}{n}}\leq C_{0}$, it holds that if $\hat{\mathbf{\theta}}$ is the maximal eigenvector of $\mathbf{\hat{\Sigma}}_{n}$, then with probability $1-C_{2}\exp\{-C_{3}d\}$, we have
$$\norm{\hat{\theta}-\theta^{*}}_{2}\leq C_{1}\sqrt{\frac{\nu+1}{\nu^{2}}}\sqrt{\frac{d}{n}}$$ 
\end{theorem}
To prove the theorem, we also need the following lemma,
\begin{lemma}[Theorem 8.5 in \cite{wainwright:2019}] \label{wainwright:thm8.5}
 Consider $\mathbf{P}=\mathbf{\hat{\Sigma}}-\mathbf{\Sigma}$ and $\mathbf{\tilde{P}}= U^{\top}_{2}\mathbf{P} \mathbf{\theta^{*}}$ where the columns of $U^{\top}_{2}$ forms an orthonormal basis of $\text{span}\left\{ \theta^{*} \right\}^{\perp}$. If $\norm{\mathbf{P}}_{2}<\frac{\nu}{2}$ then
  \begin{equation*}
    \norm{\hat{\theta}-\theta^{*}}_{2}\leq \frac{2 \norm{\mathbf{\tilde{P}}}_{2}}{\nu - 2 \norm{\mathbf{P}}_{2}}
  \end{equation*}
\end{lemma}

\section{Proof of Theorem \ref{main}}
We continue the proof of Theorem \ref{main} by using Lemma \ref{wainwright:thm8.5} in this section. Last time, we decomposed $P$ as
$$\mathbf{P}=\mathbf{P}_{1}+\mathbf{P}_{2}+\mathbf{P}_{3}$$
 we claimed with probability $1-C_{4}exp\{-C_{5}d\}$, we have
 $$\norm{\mathbf{P}_{1}}_{2}\leq \frac{\nu}{8}, \quad \norm{\mathbf{P}_{2}}_{2}\leq C_{6}\sqrt{\nu}\sqrt{\frac{d}{n}}, \quad \norm{\mathbf{P}_{3}}_{2}\leq C_{7}\sqrt{\frac{d}{n}}$$
thus we have
$$\norm{\mathbf{P}}_{2}\leq \frac{\nu}{4}$$
Now we begin with the following claim,
\begin{claim}
\label{claim 1}
Let $\bar{W}=\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}W^{(i)}$, with probability $1-C_{8}\exp \{-C_{9}d\}$ we have
$$\norm{\bar{W}}_{2}\leq C_{10} \sqrt{\frac{d}{\nu}}$$
\end{claim}
We first review the concept of $\epsilon$ net before we prove the Claim \ref{claim 1}.
\subsection{Review of $\varepsilon$\textendash net}
Recall $N\subseteq T$ is $\varepsilon$\textendash net of $K\subseteq T$ if for $\forall x\in K$, $\exists x_{0}\in N$ so that $\norm{x-x_{0}}\leq \varepsilon$. Also, $N(K,\varepsilon)$ denotes the smallest size of an $\varepsilon$\textendash net of the set $K$.

Recall the Lemma 4 from lecture 19, we showed the covering number of the unit Euclidean ball $B_2^d$ satisfy the following for any $\varepsilon > 0$:
\begin{equation}
\mathcal{N}\left(B_{2}^{d}, \varepsilon\right) \leq\left(\frac{2}{\varepsilon}+1\right)^{d}. \label{ball}
\end{equation}
Take 
\subsection{Proof of Claim \ref{claim 1}}
Now we prove Claim \ref{claim 1} utilizing $\varepsilon$\textendash net,
\begin{proof}
Note $$\norm{\bar{W}}_{2}=\sup_{u\in B_{2}^d } \langle u, \bar{W}\rangle$$
Let $N$ be the $\frac{1}{2}$\textendash net of $B^{d}_{2}$, $\forall u\in B^{d}_{2}$, $\exists z\in N$ such that
$$x=u-z \quad with \quad \norm{x}_{2}\leq \frac{1}{2}$$  
also by taking $\varepsilon=\frac{1}{2}$ in inequality \ref{ball}, we have
$$\mathcal{N}\left(B_{2}^{d}, \frac{1}{2}\right) \leq 5^{d}$$
then 
\begin{equation*}
\begin{aligned}
\norm{\bar{W}}_{2}&=\sup_{u\in B_{2}^d } \langle u, \bar{W}\rangle\\
&\leq \sup_{z\in N}\langle z, \bar{W}\rangle + \sup_{x\in \frac{1}{2}B^{d}_{2}}\langle x,\bar{W}\rangle \\
&=\sup_{z\in N}\langle z, \bar{W}\rangle +\frac{1}{2}\norm{\bar{W}}_{2}
\end{aligned}
\end{equation*}
so we have
$$\norm{\bar{W}}_{2} \leq 2\sup_{z\in N}\langle z, \bar{W}\rangle$$
Now we let $t=C_{12}\sqrt{\frac{d}{\nu}}$, then the probability 
\begin{equation*}
\begin{aligned}
\mathbb{P}\left(2\sup_{z\in N}\langle z, \bar{W}\rangle \geq t\right) &\leq \sum_{z\in N}\mathbb{P}(2\langle z, \bar{W}\rangle \geq t) \\
&=\sum_{z\in N}\mathbb{P}\left(\frac{2}{n}\sum_{i=1}^{n}\epsilon_{i}\langle z, \bar{W}^{(i)}\rangle \geq t\right) \\
& \leq 5^d \exp (-C_{11}C_{12}^{2} d)
\end{aligned}
\end{equation*}
note $\epsilon_{i}$ and $\langle z, \bar{W}^{(i)}\rangle$ are sub-Gaussian so the product of them is sub-exponential, we get the last inequality by Bernstein inequality. This finishes the proof.
\end{proof}
Now with the bound of $\norm{\bar{W}}_{2}$, we could find the bound of $\tilde{P}$ and $\mathbf{P}_{2}$. This all together could prove Theorem \ref{main} by Lemma \ref{wainwright:thm8.5}.






%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{wainwright:2019}
  Wainwright, M. J. (2019). \emph{High-Dimensional Statistics: A Non-Asymptotic Viewpoint}. CUP.

\bibitem{vershynin}
  Roman Vershynin, \emph{High-dimensional probability: An introduction with applications in data science},  Cambridge University Press, 2018.

\end{thebibliography}

\end{document}