An improved quantum-inspired algorithm for linear regression

We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09, arXiv:0811.3171] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18, arXiv:1704.06174], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation. Namely, suppose we are given an A in mathbb{C}^{mtimes n} with minimum non-zero singular value σ which supports certain efficient ell₂-norm importance sampling queries, along with a b in mathbb{C}^m. Then, for some x in mathbb{C}ⁿ satisfying \|x - A^+b\| leq varepsilon\|A^+b\|, we can output a measurement of |xrangle in the computational basis and output an entry of x with classical algorithms that run in {mathcal{O}}big\(frac{\|A\|_F⁶\|A\|⁶}{σ¹²varepsilon⁴}big\) and {mathcal{O}}big\(frac{\|A\|_F⁶\|A\|²}{σ^8varepsilon4}big\) time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of frac{\|A\|¹⁶}{σ¹⁶varepsilon²} [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20, arXiv:1910.06151]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.