Abstract
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_FA⁺ and κ := AA⁺. 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\'en, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].