CODEWITHSUNDEEP
rmatrixrankcran
Jeroen Ooms
Jeroen Ooms

Reputation: 32978

Storing a large but low-rank matrix efficiently

I know there are packages in R to store sparse matrices efficiently. Is there also a way to store a low-rank matrix efficiently? For example:

A <- matrix(rnorm(1e6), nrow=1e5, ncol=1e1)
B <- A %*% t(A)

Now, B is too large to store in memory, but it is low in rank. Is there any way to construct and store B in an efficient way, such that some basic read methods (rowSums, colSums, etc) are performed on the fly, in order to trade for cpu or memory?

Upvotes: 7

Views: 1059

Answers (2)

Lutz Lehmann
Lutz Lehmann

Reputation: 25972

Your question is already the answer: To store such a low rank matrix efficiently, you make a data structure containing both factors. If matrix-vector multiplication is required, it can be done from right to left using matrix-vector products of the factors.

One application of this strategy and data structure can be found in implementations of limited-memory Broyden or BFGS quasi-Newton methods.

Upvotes: 2

flonk
flonk

Reputation: 3876

Here's another approach, although I miss the experience to know how efficient this would be for large matrices:

If the rank is low, it means the matrix contains many irrelevant lines, which are linear combinations of others. If the matrix represents a linear system of equations, one could design an algorithm, which successively removes those lines.

To check if a line is irrelevant, check if the rank of the matrix without that line is still the same. For computing the matrix rank, see this and that answer.

Upvotes: 0

Related Questions