LetB ∈ R m×d be the matrix returned by the algorithm in Figure 1.
then with probability at least 0.7, the selected rows are not arbitrarily worse than the best rank-m approximation of A (given by SVD) with high probability.