Fast quantum algorithms for Least Squares Regression and Statistic Leverage Scores Yang Liu Shengyu Zhang The Chinese University of Hong Kong
Yang Liu Shengyu Zhang The Chinese University of Hong Kong Fast quantum algorithms for Least Squares Regression and Statistic Leverage Scores
Part 1.Linear regression -Output a“quantum sketch”of solution. Part ll.Computing leverage scores and matrix coherence. Output the target numbers
• Part I. Linear regression – Output a “quantum sketch” of solution. • Part II. Computing leverage scores and matrix coherence. – Output the target numbers
Part I:Linear regression Solve overdetermined linear system Ax =b, where A∈Rnxp,x∈RP,b∈Rn,n≥p. Goal:compute minllAx-bll. X Least Square Regression (LSR)
Part I: Linear regression • Solve overdetermined linear system 𝐴𝑥 = 𝑏, where 𝐴 ∈ ℝ𝑛×𝑝 , 𝑥 ∈ ℝ𝑝 , 𝑏 ∈ ℝ𝑛 , 𝑛 ≥ 𝑝. • Goal: compute min 𝑥 𝐴𝑥 − 𝑏 2 2 . – Least Square Regression (LSR)
Closed-form solution Closed-form solution known: x*=A+b=(AA)1AT, -A+:Moore-Penrose pseudo-inverse of A. If the SVD of A is Anxp UnxrDrxrVTxp where r rank(A),then A+VD-1UT. Classical complexity:0(n2p +np2) Prohibitively slow for big matrices A
Closed-form solution • Closed-form solution known: 𝑥 ∗ = 𝐴 +𝑏 = 𝐴 𝑇𝐴 −1𝐴 𝑇 , – 𝐴 +: Moore-Penrose pseudo-inverse of 𝐴. – If the SVD of 𝐴 is 𝐴𝑛×𝑝 = 𝑈𝑛×𝑟𝐷𝑟×𝑟𝑉𝑟×𝑝 𝑇 where 𝑟 = 𝑟𝑎𝑛𝑘(𝐴), then 𝐴 + = 𝑉𝐷 −1𝑈 𝑇 . • Classical complexity: 𝑂 𝑛 2𝑝 + 𝑛𝑝 2 • Prohibitively slow for big matrices 𝐴
Relaxations 。Relaxation: -Approximate:outputx*. -Important special case:Sparse and low-rank A:0(s nr)*1,2,where .s =non-zero entries in each row/column. 。r=rank(A. Quantum speedup?Even writing down the solution x*takes linear time. *1.K.Clarkson,D.Woodruff.STOC,2013. *2.J.Nelson,H.Nguyen.FOCS,2013
Relaxations • Relaxation: – Approximate: output 𝑥 ≈ 𝑥 ∗ . – Important special case: Sparse and low-rank 𝐴: 𝑂෨ 𝑠 + 𝑛𝑟 * 1,2, where • 𝑠 = # non-zero entries in each row/column. • 𝑟 = 𝑟𝑎𝑛𝑘(𝐴) . • Quantum speedup? Even writing down the solution 𝑥 ∗ takes linear time. *1. K. Clarkson, D. Woodruff. STOC, 2013. *2. J. Nelson, H. Nguyen. FOCS, 2013