title: Solving ill-conditioned symmetric system
body: <p>As the answer to <a href="https://stackoverflow.com/questions/66269318/numpy-and-solving-symmetric-system">this question</a> tells us, a symmetric positive definite linear system can be solved in quadratic time (using conjugate gradients). But now, suppose our system is ill-conditioned. Then, we know that we can approximate the solution to <code>A x = b</code> by <code>x = pinv(A) b.</code> But can this be done in sub-cubic time?</p>