\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}

\begin{document}

\lecture{22 --- October 27, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Sang Yup Han}

\section{Overview}

In the last lecture we applications to principal component analysis and previewed the proof of Cor. 8.7 in \cite{wainwright:2019}. 

In this lecture we finish the proof of Cor. 8.7.

\section{Review of Last Lecture}

Reviewing last lecture, we talked about the spiked covariance model. As a review of the setup:

\begin{definition}
  Let $\textbf{W}\in \mathbb{R}^{d}$ be an isotropic, subgaussian random vector with mean zero and norm $\leq 1$, and let $\epsilon$ be an independent real-valued subgaussian random variable with mean zero and variance 1.\footnote{Note \cite{wainwright:2019} uses $\xi$ rather than $\epsilon$} 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.
\end{definition}

With this model in mind, we defined the following matrix:

$$ \hat{\mathbf{\Sigma}}_n = \frac{1}{n} \sum_{i=1}^n \mathbf{X}^{(i)} \mathbf{X}^{(i) \top}$$

and the corresponding $\hat \theta \in \mathbb{R}^d$, the max eigenvalue of $\hat{\mathbf{\Sigma}}_n$. With these definitions in mind, we stated the following theorem from $\cite{wainwright:2019}$
    
    \begin{theorem}
    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 $\norm{\hat{\theta}-\theta^{*}}_{2}\leq C_{1}\sqrt{\frac{\nu+1}{\nu^{2}}}\sqrt{\frac{d}{n}}$ with probability $1-C_{2}\exp\{-C_{3}d\}$.
    \end{theorem}

Recall the perturbation matrix from last lecture, $\mathbf{P} := \hat{\mathbf{\Sigma}}_n - \mathbf{\Sigma}$. Define the following:
$$ \tilde{ \mathbf{p}} = \mathbf{U_2}^\top \mathbf{P} \theta^*$$
where the columns of $\mathbf{U}_2 \in \mathbb{R}^{d\times d-1}$ form an orthonormal basis of $ \theta^{* \top}$

We have the following lemma, (Thm 8.5 in \cite{wainwright:2019}), which we do not prove in lecture, but the proof boils down to linear algebra calculations. 

\begin{theorem}[Theorem 8.5 in \cite{wainwright:2019}] \label{wainwright:thm8.5}
  If $\| \mathbf{P} \|_{2} <\frac{\nu}{2}$ then
  \begin{equation*}
    \| \hat{\theta}-\theta^{*} \|_{2}\leq \frac{2 \| \mathbf{\tilde{p}}
\|_{2}} {\nu - 2 \|\mathbf{P}\|_{2}}
  \end{equation*}
\end{theorem}

\section{Proof of Theorem 2}

Now we present the proof of Theorem 2 by applying Theorem 3. To do this, we bound the norm of $\mathbf{P}$. 

\begin{proof}
The idea of the proof is to divide $\mathbf{P}$ into three contributions. 

\begin{align*}
  \mathbf{P} &= \mathbf{\hat{\Sigma}}_{n} -\mathbf{\Sigma}\\
             &=\nu \left( \frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}^{2}-1 \right)\theta^{*}\theta^{*\top} + \sqrt{\nu}\left( \mathbf{\bar{w}}\theta^{*\top}+ \theta^{*}\mathbf{\bar{w}}^{\top} \right)+ \left( \frac{1}{n}\sum_{i=1}^{n}\mathbf{w}_{i}\mathbf{w}_{i}^{\top}-I_{d} \right)
\end{align*}
\end{proof}
where $\mathbf{\bar{w}} = \frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\mathbf{w}_{i}$. Intuitively, the terms break up in the following way. The first term is the main contributions from $\theta^*$, the middle term deals with both the contributions from $\bar{\mathbf{w}}$ and $\theta^*$. The last term deals with the expectation of the values of $\mathbf{w}_i$. Call the first term $\mathbf{P}_1$, the second term $\mathbf{P}_2$, the third term $\mathbf{P}_3$. By the triangle inequality, we have that:
$$ \| \mathbf{P} \|_2 < \| \mathbf{P}_1 \|_2 + \| \mathbf{P}_2 \|_2 + \| \mathbf{P}_3 \|_2$$
We go through these individually. Starting with $\mathbf{P}_3$, previously we showed that with probability $1 - 2e^{-u}$ that:
$$ \| \mathbf{P}_3 \| \leq C (\sqrt{\frac{d+u}{n}}  + \frac{d+u}{n}) $$
So we take $ u = cd$. Use the fact that $\| \textbf{W}^{(i)} \|_2 \leq 1$ to get that:
$$\| \mathbf{P}_3 \| \simeq c' \sqrt{\frac{d}{n}}$$
Turning to $\mathbf{P}_1$, we have that the expectation of $\epsilon_i^2$ is 1 because we took it be mean zero, variance 1 and subgaussian. We can consider each piece of $\mathbf{P}_1$ separately as: 
$$\| \mathbf{P}_1 \|_2 \leq \nu | \frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}^{2}-1 | \| \theta^{*}\theta^{*\top} \|_2 $$
Note that $\|\theta^{*}\theta^{*\top} \|_2 = 1 $. We also have the following lemma (Lemma 2.7.7 in \cite{vershynin}):
\begin{lemma}
If $X, Y$ are sub-gaussian, then:
$$ \| XY \|_{\psi_1} \leq \| X \|_{\psi_2} \| Y \|_{\psi_2}$$
In particular, $ \| \epsilon_i^2 \|_{\psi_1} \leq 1$. 
\end{lemma}
Let $z = | \frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}^{2}-1 | $. By Bernstein's inequality and the fact that the expectation of $\epsilon^2$ is $1$, we prove using Cor 2.8.3 in \cite{vershynin} that:
$$\mathbb{P} (z \geq t) \leq 2 \exp(-c \min(t^2,t)n)$$
where $n$ is the number of samples. Take $t = c\sqrt{\frac{d}{n}}$. Letting this $c$ be as small as we'd like, then we can get the bound:
$$ \| \mathbf{P}_1 \|_2 \leq \frac{\nu}{8}$$ 

Using Lemma 3 above, we can also get that:
$$ \| \mathbf{P}_2 \|_2 \leq \sqrt{\nu} \cdot 2 \|  \bar{\mathbf{w}} \theta^{*\top} \|_2 \leq 2 \sqrt{\nu} \| \bar{\mathbf{w}} \|_2 $$

Now we get the following series of claims. 
\begin{claim}
With probability $1 - ce^{-c' d}$, we have that:
$$ \| \bar{\mathbf{w}} \|_2 \leq c'' \sqrt{\frac{d}{n}}$$ 

\end{claim}

Suppose Claim 4 is true, then we have:
\begin{claim}
With probability $1- ce^{-c' d}$, we have that:
$$ \| \mathbf{P}_2 \|_2 \leq c'' \sqrt{\nu} \sqrt{\frac{d}{n}}$$
\end{claim}

Suppose both Claim 4 and 5 are true, then we have:
\begin{claim}
With probability $1 - c e^{-c'd}$
$$ \| \mathbf{P} \|_2 < \frac{\nu}{4}$$
\end{claim}

The key to this claim is the assumption that $\sqrt{\frac{\nu+1}{\nu^{2}}}\sqrt{\frac{d}{n}}\leq C_{0}$. By letting $C_0$ be small enough, then we can get the above claim by combining the remaining inequalities. With this claim, we're one step closer to applying Theorem 2 (Thm 8.5 in \cite{wainwright:2019}) to finish the proof of Cor. 8.7. 



%\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}