[rwitten]

If you're interested in lower bounds or tighter upper bounds, you can find the latest here:

http://link.springer.com/article/10.1007%2Fs00453-014-9891-7... http://statweb.stanford.edu/~candes/papers/RandomizedNLA.pdf