A quantum-inspired algorithm for approximating statistical leverage scores

Suppose a matrix $A \in \mathbb{R}^{m \times n}$ of rank $k$ with singular value decomposition $A = U_{A}\Sigma_{A} V_{A}^{T}$, where $U_{A} \in \mathbb{R}^{m \times k}$, $V_{A} \in \mathbb{R}^{n \times k}$ are orthonormal and $\Sigma_{A} \in \mathbb{R}^{k \times k}$ is a diagonal matrix. The statistical leverage scores of a matrix $A$ are the squared row-norms defined by $\ell_{i} = \|(U_{A})_{i,:}\|_2^2$, where $i \in [m]$, and the matrix coherence is the largest statistical leverage score. These quantities play an important role in machine learning algorithms such as matrix completion and Nystr\"{o}m-based low rank matrix approximation as well as large-scale statistical data analysis applications. The best known classical algorithm to approximate these values runs in time $O((mn + n^3){\rm log}\,m)$ in [P. Drineas, M. Magdon-Ismail, M. W. Mahoney and D. P. Woodruff. Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res., (2012)13: 3475-3506]. In this work, inspired by recent development on dequantization techniques, we propose a fast novel classical algorithm for approximating the statistical leverage scores. Our novel algorithm has query and time complexity $O\left({\rm poly} \left(k, \kappa, \frac{1}{\epsilon}, \frac{1}{\delta}, {\rm log}(mn)\right) \right)$, where $\kappa$ is the condition number of $A$, and $\delta$ is the failure probability.