1
$\begingroup$

I have $N$ i.i.d random vectors $\{X_k\}_{k=1}^N$ in $\mathbb{R}^n$ where each entry is bounded and positive. I construct a matrix $M_N$ as \begin{align} M_N=\frac{1}{N}\sum_{k=1}^NX_kX_k^T \end{align} i.e, an estimate of the covariance matrix. Let's define \begin{align} M=\mathbb{E}\bigg[X_kX_k^T \bigg] \end{align} and hence $M=\mathbb{E}[M_N ]$. $M$ is symmetric and I know that $M$ is positive definite.

The problem: I have a particular vector $v\in \mathbb{R}^n$ and want to show that, with high probability, there is a constant $C$ (independent of $N,n$) such that \begin{align} v^T(M_N)^{-1}v\leq C v^TM^{-1}v \end{align} and the probability will of course depend on $N,n$. I want to know if this is possible with the assumption that $N=\kappa n$ where $\kappa>1$ is a constant.

I can proceed in this way: \begin{align} v^T(M_N)^{-1}v=v^T((M_N)^{-1}-M^{-1})v+v^TM^{-1}v, \end{align} so if I can show that $v^T((M_N)^{-1}-M^{-1})v\leq C v^TM^{-1}v$ with high probability the result follows.

I also know that $v^TM^{-1}v\lesssim n$, if that can be of any help. The problem is the inverses in the expressions. Maybe it is possible to apply some sort of concentration inequality.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The constant $C$ should depend on the distribution of $X_1$, which in turn depends on $n$. So, $C$ should depend on $n$. $\endgroup$ Commented Jun 24 at 0:09
  • $\begingroup$ Ok! Is it possible to derive such a constant and estimate the probability? $\endgroup$ Commented Jun 24 at 10:36
  • $\begingroup$ Do you have a response to the answer below? $\endgroup$ Commented Jul 1 at 19:13

1 Answer 1

Reset to default
2
$\begingroup$

$\newcommand{\ep}{\varepsilon}\newcommand{\de}{\delta}$Yes, this is possible -- however,

  • $C$ must depend on $W:=\|M^{-1}\|$, where $\|\cdot\|$ is the spectral matrix norm; if we cannot control $\|M^{-1}\|$, then, because of random fluctuations, we certainly cannot control $\|M_N^{-1}\|$;

  • we have also to impose conditions on how big $\|X_1\|$ can be.

The proof is based on Tropp's state-of-the-art Bennett-type inequality (see e.g. inequality (5)), which implies the following: \begin{equation*} P(\|M_N-M\|<\ep)\ge1-2\de \tag{10}\label{10} \end{equation*} where $\de\in(0,n)$, \begin{equation*} \ep:=\frac B3\,h+\sqrt{2V h},\quad h:=\frac{\ln(n/\de)}N, \tag{20}\label{20} \end{equation*} assuming that \begin{equation*} \|X_1\|\le B,\quad E\|X_1\|^2\le V. \end{equation*}

Next, from the identity $A^{-1}-B^{-1}=B^{-1}(B-A)A^{-1}$ for nonsingular $n\times n$ matrices $A$ and $B$, we get \begin{equation*} \|M_N^{-1}-M^{-1}\|\le \|M_N^{-1}\|\,\|M_N-M\| \, \|M^{-1}\| \le\frac{W^2}{1-\ep W}\,\|M_N-M\| \end{equation*} provided that \begin{equation*} \ep<1/W; \tag{30}\label{30} \end{equation*} it will be henceforth assumed that $h$ is small enough so that, in view of \eqref{20}, \eqref{30} holds. Then \begin{equation*} P(\|M_N^{-1}-M^{-1}\|<\ep_1)\ge1-2\de, \tag{40}\label{40} \end{equation*} where \begin{equation*} \ep_1:=\frac{W^2}{1-\ep W}\,\ep. \end{equation*}

So, with probability $\ge1-2\de$ we have
\begin{equation*} v^T M_N^{-1}v\le v^T M^{-1}v+\ep_1|v|^2 \le Cv^T M^{-1}v, \end{equation*} where $|\cdot|$ is the Euclidean norm and \begin{equation*} C:=1+\|M\|\ep_1 =1+\|M\|\,\frac{W^2}{1-\ep W}\,\ep. \end{equation*} It remains to note that, by \eqref{20}, \begin{equation} \de=n e^{-hN}\to0 \end{equation} if $h\asymp1$ and $N=\kappa n\to\infty$ for a real constant $\kappa>0$.

More generally, one can let $h$ vary so that $h\ge b\frac{\ln N}N$ for a constant real $b>1$ and also allow $B$ and $V$ to grow so that $\ep$, as defined in \eqref{20}, remain bounded and small enough for \eqref{30} to hold. For such a choice of $h$ to be possible, it will be enough that $B$ and $V$ grow slower than $n/\ln n$ whereas $W=O(1)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.