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 x^* := A⁺b to a linear system Ax = b. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of A. Our algorithm produces a compressed representation of some vector x for which \|x^* - x\| < ε \|x^* \| in O(κF⁴ κ² / ε²) time, where κF := \|A\|F\|A⁺\| and κ:= \|A\|\|A⁺\|. The representation of x allows us to query entries of x in O(κF²) time and sample proportional to the square entries of x in O(κF⁴ κ⁶) time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of 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].