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.
2026-05-05 21:54:00.1778018040
A confusion about big Oh notation
53 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.