Note that the time it takes to obtain the first sample (i.e., the
preprocessing cost) is \(o(d^2)\) ,
meaning that we do not actually have to read the entire matrix
\(\) . Moreover, the cost of producing repeated samples only depends
on the sample size \(k\) , which is typically small. The key idea behind
the algorithm of [1]} is to produce a
larger sample of indices drawn i.i.d. proportionally to the marginal probabilities
of \(()\) . For any \(i\in [d]\) , the marginal probability of \(i\)  in
\(\hat{S} \sim (\frac{1}{\alpha })\)  is:

(iS) = [(+)-1]ii.

In the randomized linear algebra literature, this quantity is often
called the \(i\) th \(\alpha \) -ridge leverage score
[2]}, and sampling i.i.d. according to ridge
leverage scores is known to have strong
guarantees in approximating p.s.d. matrices.
