Timeline for Error bound for MonteCarlo estimate of elements in Gram-Matrix
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 12 at 19:38 | vote | accept | Jjj | ||
| Oct 11 at 21:04 | comment | added | Jjj | Yes I agree that you answered the question. But I dont agree that dividing $N$ by $n$ would be much worse. Now the $n$ dependency is hidden in $M$ and $M$ could scale like $n^s$ for some $s$, which would mean that we would get something like $N/n^{2s}$ in the exponent as $\psi (u)\sim u^{2}$ for small $u$. | |
| Oct 11 at 18:56 | comment | added | Iosif Pinelis | @Erling : Your question was "I want an expression for the probability $p$, and if possible, the expression would be of the form $p=1-\exp(-cN)$." Your $c$ was not specified anyhow. My answer gives you such a bound, even with a completely specified and natural $c$. Thus, your question has been completely answered. It was also explained that dividing $N$ by $n$ would only make the bound much worse. If you have further questions about your computer experiments or else, you can post them separately. | |
| Oct 11 at 18:43 | comment | added | Jjj | Yes I understand. Its more that I wonder how to obtain a dependency on $n$ in the constant $M$. When i run some computer experiments I observe that $\|\Delta_N\|<1$ only if $N>n$, (sufficiently larger) and this is what I want the estimated probability to reflect. Thats why I would like to get something like $N/n$ in the exponent. Now the $n$ dependency is hidden in $M$. So im curious about how to attack the problem om determine this dependency. | |
| Oct 11 at 18:41 | comment | added | Iosif Pinelis | @Erling : Another way to look at this: You wanted the "high probability" to be close to $1$ for large enough $N$. By dividing $N$ by $n$, you of course diminish the large-$N$ effect. | |
| Oct 11 at 17:28 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
added 3 characters in body
|
| Oct 11 at 17:25 | comment | added | Iosif Pinelis | @Erling : The bound obtained in my answer does not explicitly depend on $n$; it depends on $n$ only very indirectly, through the bound $b$ on $\|f\|$ and the measure $\|A^{-1/2}\|$ of the non-singularity of the matrix $A$. This is natural and desirable. However, if, for some reason, you want to replace $N$ in $1-2\exp(-N\psi(\delta/M))$ by $N/n$, you can certainly do it -- but then you will get a much worse lower bound $1-2\exp(-(N/n)\psi(\delta/M))$ on the "high probability" (e.g., think what will happen with the latter lower bound when $n\to\infty$). | |
| Oct 11 at 17:16 | comment | added | Jjj | 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. | |
| Oct 11 at 13:22 | comment | added | Iosif Pinelis | @Erling : Do you have a further response to my answer and comment? | |
| Oct 10 at 19:50 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
added 6 characters in body
|
| Oct 10 at 19:45 | comment | added | Iosif Pinelis | 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. | |
| Oct 10 at 19:45 | comment | added | Iosif Pinelis | @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$. | |
| Oct 10 at 18:57 | comment | added | Jjj | 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! | |
| Oct 9 at 15:44 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
added 52 characters in body
|
| Oct 9 at 15:35 | history | answered | Iosif Pinelis | CC BY-SA 4.0 |