An improved quantum-inspired algorithm for linear regression
share
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig et al., Physical Review Letters'18], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation. Namely, given an A ∈ℂ^m× n with minimum singular value σ and which supports certain efficient ℓ_2-norm importance sampling queries, along with a b ∈ℂ^m, we can output a description of an x ∈ℂ^n such that x - A^+b≤εA^+b in 𝒪̃(A_F^6A^2/σ^8ε^4) time, improving on previous "quantum-inspired" algorithms in this line of research by a factor of A^14/σ^14ε^2 [Chia et al., STOC'20]. The algorithm is stochastic gradient descent, and the analysis bears similarities to those of optimization algorithms for regression in the usual setting [Gupta and Sidford, NeurIPS'18]. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired setting, for comparison against future quantum computers.
READ FULL TEXT