We describe and analyze a simple algorithm for sampling from the solution $\mathbf{ x}^* := \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 $\|\mathbf{ x}^* - \mathbf{ x}\| < \varepsilon \|\mathbf{ x}^* \|$ in $\widetilde{ O}(\kappa_{ \mathsf{ F}}^4 \kappa^2 / \varepsilon^2)$ time, where $\kappa_{ \mathsf{ F}} := \|\mathbf{ A}\|_{ \mathsf{ F}}\|\mathbf{ A}^{ +}\|$ and $\kappa := \|\mathbf{ A}\|\|\mathbf{ A}^{ +}\|$. The representation of $\mathbf{ x}$ allows us to query entries of $\mathbf{ x}$ in $\widetilde{ O}(\kappa_{ \mathsf{ F}}^2)$ time and sample proportional to the square entries of $\mathbf{ x}$ in $\widetilde{ 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\'en, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].
Categories: cs.DS quant-ph