\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{21 --- October 25, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Max B, Sebastien Roch}

\section{Overview}
In the last lecture, we discussed estimation of the covariance matrix of both subgaussian and more general random vectors. In this lecture, we discuss an application to principal component analysis (PCA). This lecture is based on Section 8.2 from Wainwright \cite{wainwright:2019}.

\section{Application to Principal Component Analysis}
\subsection{General Setting and Goal}
Recall the setting of covariance estimation from the previous lecture:
For a mean-zero random vector $\mathbf{X}\in \mathbb{R}^d$, the covariance matrix is  $\mathbf{\Sigma}:=\mathbb{E}\left[\mathbf{X}\mathbf{X}^{\top}\right]$, so that $\mathbf \Sigma_{ij}=\mathbb{E}\left[\mathbf{X}_i\mathbf{X}_j\right]$.

PCA is a dimension-reduction technique. $\mathbf{X}$ may be a high-dimensional, but its action might be mostly concentrated in lower dimensional space. Hence we are interested in estimating the direction $\mathbf{u}\in \mathbb{S}^{d-1}$ that maximizes the variance of the scalar projection $\langle \mathbf{X},\mathbf{u}\rangle$. Define
\begin{equation*}
  \mathbf{u}_{1}
  \in \text{argmax}_{\mathbf{u}\in \mathbb{S}^{d-1}} \text{Var}\left[ \left\langle \mathbf{X},\mathbf{u} \right\rangle \right].
\end{equation*}
Since $\mathbf{X}$ is mean-zero, it follows that $\left\langle \mathbf{X},\mathbf{u} \right\rangle$ is also mean-zero. Therefore 
$\rm{Var}\left[ \left\langle \mathbf{X},\mathbf{u} \right\rangle \right]=\mathbb{E}\left[ \left\langle \mathbf{X},\mathbf{u} \right\rangle ^{2}\right]$. Moreover, at the beginning of the previous lecture we showed that $\mathbb{E}\left[ \left\langle \mathbf{X},\mathbf{u} \right\rangle ^{2}\right] = \left\langle \mathbf{u},\mathbf{\Sigma}\mathbf{u} \right\rangle$. Therefore
\begin{equation*}
   \mathbf{u}_{1}
  \in \text{argmax}_{\mathbf{u}\in \mathbb{S}^{d-1}} \left\langle \mathbf{u},\mathbf{\Sigma}\mathbf{u} \right\rangle.
\end{equation*}
Therefore by variational calculus (See, e.g. the ``Review of eigenvalues'' section in Lecture 16), the solution $\mathbf{u}_{1}$ is the maximal eigenvector of $\mathbf{\Sigma}$ (i.e. corresponding to the largest eigenvalue of $\mathbf{\Sigma}$,)

\noindent\textbf{Remark:} Having obtained the first principal component $\mathbf{u}_{1}$, we could then go on to obtain $\mathbf{u}_{2}\in \rm{argmax}_{\mathbf{u}\in \mathbb{S}^{d-1}\cap \rm{span}\left\{ \mathbf{u}_{1} \right\}^{\perp}} \text{Var}(\left\langle \mathbf{X},\mathbf{u} \right\rangle)$ and so forth... but we won't do that today.)


Given $n$ i.i.d. samples $\mathbf{X}^{(1)},\ldots,\mathbf{X}^{(n)}\sim \mathbf{X}$, the \textbf{sample covariance} is defined as
\begin{equation}\label{sample-covariance-definition}
 \mathbf{\hat{\Sigma}}_n:=\frac{1}{n}\sum_{i=1}^n \mathbf{X}^{(i)}\mathbf{X}^{(i)\top}  
\end{equation}
Our goal is to estimate $\mathbf{u}_{1}$ with these samples. To this end, define
\begin{equation*}
  \hat{\mathbf{u}} \in \text{argmax}_{\mathbf{u}\in \mathbb{S}^{d-1}}\left\langle \mathbf{u},\mathbf{\hat{\Sigma}}\mathbf{u}\right\rangle
\end{equation*}
We wish to know how close are $\mathbf{u}_{1}$ and $\mathbf{\hat{u}}$. In particular, we wish to estimate $\norm{\mathbf{u}_{1}-\mathbf{\hat{u}}_{1}}_{2}$, the Euclidean distance between $\mathbf{u}_{1}$ and $\mathbf{\hat{u}}$. Equipped with the theorems from the previous lecture, we have estimates of $\norm{\mathbf{\hat{\Sigma}_{n}-\mathbf{\Sigma}}}$; moreover, $\mathbf{\hat{\Sigma}}$ can be seen as a perturbation $\mathbf{\Sigma}$, so we shall utilize perturbation theorems as well.

We consider the following toy model.

\subsection{Spiked Covariance Model}
\begin{definition}[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.\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}

The idea here is that $\mathbf{\theta}^{*}$ is a ``secret direction'', so that we are adding variation in the $\mathbf{\theta}^{*}$ direction. The constant $\nu$ can be thought of as the ``strength'' of the hidden signal.

Since $\mathbf{X}$ is mean-zero and isotropic, its covariance is easily computed as
\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 $\mathbf{\theta}^{*}$ direction maximizes variance. Indeed, $\mathbf{\theta}^{*}=\mathbf{u}_{1}$ has eigenvalue $1+\nu$ since $\mathbf{\Sigma}\mathbf{\theta}^{*} = (1+\nu)\mathbf{\theta}^{*}$ whereas if $\left\langle \mathbf{z},\mathbf{u}_{1} \right\rangle =0$ then $z$ is an eigenvector with eigenvalue $1$, since $\mathbf{\Sigma}\mathbf{z}=\mathbf{z}$. Hence the eigengap is $(1+\nu)-1 = \nu$.


We make the further assumption that the subgaussian norms are all 1. Call this assumption $(*)$.

\begin{theorem}[Cor 8.7 in \cite{wainwright:2019}]
  \label{wainwright:cor8.7}
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}

\noindent\textbf{Remarks:}
\begin{enumerate}
\item The assumption that $\sqrt{\frac{\nu+1}{\nu^{2}}}\sqrt{\frac{d}{n}}\leq C_{0}$ means that $\frac{d}{n}$ cannot be too large.
\item The constants $C_{1},C_{2},$ and $C_{3}$ are universal, i.e. they do not depend on $n$ or $d$.
\end{enumerate}



\subsection{A Perturbation Bound}
Consider the \textbf{perturbation matrix } $\mathbf{P}:=\mathbf{\hat{\Sigma}}-\mathbf{\Sigma}$. Consider the real $d\times d$ orthonormal matrix $U$ whose columns are the eigenvectors of $\mathbf{\Sigma}$. Then $U=(\theta^{*}|U_{2})$ where $U_{2}$ is a $d\times (d-1)$ matrix whose columns are an orthonormal basis of $\text{span}\left\{ \theta^{*} \right\}^{\perp}$. Define the \textbf{transformed perturbation matrix}
\begin{equation*}
  \mathbf{\tilde{P}}:= U^{\top}\mathbf{P}U =\begin{pmatrix}
\tilde{p}_{11} & \mathbf{\tilde{p}}^{\top} \\
\mathbf{\tilde{p}} & \mathbf{\tilde{P}}_{22}  
\end{pmatrix}
\end{equation*}
where $\tilde{p}_{11}\in \mathbb{R}$, $\mathbf{\tilde{p}}\in \mathbb{R}^{d-1}$, and $\mathbf{\tilde{P}}_{22}\in \mathbb{R}^{(d-1)\times(d-1)}$.

We will use the following bound version of Davis-Kahan (see Lecture 16) to prove Theorem \ref{wainwright:cor8.7}.

\begin{theorem}[Theorem 8.5 in \cite{wainwright:2019}] \label{wainwright:thm8.5}
  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{theorem}
\noindent\textbf{Remark:} This theorem is similar to the more basic Davis-Kahan result discussed in Lecture 16 (Theorem 4.5.5 in Vershynin \cite{vershynin}). To see the similarity, note that since $\norm{\theta^{*}}_{2} =1$ and $\norm{U_{2}^{\top}}_{2}=1$,
\begin{equation*}
  \norm{\mathbf{\tilde{p}}}_{2} = \norm{U_{2}^{\top}\mathbf{P}\theta^{*}}_{2}\leq  \norm{U_{2}^{\top}}_{2}\norm{\mathbf{P}}_{2}\norm{\theta^{*}}_{2} = \norm{\mathbf{P}}_{2}= \norm{\mathbf{\hat{\Sigma}}-\mathbf{\Sigma}}_{2}
\end{equation*}
so that by also using the inequality $\norm{\mathbf{P}}_{2}<\nu/2$, the right hand side of Theorm \ref{wainwright:thm8.5} can be bounded above by $C \norm{\mathbf{\hat{\Sigma}}-\mathbf{\Sigma}}_{2}$.

\subsection{Preview of Proof of Theorem \ref{wainwright:cor8.7}}
In order to gainfully employ Theorem \ref{wainwright:thm8.5} in order to prove Theorem \ref{wainwright:cor8.7}, it is necessary to bound both $\norm{\mathbf{P}}_{2}$ and $\norm{\mathbf{\tilde{p}}}_{2}$. Since $X^{(i)}= \mathbf{w}_{i}+\sqrt{\nu}\epsilon_{i}\theta^{*}$ for $i=1,\ldots,n$, therefore by \eqref{sample-covariance-definition}
\begin{equation*}
  \mathbf{\hat{\Sigma}}_{n} = \frac{1}{n} \sum_{i=1}^{n}\left[ \mathbf{w}_{i}+\sqrt{\nu}\epsilon_{i}\theta^{*} \right]\left[ \mathbf{w}_{i}+\sqrt{\nu}\epsilon_{i}\theta^{*} \right]^{\top}.
\end{equation*}
Using this, the perturbation matrix may be decomposed in the following way:
\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*}
where $\mathbf{\bar{w}} = \frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\mathbf{w}_{i}$. We then deal with each of the terms individually, which is the subject of the next lecture.
%\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}
