We present classical sublinear-time algorithms for solving low-rank linear
systems of equations. Our algorithms are inspired by the HHL quantum algorithm
for solving linear systems and the recent breakthrough by Tang of dequantizing
the quantum algorithm for recommendation systems. Let $A \in \mathbb{C}^{m
\times n}$ be a rank-$k$ matrix, and $b \in \mathbb{C}^m$ be a vector. We
present two algorithms: a "sampling" algorithm that provides a sample from
$A^{-1}b$ and a "query" algorithm that outputs an estimate of an entry of
$A^{-1}b$, where $A^{-1}$ denotes the Moore-Penrose pseudo-inverse. Both of our
algorithms have query and time complexity $O(\mathrm{poly}(k, \kappa, \|A\|_F,
1/\epsilon)\,\mathrm{polylog}(m, n))$, where $\kappa$ is the condition number
of $A$ and $\epsilon$ is the precision parameter. Note that the algorithms we
consider are sublinear time, so they cannot write and read the whole matrix or
vectors. In this paper, we assume that $A$ and $b$ come with well-known
low-overhead data structures such that entries of $A$ and $b$ can be sampled
according to some natural probability distributions. Alternatively, when $A$ is
positive semidefinite, our algorithms can be adapted so that the sampling
assumption on $b$ is not required.

本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。