Algorithm to extract linearly dependent columns in a large scale [-1,1] matrix ( 10^5 by 10^6)
2 views (last 30 days)
Show older comments
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
5 Comments
Bruno Luong
on 4 Jan 2023
Edited: Bruno Luong
on 4 Jan 2023
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.
Answers (1)
See Also
Categories
Find more on Linear Algebra in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!