2

I have seen in a paper that, if $A=\mathcal{O}(p^2)$ and $B=\mathcal{O}(p)$ then,

how can we say that, $A^{-1/2}B$ is diverging?

The way I thought is,

if $A = \mathcal{O}(p^2)$, then $A^{-1/2}$ = $\mathcal{O}(p^{-1})$, then $A^{-1/2}B$ = $\mathcal{O}(p^{-1})\mathcal{O}(p) = \mathcal{O}(1)$. If so, we can't say it is diverging?

Any help is greatly appreciated.

Rob Hyndman
  • 219
shani
  • 779
  • 1
  • 5
  • 12
  • Can you refer the paper you have seen? – Marc Jan 14 '14 at 13:40
  • 1
    Taking $A=p^2$ and $B=p$ gives a counterexample. Perhaps it was a small o? – Giulio Belletti Jan 14 '14 at 13:47
  • @ Marc: The paper is Large covariance estimation by thresholding principal orthogonal complements. In that it is an example given in page 13. – shani Jan 14 '14 at 13:47
  • @ Giulio: It is not small o. As in the paper it is O(p) – shani Jan 14 '14 at 13:51
  • 2
    Note that if $A\in \mathcal{O}(p^2)$, then you generally don't have $A^{-1/2} \in \mathcal{O}(p^{-1})$, but $A^{-1/2} \in \Omega(p^{-1})$. Now, the product of functions from $\Omega(g)$ and $\mathcal{O}(h)$ can be pretty much anything. – Daniel Fischer Jan 14 '14 at 14:07
  • @ Daniel: What is meant by $\Omega$ symbol? – shani Jan 14 '14 at 14:11
  • $f\in \Omega(g)$ if there exists a $c > 0$ with $\lvert f(x)\rvert \geqslant c\cdot g(x)$ for all large enough $x$ (or $x$ close enough to $x_0$ if you're looking at the asymptotics for $x\to x_0$). – Daniel Fischer Jan 14 '14 at 14:22
  • $f=\Omega(g)$ means that $f$ is bounded below by $g$. – Marc Jan 14 '14 at 14:23
  • Oh...then can we say if $B=O(p)$ and $A=\Omega(p^{-1})$, $AB = O(p)\Omega(p^{-1})$ is diverging as A is bounded below. – shani Jan 14 '14 at 14:31
  • @Daniel: Can you give any reference to that result: if $A \in O(p^{2})$, then $A^{−1/2} \in \Omega(p^{−1})$? – shani Jan 14 '14 at 15:27
  • $\lvert A\rvert \leqslant K\cdot p^2 \Rightarrow \lvert A\rvert^{1/2} \leqslant \sqrt{K}\cdot p \Rightarrow \dfrac{1}{\sqrt{K}\cdot p} \leqslant \lvert A\rvert^{-1/2}$. – Daniel Fischer Jan 14 '14 at 15:32

2 Answers2

1

Thanks for the reference. Well, they state that if $A = \mathcal{O}(p^2)$ then $\mathcal{O}(p\cdot A^{-1/2})$ can diverge. Take a look at Grandi's serie which is $1-1+1-1\ldots$ which is in $\mathcal{O}(1)$ but does diverge.

Marc
  • 755
  • Yes, I get your point. But how can we show this mathematically? In that paper, how can we say it is diverging? Do you have any idea? – shani Jan 14 '14 at 14:22
  • They are not saying that it is diverging. Only that it is possible. I think they want to say that even if you have a good estimator for the first eigenvector does not mean that the matrix is converging. Or else, we just cannot say anything about the convergence of $\hat \Sigma$ – Marc Jan 14 '14 at 14:26
  • Hmmm..yes can be. If $f(x) = x^2 + 5x + 8$ is it wrong to say $ f(x) = O(x^2)$? – shani Jan 14 '14 at 14:37
  • 1
    No, this is correct. $f(x)$ is in $\mathcal{O}(x^2)$. But $f(x)$ in $\mathcal{O}(1)$ does not imply any convergence (nor divergence) of $f$. – Marc Jan 14 '14 at 14:42
  • In this case $f(x) = O(x^2)$, since for $x > 1$ we have $x^2 > x$, so this leads to $|f(x)| \le |x^2| + 5|x^2| + 8|x^2| = 14|x^2|$ and thus $f(x) = O(x^2)$. – Joel Jan 14 '14 at 14:43
0

We say that $f = O(g)$ (as $x \to \infty$) if there exists a constant $M > 0$ and a point $x_0 \in \mathbb{R}$ such that $$|f(x)| \le M | g(x) |$$ for all $x > x_0$. This just gives us upper bounds. Take for instance $A(p) = 1$ (a constant function) and $B(p) = 1/p$, then trivially we have $A = O(p^2)$ and $B = O(p)$. However $A^{-1/2} B = 1/p$, and converges to 0 as $p \to \infty$.

Joel
  • 16,256
  • @ Joel: If $B(p) = 1/p$, then isn't it implies $ B=O(p^{-1})$ rather than $O(p)$? – shani Jan 14 '14 at 14:14
  • Big oh is simply a statement about upper bounds. If $B = p^{-1}$, then we know that for $p > 1$ we have $B = 1/p \le 1 |p|$. This means that $B = O(p)$. We also have $B = O(p^{-1})$ and $B = O(p^{2})$. – Joel Jan 14 '14 at 14:16