2021/11/17 by Qian Zuo, Hua Xiang, Zuo, Qian +1 · 1 citation
Computer Science · #FOS: Mathematics #Numerical Analysis (math.NA) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2111.08915
openalex publication_date 2021/11/17 · openalex created_date 2021/11/22 · openalex updated_date 2026/07/28
Suppose a matrix A ∈ ℝm × n of rank r with singular value decomposition A = UAΣA VAT, where UA ∈ ℝm × r, VA ∈ ℝn × r are orthonormal and ΣA ∈ ℝr × r is a diagonal matrix. The statistical leverage scores of a matrix A are the squared row-norms defined by ℓi = ‖(UA)i,:‖22, where i ∈ [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 κ and logarithm of the matrix size.