I take a special case in http://cs-www.cs.yale.edu/homes/kannan/Papers/matrixmult.pdf as an example. Give a matrix $A\in R^{d\times n}$ with $n$ columns $\{a_i\in R^d\}_{i=1}^n$, we can randomly sample $m$ columns from $A$ with replacement to form a matrix $B\in R^{d\times m}$ such that $BB^T\approx AA^T$. The sampling probability is based on the relative $l_2$ norm of $a_i$, i.e., $\frac{\|a_i\|_2^2}{\sum_{i=1}^n\|a_i\|_2^2}$.
However, some subsequent paper claim that the above algorithm is two-pass because it requires the first pass on data to calculate the sampling probability, and the second pass to sample on the data.
Based on weighted random sampling using Reservoir https://en.wikipedia.org/wiki/Reservoir_sampling#Weighted_Random_Sampling_using_Reservoir, it seems that the above matrix approximation algorithm is one pass, that is we keep the first $m$ columns of $A$ and obtain the $\{\|a_i\|_2^2\}_{i=1}^m$, and then re-sample the $m$ columns when the $(m+1)$-th column comes. Repeating such procedure until processing all columns of $A$.
Can someone help to ensure my opinion, and give some suggestion? Thanks.