As far as I know, the statement $|T|\le C_M\cdot (\log N)^{-1}.|\Omega|,\ (C_M>0)$ should imply that $$|\Omega|=\mathcal{\Omega}(|T|\log N)$$ but this seminal paper by Candes et al. says in the abstract that $|\Omega|=\mathcal{O}(|T|\log N)$. I am really confused because it seems that my understanding is correct, but then how could such a seminal paper commit such a mistake, which makes me dubious about the notation used. Please help to alleviate this confusion.
Asked
Active
Viewed 52 times
1 Answers
0
I'm not an expert in signal processing, but I don't think you're misunderstanding the notation. The first inequality says that any $\Omega$ of size $\geq C_M^{-1} |T| \cdot \mathrm{log} N$ suffices. The big-O notation used later is pointing out the fact that we can choose $|\Omega|$ to be approximately equal to this expression, and thus big-O of it. It's like saying "if we choose at least 90 things, then X happens", and then celebrating the fact that fewer than 100 things suffice.
Ravi Fernando
- 7,284
-
But that's not the correct use of that notation, is it? – Samrat Mukhopadhyay Nov 09 '15 at 06:30
-
They are being a bit imprecise when they say "almost every set of frequencies of size $O(|T| \cdot \mathrm{log} N)$"--perhaps it would be more correct to say "almost every set of frequencies of size $x$, where we can choose $x$ to be $O(|T| \cdot \mathrm{log} N)$". In context, the other meaning is unreasonable: for an extreme case, if $|\Omega| = 0$ (which certainly is $O(|T| \cdot \mathrm{log} N)$), then the statement couldn't possibly be correct. – Ravi Fernando Nov 09 '15 at 06:43
-
Exactly @Ravi Fernando, what you said is what I was thinking (and it makes sense). – Samrat Mukhopadhyay Nov 09 '15 at 07:15