3
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean, precisely, by " high probability" here? $\endgroup$ Commented Oct 9, 2024 at 12:42
  • $\begingroup$ Hi! Sorry about being to vague. But I would like to show that the given bound holds with at least a probability $p$, where the expression for $p$ depends on $N$ and possibly $n$. A desirable expression would be something like $p\sim 1-exp(-cN)$ so that $p$ goes to $0$ fast with N. I don't know if that's possible to show, but Im interested in that kind of results. $\endgroup$ Commented Oct 9, 2024 at 12:59

1 Answer 1

Reset to default
2
$\begingroup$

$\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$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ thanks for your very good explanation, I really appreciate it :) I understand your derivation, until you state that $\|X_k-I_n\|\leq M$ follows by the assumption that all $f_i(x)$ can be extended to be continuous on the closure of $\Omega$, how can that be shown? Also, I guess the constant $M$ will depend on the dimension $n$? Can one say anything about this dependence? After some thoughts, Im after some expression like $1-exp(- c N/n)$ for the probability. So by making $N$ much larger than $n$ we make the probability close to 1. Thanks! $\endgroup$ Commented Oct 10, 2024 at 18:57
  • $\begingroup$ @Erling : Since the vector function $f$ can be continuously extended to the closure of the bounded domain $\Omega$, we have $\|f\|:=\sup_{x\in\Omega}|f(x)|\le b$ for some real $b>0$; here, $|\cdot|$ is the Euclidean norm on $\Bbb R^n$. Since $g=A^{-1/2}f$ and $X_k=g(x_k)g(x_k)^\top$, we have $\|X_k\|\le\|g\|^2\le(\|A^{-1/2}\|\,\|f\|)^2\le\|A^{-1/2}\|^2\,b^2=:M_0<\infty$, where $\|A^{-1/2}\|$ is the spectral norm of the matrix $A^{-1/2}$. So, $\|X_k-I_n\|\le M:=M_0+1=\|A^{-1/2}\|^2\,b^2+1$. $\endgroup$ Commented Oct 10, 2024 at 19:45
  • $\begingroup$ Previous comment continued: We see that, naturally, $M$ will be large if $A$ is close to being singular and/or if $|f_i|$'s may take large values. $\endgroup$ Commented Oct 10, 2024 at 19:45
  • $\begingroup$ @Erling : Do you have a further response to my answer and comment? $\endgroup$ Commented Oct 11, 2024 at 13:22
  • $\begingroup$ thanks for your answer. I know that the functions $f_i$ are bounded so thats not a problem. However, Im still wondering the dependency of $n$. Its seems reasonable to get some expression like $N/n$ in the exponent. $\endgroup$ Commented Oct 11, 2024 at 17:16

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.