[Wording] Algorithm-independent definition of `matrix_rank`

[lezcano]

The current definition of matrix_rank is:

Computes the rank (i.e., number of non-zero singular values) of a matrix

This is strongly biased towards the SVD view of the rank, which goes against point 4 of the design principles.

Edit Note that there are other algorithms that are rank-revealing. The most important is QR with pivoting present in LAPACK, which is also sometimes used to solve lstsq. See L351-395 of LAPACK's implementation.
LU with full pivoting strategies may also be made into a rank-revealing algorithm (see this paper with +150 citations) although no large library implements them to the best of my knowledge.

A more implementation agnostic definition would be "the number of independent columns". This gets closer into the intuition of what the rank of a linear map really is: The dimension of the image of the map.

cc @rgommers @mruberry

[asmeurer]

The rtol parameter is based on the singular values, so it's implicit in the current specification that it would be computed that way. If there are alternate algorithms that wouldn't be based on that, we might want to reconsider the inclusion of that parameter.

[lezcano]

Sorry, I did miss that point in the OP, I will update it for future reference.

There are indeed other algorithms that are rank-revealing. The most important is QR with pivoting present in LAPACK, which is also sometimes used to solve lstsq.
There is also LU with full pivoting strategies (see this paper with +150 citations) although no large library implements them to the best of my knowledge.

In particular, see the relevant part of the lstsq algorithm that estimates the rank via a PQR decomposition and certain estimation in L351-395 of LAPACK's implementation.

As such, I believe that it would be better to make this definition independent of the algorithm used to compute it.

[leofang]

I always took it that the number of singular values is determined by the matrix rank, so in a sense they are interchangeable and is not really tied to a specific algorithm. Though looking it at a different angle it does imply matrix_rank() internally calls svd().

I shared the same concern when reviewing the relevant PRs, and I was convinced by the fact that several other libraries (Matlab, Julia, etc) also describe it in the same fashion. If this becomes universal in numerical linear algebra (which I am not an expert in) then there's little merit to not follow the convention. Just my two cents.

[kgryte]

@leofang Thanks for pointing that out. Given the universality of the definition (across MATLAB, Julia, NumPy, etc), I'd lean toward keeping the definition as is.

[kgryte]

During the consortium meeting on 2021-07-29, a decision was made to keep the definition of matrix_rank as is, following conventions set forth in PyData ecosystem and elsewhere (MATLAB, Julia) where the matrix rank is defined in terms of the number of singular values.