Error bound for MonteCarlo estimate of elements in Gram-Matrix

Question

Suppose I have a $n\times n$-symmetric positive-definite matrix $A$ with elements:
\begin{align} [A]_{ij}=\int_{\Omega}f_i(x)f_j(x) \, dx, \quad i,j=1,\ldots,n \end{align} where $\Omega\subset \mathbb{R}^d$ is a bounded domain with $\int_\Omega dx=1$ and $f_i:\Omega\to \mathbb{R}$ are continuous functions.

Suppose now that we sample $N$ points $(x_k)_{k=1}^N$ in $\Omega$ uniformly and create the matrix $A_N$ with elements $$ [A_N]_{ij}=\frac{1}{N}\sum_{k=1}^N f_i(x_k)f_j(x_k) $$

Thus, each element in $A_N$ is a Monte-Carlo estimate of the corresponding element in $A$.

Question: I would like to show that, given a vector $v\in \mathbb{R}^n$, we have that \begin{align} |v^T(A^{-1}-A_N^{-1})v|\leq C v^TA^{-1}v, \quad \text{$C$ a constant prefferably independent of $n,N, v$} \end{align} with at least probability $p$ which depends on $N$ and possibly $n$.

I want an expression for the probability $p$, and if possible, the expression would be of the form $p=1-\exp(-cN)$.

I would appreciate any thoughts/references relevant to this kind of problem. Thanks!

Answer 1

$\newcommand{\Om}{\Omega}\newcommand{\R}{\mathbb R}\newcommand{\de}{\delta}\newcommand{\De}{\Delta}$The question makes sense only if $A^{-1}$ exists, which will be assumed in what follows. For $x\in\Om$, let $f(x):=[f_1(x),\ldots,f_n(x)]^\top$, so that $f$ is a random vector in $\R^n$ defined on the probability space $(\Om,P)$, where $P$ is the Lebesgue measure over $\Om$, and $Eff^\top=A=EA_N$. We will assume that the vector function $f$ can be continuously extended to the closure of $\Om$.

Let $g:=A^{-1/2}f$. Then $Egg^\top=I_n$, where $I_n$ is the $n\times n$ identity matrix, and \begin{equation*} A_N=A^{1/2}B_N A^{1/2}, \end{equation*} where \begin{equation*} B_N:=\frac1N\,\sum_{k=1}^N X_k \tag{0}\label{0} \end{equation*} and $X_k$ is the $n\times n$ random matrix with entries $(X_k)_{ij}=g_i(x_k)g_j(x_k)$ for $i,j=1,\dots,n$.

So, considering $w:=A^{-1/2}v$, rewrite your condition $|v^T(A^{-1}-A_N^{-1})v|\leq C v^TA^{-1}v$ as \begin{equation*} \|B_N^{-1}-I_n\|\le C, \tag{10}\label{10} \end{equation*} where $\|\cdot\|$ is the spectral matrix norm. Letting \begin{equation*} \De_N:=B_N-I_n, \end{equation*} we have $B_N^{-1}-I_n=-B_N^{-1}\De_N$ and hence $\|B_N^{-1}-I_n\|\le\|B_N^{-1}\|\,\|\De_N\|$. Moreover, if $\|\De_N\|<1$, then \begin{equation*} B_N^{-1}=(I_n+\De_N)^{-1}=I_n-\De_N+\De_N^2-\cdots \end{equation*} and hence \begin{equation*} \|B_N^{-1}\|\le1+\|\De_N\|+\|\De_N\|^2+\cdots=\frac1{1-\|\De_N\|}. \end{equation*} So, $\|B_N^{-1}-I_n\|\le\|B_N^{-1}\|\,\|\De_N\|\le\frac{\|\De_N\|}{1-\|\De_N\|}$, and therefore \eqref{10} is implied by \begin{equation*} \|\De_N\|\le\de:=\frac C{1+C}. \tag{20}\label{20} \end{equation*}

It remains to show that inequality \eqref{20} happens "with high probability". Toward this end, note that $X_1,\dots,X_N$ are i.i.d. random matrices such that $EX_k=I_n$ and $\|X_k-I_n\|\le M$ for some real $M>0$ (because of the assumption that $f$ can be continuously extended to the closure of $\Om$). So, by Theorem 3.4 with $a=M$, $b=M\sqrt{N}$, $D=1$, and $r=N\de$, we have \begin{equation} P(\|\De_N\|\ge\de) =P\Big(\Big\|\frac1N\,\sum_{k=1}^N (X_k-EX_k)\Big\|\ge\de\Big) \le2\exp(-N\psi(\de/M)), \end{equation} where $\psi(u):=-u+(u+1)\ln(u+1)>0$ for real $u>0$ (and $\psi(u)\sim u^2/2$ as $u\to0$).

Thus, inequality \eqref{20} does happen with "high probability" $\ge1-2\exp(-N\psi(\de/M))$ (which does not directly depend on $n$ or $d$). $\quad\Box$.