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

Abstract

We describe and analyze a simple algorithm for sampling from the solution ${\mathbf{x}}^{\ast }:={\mathbf{A}}^{+}\mathbf{b}$ to a linear system $\mathbf{Ax}=\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 $\Vert {\mathbf{x}}^{\ast }-\mathbf{x}\Vert <\epsilon \Vert {\mathbf{x}}^{\ast }\Vert$ in $\tilde{O}(\hat{I}{º}_{\mathsf{F}}^4\hat{I}{º}^2/{\epsilon }^2)$ time, where $\hat{I}{º}_{\mathsf{F}}:=\Vert \mathbf{A}{\Vert }_{\mathsf{F}}\Vert {\mathbf{A}}^{+}\Vert$ and $\hat{I}º:=\Vert \mathbf{A}\Vert \Vert {\mathbf{A}}^{+}\Vert$. The representation of $\mathbf{x}$ allows us to query entries of $\mathbf{x}$ in $\tilde{O}(\hat{I}{º}_{\mathsf{F}}^2)$ time and sample proportional to the square entries of $\mathbf{x}$ in $\tilde{O}(\hat{I}{º}_{\mathsf{F}}^4\hat{I}{º}^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].