A naive algorithm to calculate the statistical leverage scores is achieved by SVD or QR decomposition to obtain an orthogonal basis of a matrix, and we can compute the squared Euclidean norm of the rows of the basis matrix to gain the statistical leverage scores. The matrix coherence can be obtained by finding the largest statistical leverage scores. The total time complexity is \(O\left({\rm min}(mn^2,m^2n)\right)\) , which is extremely slow if \(m\)  and \(n\)  are large. Many fast algorithms have been developed for their approximations [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, to name just a few. Drineas et al. [1]} present a randomized Hadamard transform algorithm based on subsampling to compute relative-error approximations to statistical leverage scores in time qualitatively less than the time required to compute an orthogonal basis, and the proposed algorithm runs in \(O((mn + n^3){\rm log}\,m)\)  time, which is much faster than the naive algorithm for the case when \(m \gg n \gg 1\) . Recently, Sobczyk et al. [7]} propose a approach for estimating leverage scores, which bases on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms. The running time complexity is about \(O(nnz(A)+n^3)\) , where \(nnz(A)\)  is the number of non-zero entries of \(A\) .
