Motivated by the work in Frieze et al. [1]} and Tang [2]}, in this paper we present a quantum-inspired classical algorithm to compute the statistical leverage scores under some natural sampling assumptions. More specifically, based on the subsampling method in [1]}, we obtain the small submatrix \(W \in \mathbb {R}^{p \times p}\) , its singular values and corresponding right singular vectors. Then, we use the submatrix to exploit a new concise representation of the approximate left singular matrix \(\hat{U}\)  of \(A\) , i.e., \(\hat{U} = S V\Sigma ^{-1} \in \mathbb {R}^{m \times k}\) , where \(S \in \mathbb {R}^{m \times p}\) , \(V \in \mathbb {R}^{p \times k}\) , and \(\Sigma \in \mathbb {R}^{k \times k}\)  are our subsampled low rank approximations to \(A\) , \(V_{A}\) , and \(\Sigma _{A}\) , respectively (from \(A\) 's singular value decomposition in Definition REF ). Next, we use the approximate left singular matrix \(\hat{U}\)  of \(A\)  to calculate statistical leverage scores \(\ell _{i}\) , where \(i \in [m]\) . The core ideas are as follows. Firstly, based on \(\hat{U}_{i,:} = S_{i,:} V\Sigma ^{-1}\) , we present a logarithmic time to estimate \(S_{i,:} V\) , which can be achieved by Lemma REF  for all \(j \in [k]\)  to approximate the inner product \(S_{i,:} V_{:,j}\) , resulting the 1-by-\(k\)  vector \(\mathrm {t}^{T}\) . Secondly, we calculate the matrix-vector multiplication \(\tilde{U}_{i,:} = \mathrm {t}^{T} \Sigma ^{-1}\) , and then compute the inner product \(\tilde{\ell }_{i} = \tilde{U}_{i,:}\tilde{U}_{i,:}^{T}\) . Finally, we show that \(\tilde{\ell }_{i}\)  is a good approximation to \(\ell _{i}\)  in Theorem REF . Our algorithm takes time polynomial in integer \(k\) , condition number \(\kappa \)  and logarithm of the matrix size. The proposed algorithm achieves an exponential speedup over any other classical algorithms for approximating statistical leverage scores.
