1
$\begingroup$

This question was moved from Cross-Validated: https://stats.stackexchange.com/questions/274042/pseudoinverse-of-large-sparse-matrix-in-r

I am trying to calculate the pseudoinverse of a large sparse matrix in R using the singular value decomposition. The matrix is roughly 240,000 x 240,000, and I have it stored as type dgCMatrix. I have tried using pinv, ginv, and other standard pseudoinverse functions, but they error out due to memory constraints. I then tried to opt for the sparse matrix svd provided by the package irlba, which I was then going to use to compute the pseudoinverse using the standard formula after converting all outputs to sparse matrices. My code is here:

lim = 40
digits = 4
SVD =irlba(L,lim)
tU = round(SVD$u,digits)
nonZeroU = which(abs(U)>0,arr.ind = T)
sparseU = sparseMatrix(i=nonZeroU[,2],j=nonZeroU[,1],x = U[nonZeroU])
V = round(SVD$v,digits)
nonZeroV = which(abs(V)>0,arr.ind = T)
sparseV = sparseMatrix(i=nonZeroV[,1],j=nonZeroV[,2],x = U[nonZeroV])
D = as(Diagonal(x=1/SVD$d),"sparseMatrx")
pL =D%*%sparseU
pL = sparseV%*%pL

I am able to get to the last line without an issue, but then I get an error due to memory constraints that says

Error in sparseV %*% pL : 
  Cholmod error 'problem too large' at file ../Core/cholmod_dense.c, line 105

Of course I could piece together the pseudoinverse entry by entry using a for loop and vector multiplications, but I would like to be able to calculate it using a simple function that takes advantage of the sparsity of the resultant pseudoinverse matrix. Due to the nature of the original matrix (it is a graph laplacian), I know that the pseudoinverse should also be a sparse matrix. Any help would be greatly appreciated!

$\endgroup$
9
  • $\begingroup$ How sparse is your matrix, how sparse do you expect the pseudoinverse to be? A dense 240000^2 matrix of 4 byte numbers requires more than 200GB for storage, let alone for handling. Also, in many cases the inverse of a sparse matrix ends up being a dense matrix. $\endgroup$ Apr 17, 2017 at 22:26
  • $\begingroup$ The matrix is very sparse-- <1%. The matrix L is a graph laplacian, so I expect the pseudoinverse to be equally sparse (I am saying this from empirical observation but haven't proven it yet) $\endgroup$
    – Paul
    Apr 17, 2017 at 23:33
  • 6
    $\begingroup$ Why do you expect the inverse of a Laplacian to be sparse? That's normally not true. $\endgroup$
    – cfh
    Apr 18, 2017 at 6:42
  • 1
    $\begingroup$ Do you really need the inverse/pseudoinverse matrix? For your use, you have considered the possibility of solving the linear system for applying the inverse transformation? $\endgroup$ Apr 18, 2017 at 7:44
  • 1
    $\begingroup$ If the earlier steps work well, can't you keep the matrix in factored form, evaluating matrix-vector products one at a time, like $V(D(Ux))$? Also, $L^{+}_{ij}$ has an interpretation in terms of the resistivity distance between $i$ and $j$, so I expect that for any connected component of the graph $L^{+}$ would be dense. Do you have a specific reason for thinking it would be sparse here? $\endgroup$
    – Kirill
    Apr 18, 2017 at 20:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.