Rank factorization of a matrix

1

Hi,

I have a tall rectangular matrix A of shape m by n, where m >> n, and it has a rank r such that r <= n.

I want to extract the set of r columns from A that are linearly independent, is there an implemented function in Pytorch that does this?

One way to do this is to perform a rank factorization algorithm, and I want to know if such an algorithm is implemented in Pytorch, because it will be more efficient than implementing it by hand, and support back-propagation.

Thank you in advance for your help!

2

Hi @nazareem,

Perhaps torch.svd_lowrank might be what you’re looking for?

3

Hi @AlphaBetaGamma96

Thank you for your response!
What does the torch.svd_lowrank exactly do? how it is different from the normal torch.linalg.svd?

If I understand correctly, the resulting matrix will have the same number of columns as our input matrix A, no?

4

Well, it does a low-rank approximation (of a specified rank) to a singular value decomposition, and given you’re looking for a rank factorization (of a specified rank) it might be what you’re looking for. The documentation explains a bit more in detail but the full detail can be found in Algorithm 5.1 of [0909.4061] Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

In your original link of rank factorization algorthim, torch.low_svdrank would be the SVD approach shown there.

5

Hi @AlphaBetaGamma96

Thank you for your help

I tried using it, it still returns a matrix that has the same dimension as my input matrix A, but that has rank q, specified as the parameter to the function.

This is not what I’m looking for, I’m looking for removing the linearly dependant column from matrix A, so I end up with a matrix that has the dimension m by r, that is full rank!

Basically, I’m looking for matrix C in this paragraph, I hope this made my question clear!