
The idea of the proof is to rely on concentration inequalities proved in [1]} to give condition to detect linear independence.
This algorithm has been further studied by authors and result has been improved in a followup work from the authors of the aforementioned paper.
In particular, in the following paper [2]} authors show that, it is enough to pick \(\Omega \)  in a way that its size to be lower bounded by \(32 r \log {r/\epsilon }\) .
