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

\usepackage{bm}
\usepackage[breaklinks=true,bookmarks=false]{hyperref}
\usepackage{cleveref}
\usepackage{autonum}
\usepackage{url}

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


% macros
% Random variables
\def\reta{{\textnormal{$\eta$}}}
\def\ra{{\textnormal{a}}}
\def\rb{{\textnormal{b}}}
\def\rc{{\textnormal{c}}}
\def\rd{{\textnormal{d}}}
\def\re{{\textnormal{e}}}
\def\rf{{\textnormal{f}}}
\def\rg{{\textnormal{g}}}
\def\rh{{\textnormal{h}}}
\def\ri{{\textnormal{i}}}
\def\rj{{\textnormal{j}}}
\def\rk{{\textnormal{k}}}
\def\rl{{\textnormal{l}}}
\def\rn{{\textnormal{n}}}
\def\ro{{\textnormal{o}}}
\def\rp{{\textnormal{p}}}
\def\rq{{\textnormal{q}}}
\def\rr{{\textnormal{r}}}
\def\rs{{\textnormal{s}}}
\def\rt{{\textnormal{t}}}
\def\ru{{\textnormal{u}}}
\def\rv{{\textnormal{v}}}
\def\rw{{\textnormal{w}}}
\def\rx{{\textnormal{x}}}
\def\ry{{\textnormal{y}}}
\def\rz{{\textnormal{z}}}

% Vectors
\def\vzero{{\bm{0}}}
\def\vone{{\bm{1}}}
\def\vmu{{\bm{\mu}}}
\def\vtheta{{\bm{\theta}}}
\def\va{{\bm{a}}}
\def\vb{{\bm{b}}}
\def\vc{{\bm{c}}}
\def\vd{{\bm{d}}}
\def\ve{{\bm{e}}}
\def\vf{{\bm{f}}}
\def\vg{{\bm{g}}}
\def\vh{{\bm{h}}}
\def\vi{{\bm{i}}}
\def\vj{{\bm{j}}}
\def\vk{{\bm{k}}}
\def\vl{{\bm{l}}}
\def\vm{{\bm{m}}}
\def\vn{{\bm{n}}}
\def\vo{{\bm{o}}}
\def\vp{{\bm{p}}}
\def\vq{{\bm{q}}}
\def\vr{{\bm{r}}}
\def\vs{{\bm{s}}}
\def\vt{{\bm{t}}}
\def\vu{{\bm{u}}}
\def\vv{{\bm{v}}}
\def\vw{{\bm{w}}}
\def\vx{{\bm{x}}}
\def\vy{{\bm{y}}}
\def\vz{{\bm{z}}}

% Random vectors
\def\rva{{\mathbf{a}}}
\def\rvb{{\mathbf{b}}}
\def\rvc{{\mathbf{c}}}
\def\rvd{{\mathbf{d}}}
\def\rve{{\mathbf{e}}}
\def\rvf{{\mathbf{f}}}
\def\rvg{{\mathbf{g}}}
\def\rvh{{\mathbf{h}}}
\def\rvi{{\mathbf{i}}}
\def\rvj{{\mathbf{j}}}
\def\rvk{{\mathbf{k}}}
\def\rvl{{\mathbf{l}}}
\def\rvm{{\mathbf{m}}}
\def\rvn{{\mathbf{n}}}
\def\rvo{{\mathbf{o}}}
\def\rvp{{\mathbf{p}}}
\def\rvq{{\mathbf{q}}}
\def\rvr{{\mathbf{r}}}
\def\rvs{{\mathbf{s}}}
\def\rvt{{\mathbf{t}}}
\def\rvu{{\mathbf{u}}}
\def\rvv{{\mathbf{v}}}
\def\rvw{{\mathbf{w}}}
\def\rvx{{\mathbf{x}}}
\def\rvy{{\mathbf{y}}}
\def\rvz{{\mathbf{z}}}

% Matrix
\def\mA{{\bm{A}}}
\def\mB{{\bm{B}}}
\def\mC{{\bm{C}}}
\def\mD{{\bm{D}}}
\def\mE{{\bm{E}}}
\def\mF{{\bm{F}}}
\def\mG{{\bm{G}}}
\def\mH{{\bm{H}}}
\def\mI{{\bm{I}}}
\def\mJ{{\bm{J}}}
\def\mK{{\bm{K}}}
\def\mL{{\bm{L}}}
\def\mM{{\bm{M}}}
\def\mN{{\bm{N}}}
\def\mO{{\bm{O}}}
\def\mP{{\bm{P}}}
\def\mQ{{\bm{Q}}}
\def\mR{{\bm{R}}}
\def\mS{{\bm{S}}}
\def\mT{{\bm{T}}}
\def\mU{{\bm{U}}}
\def\mV{{\bm{V}}}
\def\mW{{\bm{W}}}
\def\mX{{\bm{X}}}
\def\mY{{\bm{Y}}}
\def\mZ{{\bm{Z}}}

% Mathcal
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cD{{\mathcal{D}}}
\def\cE{{\mathcal{E}}}
\def\cF{{\mathcal{F}}}
\def\cG{{\mathcal{G}}}
\def\cH{{\mathcal{H}}}
\def\cI{{\mathcal{I}}}
\def\cJ{{\mathcal{J}}}
\def\cK{{\mathcal{K}}}
\def\cL{{\mathcal{L}}}
\def\cM{{\mathcal{M}}}
\def\cN{{\mathcal{N}}}
\def\cO{{\mathcal{O}}}
\def\cP{{\mathcal{P}}}
\def\cQ{{\mathcal{Q}}}
\def\cR{{\mathcal{R}}}
\def\cS{{\mathcal{S}}}
\def\cT{{\mathcal{T}}}
\def\cU{{\mathcal{U}}}
\def\cV{{\mathcal{V}}}
\def\cW{{\mathcal{W}}}
\def\cX{{\mathcal{X}}}
\def\cY{{\mathcal{Y}}}
\def\cZ{{\mathcal{Z}}}

% mathbb
\def\bA{{\mathbb{A}}}
\def\bB{{\mathbb{B}}}
\def\bC{{\mathbb{C}}}
\def\bD{{\mathbb{D}}}
\def\bE{{\mathbb{E}}}
\def\bF{{\mathbb{F}}}
\def\bG{{\mathbb{G}}}
\def\bH{{\mathbb{H}}}
\def\bI{{\mathbb{I}}}
\def\bJ{{\mathbb{J}}}
\def\bK{{\mathbb{K}}}
\def\bL{{\mathbb{L}}}
\def\bM{{\mathbb{M}}}
\def\bN{{\mathbb{N}}}
\def\bO{{\mathbb{O}}}
\def\bP{{\mathbb{P}}}
\def\bQ{{\mathbb{Q}}}
\def\bR{{\mathbb{R}}}
\def\bS{{\mathbb{S}}}
\def\bT{{\mathbb{T}}}
\def\bU{{\mathbb{U}}}
\def\bV{{\mathbb{V}}}
\def\bW{{\mathbb{W}}}
\def\bX{{\mathbb{X}}}
\def\bY{{\mathbb{Y}}}
\def\bZ{{\mathbb{Z}}}

% Random matrices
\def\rmA{{\mathbf{A}}}
\def\rmB{{\mathbf{B}}}
\def\rmC{{\mathbf{C}}}
\def\rmD{{\mathbf{D}}}
\def\rmE{{\mathbf{E}}}
\def\rmF{{\mathbf{F}}}
\def\rmG{{\mathbf{G}}}
\def\rmH{{\mathbf{H}}}
\def\rmI{{\mathbf{I}}}
\def\rmJ{{\mathbf{J}}}
\def\rmK{{\mathbf{K}}}
\def\rmL{{\mathbf{L}}}
\def\rmM{{\mathbf{M}}}
\def\rmN{{\mathbf{N}}}
\def\rmO{{\mathbf{O}}}
\def\rmP{{\mathbf{P}}}
\def\rmQ{{\mathbf{Q}}}
\def\rmR{{\mathbf{R}}}
\def\rmS{{\mathbf{S}}}
\def\rmT{{\mathbf{T}}}
\def\rmU{{\mathbf{U}}}
\def\rmV{{\mathbf{V}}}
\def\rmW{{\mathbf{W}}}
\def\rmX{{\mathbf{X}}}
\def\rmY{{\mathbf{Y}}}
\def\rmZ{{\mathbf{Z}}}

\DeclareRobustCommand\onedot{}
\def\ie{\emph{i.e}\onedot}
\def\wrt{\emph{w.r.t }\onedot}
\def\eg{\emph{e.g}\onedot}
\def\ow{\emph{o.w}\onedot}
\newcommand{\st}{\mathrm{s.t\onedot}}
\def\iid{\emph{i.i.d}\onedot}
\def\wp{\emph{w.p.}\onedot}

\def\bnull{{\boldsymbol{0}}}
\def\bth{\bm{\theta}}
\def\lse{\widehat{\bm{\theta}}^\mathrm{LS}}
\def\tth{\bth^\star}

\def\eps{\varepsilon}
\def\veps{\bm{\varepsilon}}

\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\innerproduct}[2]{\langle #1, #2\rangle}

\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}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[]{Example}
\newtheorem{exercise}[theorem]{Exercise}

% 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{20 --- October 22, 2021}{Fall 2021}{Sebastien Roch, UW-Madison}{Shuqi Yu}

\section{Overview}
In the last lecture, we showed the bound on approximate isometries. In this lecture, we focus on estimating the covariance matrix from finite sample, which has a well-known application in the principal components analysis (PCA). And the material follows from section 4.7, 5.2, 9.2 in~\cite{vershynin}.

\section{Covariance estimation}
Let $\rmX\in\bR^d$ be a random vector with mean zero, the covariance matrix is $\mathbf \Sigma:=\mathbb E\mathbf X\mathbf X^\top$, $\ie$ $ \mathbf \Sigma_{ij}=\mathbb E\mathbf X_i\mathbf X_j$. We first show the following property of covariance matrix. For $\mathbf u\in\bS^{d-1}$, $\mathbb E\langle\mathbf X,\mathbf u\rangle=0$ as $\mathbf X$ is mean zero, then
\begin{equation}
    Var\langle\rmX,\rvu\rangle=\bE\left(\langle\rmX,\rvu\rangle^2\right)=\bE\rvu^\top\rmX\rmX^\top\rvu=\rvu^\top\bE(\rmX\rmX^\top)\rvu=\rvu^\top\mathbf\Sigma\rvu\label{eqn:inner_prod}
\end{equation}

Suppose there are $n$ $\iid$ samples $\mathbf X^{(1)},\cdots,\mathbf X^{(n)}\sim \mathbf X$, the sample covariance is defined as
\begin{equation}
 \hat{\mathbf\Sigma}_n=\frac{1}{n}\sum_{i=1}^n \rmX^{(i)}\rmX^{(i)\top}  
\end{equation}
Put differently, let $\rmA\in\bR^{n\times d}$ have row $i$ is $\rmX^{(i)}$, then $\hat{\mathbf\Sigma}_n=\frac{\rmA^\top\rmA}{n}$.
\subsection{Corvariance estimation for high dimensional distributions}

Recall the following theorem we proved last time for sub-gaussian isotropic random vectors.
\begin{theorem}[Theorem 4.6.1 in \cite{vershynin}]\label{thm1}
Let $\rmA\in\bR^{n\times d}$ have rows that are independent, mean zero, sub-gaussian isotropic random vectors with $K=\max_{i=1,\cdots n}\norm{\rmA_{i\cdot}}_{\psi_2}$, then with probability $1-2e^{-u}$,
\begin{equation}
    \norm{\frac{1}{n}\rmA^\top\rmA-\rmI_d}_2\leq CK^2\left(\sqrt{\frac{d+u}{n}}+\frac{d+u}{n}\right)
\end{equation}
\end{theorem}
\begin{remark}
Since rows of $\rmA$ are isotropic whose covariance are $\rmI_d$, $\norm{\frac{1}{n}\rmA^\top\rmA-\rmI_d}_2=\norm{\hat{\mathbf\Sigma}_n-\mathbf\Sigma}_2$.
\end{remark}
Next, we extend to the general sub-gaussian setting.
\begin{theorem}[Theorem 4.7.1 in~\cite{vershynin} ]
    Let $\rmX$ be a sub-gaussian random vector in $\bR^d$ with invertible covariance matrix $\mathbf\Sigma$ $\st$
    \begin{equation}
        \norm{\langle\rmX,\rvu\rangle}_{\psi_2}\leq K\sqrt{\bE(\langle\rmX,\rvu\rangle^2)}\qquad\text{ for all  }\rvu\in\bS^{d-1}
    \end{equation}
    with probability $1-2e^{-u}$, then 
    \begin{equation}
        \norm{\hat{\mathbf\Sigma}_n-\mathbf\Sigma}_2\leq CK^2\norm{\mathbf\Sigma}_2\left(\sqrt{\frac{d+u}{n}}+\frac{d+u}{n}\right).
    \end{equation}
\end{theorem}
\begin{remark}
$\bE(\langle\rmX,\rvu\rangle^2)=\langle\rvu,\mathbf\Sigma\rvu\rangle$ by~\eqref{eqn:inner_prod}.
\end{remark}
\begin{proof}
We first bring the random vectors $\rmX_1,\cdots,\rmX_n$ to the isotropic position. By slides(\url{https://people.math.wisc.edu/~roch/hdps/roch-hdps-slides12.pdf}) or Exercise 3.2.2 in~\cite{vershynin}, there exist isotropic mean zero vectors $\rmZ^{(1)},\cdots,\rmZ^{(n)}$ $\st$ 
\begin{equation}
    \rmX^{(i)}=\mathbf\Sigma^{1/2}\rmZ^{(i)}, \text{ for all }i=1,\cdots,n.
\end{equation}
We proved previously, $\norm{\rmZ^{(i)}}_{\psi_2}\leq K$. Let $\hat\rmR_n:=\frac{1}{n}\sum_{i=1}^n\rmZ^{(i)}\rmZ^{(i)\top}-\rmI_d$, then
\begin{equation}
     \norm{\hat{\mathbf\Sigma}_n-\mathbf\Sigma}_2=\norm{\mathbf\Sigma^{1/2}\hat\rmR_n\mathbf\Sigma^{1/2}}_2\leq \norm{\hat\rmR_n}_2\norm{\mathbf\Sigma}_2
\end{equation}
where we apply the property $\norm{\rmA\rmB}_2\leq \norm{\rmA}_2\norm{\rmB}_2$ and $\norm{\rmA^{1/2}}_2^2=\left(\sqrt{\sigma_{max}(A)}\right)^2=\norm{\rmA}_2$.

Consider the $n\times d$ random matrix $\rmA$ whose rows are $\rmZ^{(i)}$, then 
\begin{equation}
   \frac{1}{n}\rmA^\top\rmA-\rmI_d=\frac{1}{n}\sum_{i=1}^n\rmZ^{(i)}\rmZ^{(i)\top}-\rmI_d=\hat\rmR_n
\end{equation}
Then we conclude by applying Theorem~\ref{thm1} for $\rmA$.
\end{proof}

\subsection{Covariance estimation for lower-dimensional distributions}
We found that the covariance matrix $\mathbf\Sigma$ of an $n$-dimensional distribution can be estimated from $m=O(n)$ sample points for sub-gaussian distributions. For approximately lower-dimensional distributions,  smaller sample can be sufficient for covariance estimation, which means that the distribution tends to concentrate near a small subspace.
\begin{theorem}[Theorem 9.2.4 in~\cite{vershynin}]
    Let $\rmX$ be a sub-gaussian random vector in $\bR^d$ with invertible covariance matrix $\mathbf\Sigma$ $\st$
    \begin{equation}
        \norm{\langle\rmX,\rvu\rangle}_{\psi_2}\leq K\sqrt{\bE(\langle\rmX,\rvu\rangle^2)}\qquad\text{ for all  }\rvu\in\bS^{d-1}
    \end{equation}
    with probability $1-2e^{-u}$, then 
    \begin{equation}
        \norm{\hat{\mathbf\Sigma}_n-\mathbf\Sigma}_2\leq CK^4\norm{\mathbf\Sigma}_2\left(\sqrt{\frac{r+u}{n}}+\frac{r+u}{n}\right).
    \end{equation} 
   where $r=tr(\mathbf\Sigma)/\norm{\mathbf\Sigma}_2$. 
\end{theorem}

\subsection{General covariance estimation}
Next, we state a more general version of covariance estimation by applying matrix Berstein inequality, see the slides(\url{https://people.math.wisc.edu/~roch/hdps/roch-hdps-slides20.pdf}) for more details.

\begin{theorem}[Theorem 5.6.1 in~\cite{vershynin}]
Let $\rmX$ be a random vector in $\bR^d$, $d\geq 2$. Assume that for some $K\geq 1$,
\begin{equation}
    \norm{\rmX}_2\leq K\left(\bE\norm{\rmX}_2^2\right)^{1/2} \qquad\text{almost surely.}
\end{equation}
Then, with probability $1-2e^{-u}$, we have
\begin{equation}
    \norm{\hat{\mathbf\Sigma}_n-\mathbf\Sigma}_2\leq C\norm{\mathbf\Sigma}_2\left(\sqrt{\frac{K^2r(\log d+u)}{n}}+\frac{K^2r(\log d+u)}{n}\right) 
\end{equation}
where $r=tr(\mathbf\Sigma)/\norm{\mathbf\Sigma}_2\leq n$.
\end{theorem}

%\bibliography{mybib}
\bibliographystyle{alpha}

\begin{thebibliography}{77}

\bibitem{durrett}
Rick Durrett,
\emph{Probability—theory and examples (fifth edition)},
Cambridge University Press, 2019.


\bibitem{Ramon van Handel}
Ramon van Handel, 
\emph{APC 550: Probability in High Dimension},
Lecture Notes, 2016.
\url{https://web.math.princeton.edu/~rvan/APC550.pdf}%


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

\end{thebibliography}



\end{document}