This can be seen as a follow-up of #211.

The current definition of rtol in these functions reads:

rtol: relative tolerance for small singular values. Singular values less than or equal to rtol * largest_singular_value are set to zero

This rules out the implementation of these functions via algorithms based on the QR decomposition, which goes against Design Principle 4: Implementation Agnosticism.

Note that in LAPACK, the meaning of rcond in SVD-based lstsq solvers and QR-solvers are somewhat equivalent. The one using a QR-decomposition defines RCOND for the decomposition

A * P = Q * [ R11 R12 ]
            [  0  R22 ]

as the smallest k for which \sigma_1(R11) / \sigma_{k+1}(R11) >= 1/RCOND, that is, the k for which RCOND\sigma_1(R11) >= \sigma_{k+1}(R11). In this case they assume R22 = 0. Note that this is an approximation of the definition for the SVD, for which if RCOND\sigma_1(A) >=\sigma_{k+1}(A) then \sigma_r(A) is considered zero for r = k+1,...,n.

For this reason, a solution to this problem might go through rewording the definition of rtol in this functions in terms of condition numbers, although it is not clear to me how to write this down in a simple way.

A simpler but less satisfactory way to address this would be to simply define rtol as

Singular values approximately less than or equal to rtol * largest_singular_value are set to zero.

I do not completely like this solution, because it sort of biases the definition to be based on SVD-like algorithms, and it takes a few seconds to realise that this is also what LAPACK's QR with pivoting is doing .

cc @rgommers @mruberry