Get linearly depend rows of matrix 2N x N with N large (GPU-compatible)

Hello everyone,

I know that there is already a lot of helpful information on this topic here: I am having a N x 2N matrix A and would like to remove these columns of A such that A has full rank and is optimally conditioned. This works amazingly well with the QR decomposition with column pivoting, as can be used in Matlab as follows:

N       = 1000;
A       = rand( N, 2*N );
[Q,R,E] = qr(A,'vector');
tol     = 1.0;
rankA    = find( abs(diag(R)) >= tol, 1, 'last');
idx    = sort(E(1:rankA));

A_red   = A(:,idx);

The problem, however, is that N will get quite large, something like N = 10000. The GPU version of the QR algorithm is very fast, but it does not support the column pivoting (only Q and R are returned, not the permutation vector E). Do some of you know about ways to use different fast approaches (SVD, EIG, ...) to solve the above problem? Or maybe there is a way to synthesize some permutation vector E from the Q and R matrices? Otherwise, are there GPU implementations with column pivoting available which can be easily compiled to be used in Matlab? Thanks a lot in advance for your helpful comments!

Warm regards

Mathias

[Matt J]

I wonder even about the QR method. I can see that this would work as long as R always satisfies

   abs(R(i,i))>=abs(R(i,j))

for all j>=i. This property always seems to hold in randomized examples. Can't seem to find a proof of this, however.

[Mathias]

Hey, I am not quite sure if I understand you correctly? You mean you're wondering if the method I've shown works in any case? It wouldn't be too critical if the resulting reduced matrix was not be the strictly optimal solution. I am more interested in the pattern, in which the rows are removed from the matrix.

That's why I could imagine, that you could actually use another "metric" for how important the rows are rather than the pivoting order...