Algorithm to extract linearly dependent columns in a large scale [-1,1] matrix ( 10^5 by 10^6)

I am trying to find an efficient algorithm for extracting linear independent collumns ( an old problem) but on a Very large matrix ( 10^5 rows, 10^6 columns) with all +-1 Real elements.... so , a dense matrix.

these matrcies are so large that I have no hope to put them in memory all at once, and then use the standard QR algorithm (or other real matrix decompositions that I have found) .

I know the choice of spanning collumns are not unique. I just want a subset "Q" of N colums of the Matrix A, such that rank(A) = N = rank(Q)

I have been looking for a clever random algorithm with bounded error.

Cheers

[Bruno Luong]

How currently the matrix is stored when you say "I have no hope to put them in memory all at once"?

What is typical rank of A?

[Matt J]

And, how do such hideously large matrices come about....?

[Wayne Shanks]

Generaly in Machine vision and ML... these are generaly QBO ( Quadratic Binary Optimization)

I am looking at ways to shrink these problems down from their "hideously large" starts

These systems generaly have a rank that is 10X smaller than the collumn vector... so the rank, N = ~10^4

My top contender are just modified Gram Schmidt types algorithms, run on a GPU, searching for dependent columns while building a Basis, projected run times are hours to days.

[Wayne Shanks]

I store these matricies as blocks of binary files, When I load them into memory to process , I convert the [0,1] bts to [-1,1] single floats

I am starting to read some articles on "out of core SVD" algorithms,

[Bruno Luong]

SVD cannot find independent set of columns, QR does.

Do not use Gram Schmidt, it is numerically unstable. Use Housholder, and Q-less QR algorithm with permutation, until the projection is numerically 0.

But still storing R required few hundred Gb. It is doable on HD but it will take very long to compute.

Answer 1

[Joss Knight]

You might consider using distributed arrays on an HPC cluster.