A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems

We describe and analyze a simple algorithm for sampling from the solution ${\mathbf{x}}^{\ast }:={\mathbf{A}}^{+}\mathbf{b}$ to a linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\mathbf{A}$. Our algorithm produces a compressed representation of some vector $\mathbf{x}$ for which $\mathrm{\parallel }{\mathbf{x}}^{\ast }-\mathbf{x}\mathrm{\parallel }<\epsilon \mathrm{\parallel }{\mathbf{x}}^{\ast }\mathrm{\parallel }$ in $\tilde{O}({\kappa }_{\mathsf{F}}^4{\kappa }^2\mathrm{/}{\epsilon }^2)$ time, where ${\kappa }_{\mathsf{F}}:=\mathrm{\parallel }\mathbf{A}{\mathrm{\parallel }}_{\mathsf{F}}\mathrm{\parallel }{\mathbf{A}}^{+}\mathrm{\parallel }$ and $\kappa :=\mathrm{\parallel }\mathbf{A}\mathrm{\parallel }\mathrm{\parallel }{\mathbf{A}}^{+}\mathrm{\parallel }$. The representation of $\mathbf{x}$ allows us to query entries of $\mathbf{x}$ in $\tilde{O}({\kappa }_{\mathsf{F}}^2)$ time and sample proportional to the square entries of $\mathbf{x}$ in $\tilde{O}({\kappa }_{\mathsf{F}}^4{\kappa }^6)$ time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of $\mathbf{A}$. Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gilyén, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].