A quantum-inspired algorithm for approximating statistical leverage scores

Abstract

Suppose a matrix $A\in {\mathbb{R}}^{m\times n}$ of rank $r$ with singular value decomposition $A=U_A{\Sigma }_A{V}_A^T$, where $U_A\in {\mathbb{R}}^{m\times r}$, $V_A\in {\mathbb{R}}^{n\times r}$ are orthonormal and ${\Sigma }_A\in {\mathbb{R}}^{r\times r}$ is a diagonal matrix. The statistical leverage scores of a matrix $A$ are the squared row-norms defined by ${\ell }_i=\Vert (U_A{)}_{i,:}{\Vert }_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öm-based low rank matrix approximation as well as large-scale statistical data analysis applications, whose usual algorithm complexity is polynomial in the dimension of the matrix $A$. As an alternative to the conventional approach, and inspired by recent development on dequantization techniques, we propose a quantum-inspired algorithm for approximating the statistical leverage scores. We then analyze the accuracy of the algorithm and perform numerical experiments to illustrate the feasibility of our algorithm. Theoretical analysis shows that our novel algorithm takes time polynomial in an integer $k$, condition number $\kappa$ and logarithm of the matrix size.

References in corpus (18)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• Preconditioned quantum linear system algorithm
• Prediction by linear regression on a quantum computer
• A quantum linear system algorithm for dense matrices
• Quantum-Inspired Support Vector Machine
• Quantum gradient descent for linear systems and least squares
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum Circulant Preconditioner for Linear System of Equations
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Quantum algorithm for total least squares data fitting
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems

Cited by in corpus (1)

• pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores